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 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 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 4 Ví dụ 1 Cho dãy S: Tìm xem trong dãy có phần tử k=33 Quá trình tìm kiếm 45 3 34 13 7 43 9 110 45 3 34 13 7 43 9 110 Bước 1 Bước 8Bước 7 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 9 • Không tìm thấy Search 5 Ví dụ 2 Cho dãy S: Tìm xem trong dãy có phần tử k=13 Quá trình tìm kiếm 45 3 34 13 7 43 9 110 45 3 34 13 7 43 9 110 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 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 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 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 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 10 Ví dụ 1 1 3 4 5 7 8 9 11 14 16 18 190 • Cho dãy dưới đây. Tìm phần tử k=6 Bước1: 6< 1 3 4 5 70 Bước 2: 6> 4 5 7 Bước 3: 6> 7 Bước 4: 6< Bước 5: 6 Rỗng Không tìm thấy [...]... 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 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())... 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< p->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 {... TreeSearch(Keys k, Node* v) if(v==NULL) return v; else if (k < v->getKey()) return TreeSearch(k, v->Left()); else if (k == v->getKey()) return v else // k > key(v) return TreeSearch(k, v->Right()); Search 20 Ví dụ < 2 1 6 9 > 4 = 8 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()) Search 21 Phân tích Thuật toán TreeSearch... 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 Ví dụ: Mô tả từng bước xóa bỏ nút có key=58? 58 31 90 62 25 12 75 64 63 Search 36 ... cây- Insertion Sau khi bổ sung cây vẫn thỏa mãn tính chất cây TKNP 6 < Bổ sung một nút với khóa k và value x  2 Thực hiện tìm kiếm k trên cây 1 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 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 5 9 > 4 8 > 6 2 1 9 4 8 5 Search 24 void TreeInsert(Keys k, Object elem) q = new Node(); q->setKey(k);... bên phải Các nút con trái và phải cũng là cây tìm kiếm nhị phân Search 6 < < 2 10 0 -1 8 4 1 3 5 7 9 Ví dụ: Cây tìm kiếm nhị phân 14 Cây tìm kiếm nhị phân (Binary search tree) < 2 6 9 > 4 = 1 Search 8 15 find(4) < 2 1 6 > 9 4 = Search 8 12 16 Cấu trúc Node biểu diễn cây Phương thức nhị phân  Node *Parent()   Thuộc tính  Node *Left()  Node *Right()  Keys key  Object elem  void setLeft(Node*)... hasLeft()  Node *Right  int hasRight()  Object getElem() Chú ý: Keys là tập các giá trị được sắp có thứ tự  void setElem(Object o)  void setKey(Keys k) Search  Keys getKey() 17 Cấu trúc của cây tìm kiếm nhị phântính Thuộc  Các phương thức truy Node * root cập: Phương thức  Node *root()  int size()  int isEmpty()  int isInternal(Node*)  int isExternal(Node*)  int isRoot(Node*)  void preOrder(Node*)... phai if(p->Right() == NULL){ q->setParent(p); p->setRight(q); p = NULL; } else p = p->Right; else { delete q; break;} } } Search 25 Ví dụ < 2 1 6 9 > 4 = Search 8 26 Xóa – Sau khi xóa cây vẫn thỏa mãn tính chất cây TKNP Xẩy ra hai khả năng:   Nút cần xóa là nút trong Nút cần xóa là nút ngoài Xó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 . v) if(v==NULL) return v; else if (k < v->getKey()) return TreeSearch(k, v->Left()); else if (k == v->getKey()) return v else // k > key(v) return TreeSearch(k, v->Right()); Thuật toán giả. 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 . getKey() Chú ý: Keys là tập các giá trị được sắp có thứ tự Search 18 Cấu trúc của cây tìm kiếm nhị phân Thuộc tính  Node * root Phương thức  int size()  int isEmpty()  int isInternal(Node*)  int