Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 13. Tìm kiếm- Search

Search 1Bài 13. Tìm kiếm- SearchBài toánInput: Cho một dãy S các phần tử, mỗi phần tử là một bộ gồm khóa-giatrị (key-value). Một khóa k bất kỳ.Output: Trong S có phần tử có khóa k hay không?Search 2Các phương pháp tìm kiếm Tìm kiếm tuần tự (sequence search) Tìm kiếm nhị phân (Binary search) Bảng băm (hash table)Search 31. Tìm kiếm tuần tựTập S các phần tử được lưu bằng mảng hoặc danh sách liên kết. Thuật toán tìm kiếm: Xuất phát từ phần tử đầu của dãy, thực hiện so sánh khóa của nó với k. Nếu trùng nhau thì dừng lại, nếu không trùng thì lặp lại với phần tử tiếp theo. Quá trình dừng lại khi tìm thấy hoặc không còn phần tử nào nữa. Khi đó thông báo không tìm thấy.Search 4Ví dụ 1 Cho dãy S:Tìm xem trong dãy có phần tử k=33Quá trình tìm kiếm4533413743911045334137439110Bước 1Bước 8Bước 7Bước 2Bước 3Bước 4Bước 5Bước 6Bước 9 Không tìm thấySearch 5Ví dụ 2 Cho dãy S:Tìm xem trong dãy có phần tử k=13Quá trình tìm kiếm4533413743911045334137439110Bước 1Bước 2Bước 3Bước 4Bước 5 Tìm thấy, tại vị trí 5Search 6Thuật toánInput: Cho một dãy S các phần tử, mỗi phần tử là một bộ key và value. Một khóa k bất kỳ.Output: Trong S có phần tử có khóa k hay không?found = 0; i =1;while ((chưa duyệt hết S ) && (found= =0) ){ if (S[i].key == k) found =1; i = i+1;}return found;Search 7Thời gian chạy Trong trường hợp xấu nhất thuật toán phải duyệt qua tất cả các phần tử của S. Vậy thời gian chạy là O(n)Search 82. Tìm kiếm nhị phân Tập S được tổ chức lưu trữ dựa trên mảngTập S được tổ chức lưu trữ dạng cây nhị phânSearch 92.1Tìm kiếm nhị phân trên mảng Các phần tử của S được lưu trữ trong mảng và được sắp xếp theo thứ tự tăng dần (giảm dần) của giá trị khóa (key). Thuật toán tìm kiếm nhị phân được thiết kế dựa trên chiến lược chia và trị Thuật toán: So sánh khóa k với khóa của phần tử ở giữa dãy. Nếu trùng thì thông báo tìm thấy và dừng Nếu k> thì gọi đệ qui tìm trên nửa cuối dãy Nếu k457Bước 3: 6>7Bước 4: 6457Bước 3: 5=Tìm thấySearch 12Algorithm BinarySearch(S, k, n); Found = 0; i = 1; j = n; while(i=Search 16692418=find(4)12Search 17Cấu trúc Node biểu diễn cây nhị phânThuộc tínhKeys keyObject elemNode *ParentNode *LeftNode *RightPhương thứcNode *Parent()Node *Left()Node *Right()void setLeft(Node*)void setRight(Node*)void setParent(Node *)int hasLeft() int hasRight()Object getElem()void setElem(Object o)void setKey(Keys k)Keys getKey()Chú ý: Keys là tập các giá trị được sắp có thứ tựSearch 18Cấu trúc của cây tìm kiếm nhị phânThuộc tínhNode * rootPhương thứcint size()int isEmpty()int isInternal(Node*)int isExternal(Node*)int isRoot(Node*)void preOrder(Node*)void inOrder(Node*)void postOrder(Node*)Node * TreeSearch(Keys, Node*)Node * InsertTree(Keys, Object ) void Remove(Keys) Các phương thức truy cập: Node *root()Search 19Thuật toán tìm kiếmTìm trong cây có nút có khóa bằng k không?Thuật toánXuất phát từ nút gốcSo sánh giá trị khóa của nút gốc với kNếu giá trị của gốc =k thì trả lại đ/c của nút dừng lạiNếu giá trị của nút gốc k thì gọi đệ qui tìm trên cây con tráiQuá trình tìm dừng lại khi tìm thấy hoặc phải tìm trên cây rỗng, trả lại địa chỉ của nút mà thuật toán dừng lạiSearch 20Node* TreeSearch(Keys k, Node* v) if(v==NULL) return v;else if (k getKey()) return TreeSearch(k, v->Left());else if (k == v->getKey()) return velse // k > key(v) return TreeSearch(k, v->Right());Thuật toán giả mãSearch 21Ví dụTìm giá trị 4 trên cây:Gọi T.TreeSearch(4, T.root())Gọi T.TreeSearch(4, T.root()->Left()))Gọi T.TreeSearch(4, T.root()->Left()->Right())692418=Search 22Phân tíchThuật toán TreeSearch Là thuật toán đệ qui, Mỗi lần gọi đệ qui nó thực hiện một số phép toán cơ bàn không đổi, vậy một lần gọi đệ qui cần thời gian là O(1)Thực hiện gọi đệ qui dọc theo các nút, bắt đầu từ nút gốc, mỗi lần gọi đệ qui nó đi xuống một mức.Do đó số nút tối đa mà nó phải đi tới không vượt quá chiều cao h của cây.Thòi gian chạy là O(h)Cây T Trong trường hợp xấu nhất cây có chiều cao bằng bao nhiêu?Search 23Một số trường hợp Cây chỉ có con trái hoặc con phảiChiều cao cây bằng số nút của cây Cây hoàn chỉnhChiều cao của cây là log2n69241812691215Search 24 Bổ sung nút vào cây- InsertionSau khi bổ sung cây vẫn thỏa mãn tính chất cây TKNPBổ sung một nút với khóa k và value xThực hiện tìm kiếm k trên câyGiả sử k không có trên cây, khi đó ta sẽ tìm đến được một nút lá của cây. Khi đó tạo ra một nút mới và đặt nó là con trái hoặc con phải của nút lá đó.Ví dụ: Bổ sung 5692418>6924185Search 25void TreeInsert(Keys k, Object elem)q = new Node(); q->setKey(k); q->setEmlem(elem);q->setLeft(NULL); q->setRight(NULL); q->setParent(NULL);if(root==NULL){root = q;}else{ p = root; while(p != NULL){ if(kgetKey()) if(p->Left()==NULL){ q->setParent(p); p->setLeft(q); p = NULL; }else p = p->Left(); else if(k> p->getKey()) // nam ben cay con ben phai if(p->Right() == NULL){ q->setParent(p); p->setRight(q); p = NULL; } else p = p->Right; else { delete q; break;} } }Search 26Ví dụ692418=Search 27Xóa – Sau khi xóa cây vẫn thỏa mãn tính chất cây TKNPXẩy ra hai khả năng:Nút cần xóa là nút trongNút cần xóa là nút ngoàiXóa một nút trong yêu cầu giải quyết lỗ hổng bên trong câyĐể thực hiện thao tác remove(k), Chúng ta tìm kiếm đến nút có khóa kGiả sử rằng khóa k có ở trên cây, và ta đặt v là nút lưu trữ k6924185vwSearch 28Xóa nút ngoài Xóa bỏ nút V6924185vSearch 29Xóa nút trong v chỉ có con trái hoặc phảiLoại bỏ v và thay thế cây con của v vào vai trò của v Ví dụ: xóa bỏ 46925186924185vw6924183vSearch 30Xóa nút trong v có cả hai nút con trái và phảiChúng ta tìm nút w, w là nút được thăm đầu tiên bằng phương pháp duyệt theo thứ tự giữa (inorder) bắt đầu từ nút con phải của nút vĐổi chỗ hai phần tử lưu trong v và w Khi đó w là nút có thể là nút không có con hoặc nút có con bên phải.Thực hiện loại bỏ w như trong hai trường hợp đã nêu trênVí dụ: xóa bỏ 351869v2318695vwz2Search 31Ví dụ Xóa phần tử 331812v2w108112v2w10Search 32Thuật toán giả mãXây dựng hàm phương thức duyệt trên một cây con của cây theo thứ tự giữa, hàm trả lại điạ chỉ của nút đầu tiên được thămXây dựng hàm xóa bỏ một nút trên câySearch 33Hàm duyệt cây con của một cây theo thứ tự giữa và trả lại đ/c của nút được thăm đầu tiên void InOrder(Node *v, Node *first, int* kt){ if(v!=null && kt!=1){ InOrder(v.Left(),first, kt); if(kt==0) first = v; kt=1; InOrder(v.Right(),first, kt); }}Search 34Hàm xóa một nút v của cây khi v có con trái hoặc con phảivoid Remove(Node *v){if(v->hasLeft() && (!v->hasRight()){ p=v->getParent(); if(p->Left()==v) p->setLeft(v->Left()); else p->setRight(v->Left()); } if((!v->hasLeft()) && (v->hasRight()){ p=v->getParent(); if(p->Left()==v) p->setLeft(v->Right()); else p->setRight(v->Right()); } delete v;}Search 35Hàm xóa nút bất kỳ trên câyvoid Remove(Keys k){ Node *v = TreeSearch(root, k); if(v==NULL) return; if((v->hasLeft() && !v->hasRight()) || ((v->hasRight() && !v->hasLeft())) Remove(v); else{Node *first; int kt=0;InOrder(v->Right(), first, kt); v->setKey(first->getKeys());v->setElem(first->getElem());Remove(first);}} Search 36Ví dụ: Mô tả từng bước xóa bỏ nút có key=58?589075623112256463Search 37Đánh thời gianXem xét việc cài đặt một từ điển có n mục được cài dặt bằng một cây nhị phân tìm kiếm với chiều cao hBộ nhớ sử dụng O(n)Phương thức find, insert và remove take O(h) timeTrong trường hợp xấu nhất chiều cao của cây là O(n) và trường hợp tốt nhất là O(log n)Search 38Bài tậpXây dựng lớp cây tìm kiếm nhị phânSử dụng lớp cây tìm kiếm nhị phân xây dựng một chương trình tra cứu từ điển có các chức năng sau:Đọc dữ liệu từ điển nạp vào cây từ tệpBổ sung từ mới vào câyXóa bỏ một từ khỏi câyTìm kiếm từ Lưu cây vào tệpSearch 39Ra chơi