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

Nội dung text: 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

1. Bài 13. Tìm kiếm- Search Bài toán Input: 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 1
2. Cá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 2
3. 1. 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 3
4. Ví dụ 1 Cho dãy S: 0 45 3 34 13 7 43 9 11 Tìm xem trong dãy có phần tử k=33 Quá trình tìm kiếm 0 45 3 34 13 7 43 9 11 Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Bước 9 • Không tìm thấy Search 4
5. Ví dụ 2 Cho dãy S: 0 45 3 34 13 7 43 9 11 Tìm xem trong dãy có phần tử k=13 Quá trình tìm kiếm 0 45 3 34 13 7 43 9 11 Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 • Tìm thấy, tại vị trí 5 Search 5
6. Thuật toán Input: 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 6
7. Thờ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 7
8. 2. Tìm kiếm nhị phân Tập S được tổ chức lưu trữ dựa trên mảng Tập S được tổ chức lưu trữ dạng cây nhị phân Search 8
9. 2.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 k< thì gọi đệ qui tìm trên nửa đẫu dãy • Quá trình tìm nếu phải tìm trong dãy rỗng thì dưng lại và thông báo không tìm thấy Search 9
10. Ví dụ 1 • Cho dãy dưới đây. Tìm phần tử k=6 0 1 3 4 5 7 8 9 11 14 16 18 19 Bước1: 6 4 5 7 Bước 3: 6> 7 Bước 4: 6< Rỗng Bước 5: 6 Không tìm thấy Search 10
11. Ví dụ 2 • Cho dãy dưới đây. Tìm phần tử k=5 0 1 3 4 5 7 8 9 11 14 16 18 19 Bước1: 5 4 5 7 Tìm thấy Bước 3: 5= Search 11
12. Thuật toán tìm kiếm nhị phân trên mảng Algorithm BinarySearch(S, k, n); Found = 0; i = 1; j = n; while(i<=j && Found!=1) mid = (i+j) / 2; if (k==S[mid].Key) Found = 1; else if (k < S[mid].Key) j = mid – 1; else i = mid+1; return Found; Search 12
13. Thời gian chạy Sau mỗi lần tìm kiếm, thì dãy cần tìm lại được chia đôi và ta chỉ phải tìm trên một nửa Trong trường hợp xấu nhất là không tìm thấy phần tử có khóa k. Và như vậy ta phải thực hiện chia đôi liên tiếp đến khi được dãy rỗng. Số lần thực hiện chia đôi là: log2n Vậy thời gian chạy là O(log2n) Search 13
14. 2.2 Tìm kiếm trên cây tìm kiếm nhị phân Định nghĩa: cây tìm 6 kiếm nhị phân là cây < < nhị phân thỏa mãn: 2 10 n Nút cha có khóa lớn hơn 8 khóa của tất cả các nút 0 4 của cây con bên trái và 5 9 nhỏ hơn khóa của tất cả -1 1 3 7 các nút của cây con bên phải. n Các nút con trái và phải Ví dụ: Cây tìm kiếm nhị cũng là cây tìm kiếm nhị phân phân Search 14
15. Cây tìm kiếm nhị phân (Binary search tree) 9 1 4 = 8 Search 15
16. find(4) 9 = 12 1 4 8 Search 16
17. Cấu trúc Node biểu diễn cây nhị phân n Phương thức w Node *Parent() n Thuộc tính w Node *Left() w Keys key w Node *Right() w Object elem w void setLeft(Node*) w Node *Parent w void setRight(Node*) w Node *Left w void setParent(Node *) w Node *Right w int hasLeft() w int hasRight() Chú ý: Keys là tập các w Object getElem() giá trị được sắp có thứ w void setElem(Object o) tự w void setKey(Keys k) w Keys getKey() Search 17
18. Cấu trúc của cây tìm kiếm nhị phân Thuộc tính v Các phương thức truy n Node * root Phương thức cập: § Node *root() n int size() n int isEmpty() n int isInternal(Node*) n int isExternal(Node*) n int isRoot(Node*) n void preOrder(Node*) n void inOrder(Node*) n void postOrder(Node*) n Node * TreeSearch(Keys, Node*) n Node * InsertTree(Keys, Object ) n void Remove(Keys) Search 18
19. Thuật toán tìm kiếm Tìm trong cây có nút có khóa bằng k không? Thuật toán n Xuất phát từ nút gốc n So sánh giá trị khóa của nút gốc với k w Nếu giá trị của gốc =k thì trả lại đ/c của nút dừng lại w Nếu giá trị của nút gốc k thì gọi đệ qui tìm trên cây con trái w Quá 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ại Search 19
20. Thuật toán giả mã Node* 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 v else // k > key(v) return TreeSearch(k, v->Right()); Search 20
21. Ví dụ 9 1 4 = 8 Tìm giá trị 4 trên cây: n Gọi T.TreeSearch(4, T.root()) n Gọi T.TreeSearch(4, T.root()->Left())) n Gọi T.TreeSearch(4, T.root()->Left()->Right()) Search 21
22. Phân tích Thuật toán TreeSearch n Là thuật toán đệ qui, n 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) n 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. n Do đó số nút tối đa mà nó phải đi tới không Cây T vượt quá chiều cao h của cây. n Thòi gian chạy là O(h) Trong trường hợp xấu nhất cây có chiều cao bằng bao nhiêu? Search 22
23. Một số trường hợp Cây chỉ có con trái 6 hoặc con phải 9 12 n Chiều cao cây bằng 15 số nút của cây Cây hoàn chỉnh 6 n Chiều cao của cây là 2 9 log2n 1 4 8 12 Search 23
24. Bổ sung nút vào cây- Insertion Sau khi bổ sung cây vẫn thỏa mãn tính chất cây TKNP Bổ sung một nút với n Thực hiện tìm kiếm k 1 4 8 trên cây > Giả 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 6 một nút mới và đặt nó 2 9 là con trái hoặc con phải của nút lá đó.Ví 1 4 8 dụ: Bổ sung 5 5 Search 24
25. void 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(k getKey()) 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 25
26. Ví dụ 9 1 4 = 8 Search 26
27. Xóa – Sau khi xóa cây vẫn thỏa mãn tính chất cây TKNP 6 Xẩy ra hai khả năng: n Nút cần xóa là nút ngoài Xóa một nút trong yêu 1 4 v 8 w cầu giải quyết lỗ hổng 5 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 k Giả sử rằng khóa k có ở trên cây, và ta đặt v là nút lưu trữ k Search 27
28. Xóa nút ngoài 6 1 4 8 v 5 Search 28
29. Xóa nút trong v chỉ có con trái hoặc phải 6 Loại bỏ v và thay thế cây con Ví dụ: xóa bỏ 4 1 4 v 8 w 6 5 1 4 v 8 6 3 2 9 1 5 8 Search 29
30. Xóa nút trong v có cả hai nút con trái và phải 1 Chúng ta tìm nút w, w là nút v được thăm đầu tiên bằng 3 phương pháp duyệt theo thứ 2 8 tự giữa (inorder) bắt đầu từ nút con phải của nút v 6 9 Đổi chỗ hai phần tử lưu trong w v và w 5 Khi đó w là nút có thể là nút z không có con hoặc nút có con bên phải. 1 Thực hiện loại bỏ w như trong v hai trường hợp đã nêu trên 5 2 8 Ví dụ: xóa bỏ 3 6 9 Search 30
31. Ví dụ 1 • Xóa phần tử 3 v 3 2 8 w 12 10 1 v 8 2 12 w 10 Search 31
32. Thuậ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ăm Xây dựng hàm xóa bỏ một nút trên cây Search 32
33. Hà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 33
34. Hàm xóa một nút v của cây khi v có con trái hoặc con phải void 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 34
35. Hàm xóa nút bất kỳ trên cây void 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 35
36. Ví dụ: Mô tả từng bước xóa bỏ nút có key=58? 58 31 90 25 62 12 75 64 63 Search 36
37. Đánh thời gian Xem 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 h n Bộ nhớ sử dụng O(n) n Phương thức find, insert và remove take O(h) time Trong 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 37
38. Bài tập Xây dựng lớp cây tìm kiếm nhị phân Sử 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: n Đọc dữ liệu từ điển nạp vào cây từ tệp n Bổ sung từ mới vào cây n Xóa bỏ một từ khỏi cây n Tìm kiếm từ n Lưu cây vào tệp Search 38