Cây nhị phân tìm kiếm (Binary Searching Tree)

12.3. Cây nhị phân tìm kiếm (Binary Searching Tree) 2.3.1. Khái niệm – Cấu trúc dữ liệu  Cây nhị phân tìm kiếm là cây nhị phân trong đó tại mỗi nút, khoá của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khoá của tất các nút thuộc cây con phải.  Cấu trúc dữ liệu của cây nhị phân tìm kiếm là cấu trúc dữ liệu biểu diễn cây nhị phân nói chung. struct TNode { int Info; struct TNode *pL,*pR; }; 22.3. Cây nhị phân tìm kiếm (Binary Searching Tree) 2.3.2. Các thao tác trên cây nhị phân tìm kiếm 2.3.2.a. Thêm vào một phần tử X vào cây 2.3.2.b. Tạo một cây NPTK 2.3.2.c. Duyệt cây 2.3.2.d. Tìm một phần tử X trong cây 2.3.2.e. Huỷ một phần tử có khoá X 32.3.2.a. Thêm vào một phần tử X vào cây Việc thêm một phần tử x vào cây phải đảm bảo điều kiện ràng buộc của CNPTK: - * Mọi số thuộc cây con trái của nút đó đều nhỏ hơn số ứng với nút đó - * Mọi số thuộc cây con phải của nút đó đều lớn hơn số ứng với nút đó Hàm insert trả về giá trị -1: khi không đủ bộ nhớ. 0: khi gặp nút trùng. 1: khi thực hiện thành công. 4int InsertTree(TREE &T,int k) { if (T!=NULL) { //neu can ca so trung nhau thi bo dong ngay duoi if (T->Info==k) return 0; if (T->Info>k) return InsertTree(T->pL,k); else return InsertTree(T->pR,k); } else { T=(TREE)malloc(sizeof(TNode)); if (T==NULL) return -1; T->Info=k; T->pL=T->pR=NULL; return 1; } } 52.3.2.b. Tạo một cây NPTK: Ta có thể tạo CNPTK bằng cách lặp lại quá trình thêm 1 phần tử vào một cây rỗng void CreateTree(TREE &T) { T=NULL; int k; cout<<"\nIn put n="; cin>>n; for (int i=1;i<=n;i++) { cin>>k; InsertTree(T,k); } } 6Ví dụ tạo cây nhị phân tìm kiếm:  Cho mảng: 60 25 65 19 40 10 15 30 44 50 X=60 ->Root 25L 65>60->R 19L 40>25>19->R 10L 15>10R 30>15>…>25->RL 44>30->R 50>44->R 7Ví dụ chèn nút:  Chèn nút 34 34L 34>21->R 34L->NULL-> chèn  Chèn nút 68 68>62->R 68>66->R 68L 68L->NULL->chèn 62 21 66 17 50 75 70 5834 68 82.3.2.c. Duyệt cây 2.3.2.d. Tìm một phần tử X trong cây int SearchTree(TREE T,int k) { if (T==NULL) return 0; else if (T->Info==k) return 1; if (k>T->Info) return SearchTree(T->pR,k); else return SearchTree(T->pL,k); } 92.3.2.c. Duyệt cây 2.3.2.d. Tìm một phần tử X trong cây TNode* SearchTree1(TREE T,int k) { if (T==NULL) return NULL; else if (T->Info==k) return T; if (k>T->Info) return SearchTree1(T->pR,k); else return SearchTree1(T->pL,k); } 10 2.3.2.e. Huỷ một phần tử có khoá X int DelTree(TREE &T,int k) { if (T==NULL) return 0; if (T->Info>k) return DelTree(T->pL,k); if (T->InfopR,k); else { TNode *p=T; if (T->pR==NULL) T=T->pL; else if (T->pL==NULL) T=T->pR; else { TNode *q=T->pR; SearchStandfor(p,q); } delete(p); } } 11 2.3.2.e. Huỷ một phần tử có khoá X void SearchStandfor(TREE &p,TREE &q) { if (q->pL) SearchStandfor(p,q->pL); else { p->Info=q->Info; p=q; q=q->pR; } } 12 2.3.2.f. Huỷ toàn bộ CNPTK Void removeTree( TREE &T) { if(T) { removeTree(T->pL); removeTree(T->pR); delete(T); } } 13 2.3.2.a. Tìm kiếm trên cây nhị phân tìm kiếm BST  Tìm kiếm trong cây có tồn tại nút có khóa (Key) là SearchData hay không.  Dùng thuật toán tìm kiếm nhị phân vì do đặc điểm của cây nhị phân tìm kiếm thì tại 1 nút nểu Key của nút này khác với SearchData:  Nếu SearchData > Key của nút tìm ở cây con bên phải  Nếu SearchData < Key của nút tìm ở cây con bên trái B1: CurrNode = BSTree B2: IF (CurrNode == NULL or CurrNode->Key == SearchData) Thực hiện BKT B3: IF (CurrNode ->Key > SearchData) // tìm ở cây con bên trái CurrNode = CurrNode->BSTree->BSTLeft B4: ELSE // tìm ở cây con bên phải CurrNode = CurrNode->BSTree->BSTRight B5: Lặp lại B2 BKT: Kết thúc 14 - Minh họa thuật toán:  Giả sử chúng ta cần tìm kiếm nút có thành phần dữ liệu là 30 trên cây nhị phân tìm kiếm sau: SearchData = 30 15 CurNode->Key > SearchData // Tìm kiếm trên cây con trái => CurNode = CurNode->BST_Left 16 CurNode->Key > SearchData // Tìm kiếm trên cây con trái => CurNode = CurNode->BST_Left CurNode->Key = SearchData Thuật toán kết thúc (Tìm thấy) 17 2.3.2.a. Tìm kiếm trên cây nhị phân tìm kiếm BST (tt) Cài đặt thuật toán BSTType BSTSearching (BSTType BSTree, T SearchData) { BSTType CurrNode = BSTree; while (CurrNode !=NULL & CurrNode->Key != SeachData) { if (CurrNode ->Key > SearchData) CurrNode = CurrNode ->BSTLeft; else CurrNode = CurrNode ->BSTRight; } return (CurrNode); } 18 2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm  Giả sử thêm vào 1 nút có thành phần dữ liệu là NewData vào cây nhị phân tìm kiếm sao cho sau khi thêm, cây vẫn là cây nhị phân tìm kiếm.  Bao gồm các thao tác tìm kiếm vị trí thêm và thêm nút vào cây.  Thao tác chỉ thêm được nếu không có hiện tượng trùng khóa, do đó nếu NewData trùng với Key của 1 trong các nút trong cây thì không thực hiện thêm. 19 2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm (tt) B1: NewNode = BinTreeCreateNode(NewData) B2: IF(NewNode == NULL) Thực hiện BKT B3: IF (BSTree == NULL) B3.1: BSTree = NewNode B3.2: Thực hiện BKT B4: CurrNode = BSTree B5: IF (CurrNode == NULL) Thực hiện BKT B6: IF (CurrNode->Key > NewData) B6.1: AddLeft = True B6.2: If (CurrNode->BSTLeft != NULL) CurrNode = CurrNode->BSTLeft B7: IF (CurrNode->Key < NewData) B6.1: AddLeft = False B6.2: If (CurrNode->BSTRight != NULL) CurrNode = CurrNode->BSTRight B8: Lặp lại B5 B9: IF (AddLeft == True) CurrNode = CurrNode->BSTLeft B10: ELSE CurrNode = CurrNode->BSTRight BKT: Kết thúc 20 - Minh họa thuật toán:  Giả sử chúng ta cần thêm vào trong cây nhị phân tìm kiếm 1 nút có thành phần dữ liệu là 55: NewData = 55 21 CurNode->Key > NewData // Thêm vào cây con trái => AddLeft = True CurNode->BST_Left != NULL // Chuyển sang cây con trái =>CurNode = CurNode->BST_Left 22 CurNode->Key < NewData // Thêm vào cây con phải => AddLeft = False CurNode->BST_Right != NULL // Chuyển sang cây con phải => CurNode = CurNode->BST_Right 23 CurNode->Key < NewData // Thêm vào cây con bên phải => AddLeft = False CurNode->BST_Right != NULL // Chuyển sang cây con bên phải => CurNode = CurNode->BST_Right 24 CurNode->Key < NewData // Thêm vào cây con phải => AddLeft = False CurNode->BST_Right == NULL // Thêm NewNode vào thành nút gốc cây con phải của CurNode // (AddLeft = False), thuật toán kết thúc. CurNode->BST_Right = NewNode Kết quả sau khi thêm: 25 2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm (tt) BSTType BSTAddNode (BSTType &BSTree, T NewData) { BSTType NewNode = BinTreeCreateNode(NewData); if (NewNode == NULL) return (NewNode); if (BSTree == NULL) BSTree = NewNode; else { BSTType CurrNode = BSTree; int AddLeft = 1; while (CurrNode->Key != NewData) // khong them neu trung Key { if (CurrNode->Key > NewData) // them o cay con ben trai { AddLeft = 1; if (CurrNode->BSTLeft != NULL) CurrNode = CurrNode->BSTLeft; else break; } else // them o cay con ben phai { AddLeft = 0; if (CurrNode->BSTRight != NULL) CurrNode = CurrNode->BSTRight; else break; } } if (AddLeft == 1) CurrNode->BSTLeft = NewNode; else CurrNode->BSTRight = NewNode; } return (NewNode) } 26 2.3.2.c. Loại bỏ 1 nút trên cây  Hủy mộtnút trên cây nhị phân tìm kiếm cũng phải bảo đảm cho cây sau khi hủy nút đó thìcây vẫn là một cây nhị phân tìm kiếm.  Đây là một thao tác không đơn giản bởi nếukhông cẩn thận chúng ta sẽ biến cây thành một rừng.  Giả sử chúng ta cần hủy nút có thành phần dữ liệu (Key) là DelData ra khỏi cây nhịphân tìm kiếm.  Tìm kiếm địa chỉcủa nút cần hủy là DelNode,  Hủy nút có địa chỉ là DelNode nàynếu tìm thấy (Do vậy thuật toán này còn được gọi là thuật toán tìm kiếm và loại bỏtrên cây). 27 2.3.2.c. Loại bỏ 1 nút trên cây (tt)  Trong quá trình tìm kiếm cần giữ địa chỉ nút cha của nút cần hủy là PrDelNode.  Việc hủy nút có địa chỉ DelNode có thể xảy ra một trong ba trường hợp sau:  DelNode là nút lá  DelNode là nút chỉ có 01 cây con  DelNode là nút có 02 cây con 28 2.3.2.c. Loại bỏ 1 nút trên cây - DelNode là nút lá  Cắt bỏ mối quan hệ cha-con giữa PrDelNode và DelNode bằng cách cho con trỏ  PrDelNode->BST_Left = NULL  hoặc PrDelNode->BST_Right = NULL  Tiến hành hủy (delete) nút có địa chỉ DelNode này. 29 Ví dụ 1: Huỷ nút lá 30 Kết quả sau khi huỷ: 30 2.3.2.c. Loại bỏ 1 nút trên cây - DelNode là nút có 01 cây con  Chuyển mối quan hệ cha con giữa PrDelNode và DelNode thành mối quan hệ cha-con giữa PrDelNode và nút gốc cây con của DelNode rồi tiến hành cắt bỏ mối quan hệ cha-con giữa DelNode và cây con của nó và tiến hành hủy nút có địa chỉ DelNode này.  Trong trường hợp này chúng ta thực hiện các bước: B1: PrDelNode->BST_Left = DelNode->BST_Left B2: DelNode->BST_Left = NULL 31 Ví dụ 2: Huỷ nút 19 có 01 nút gốc con Kết quả sau khi huỷ: 32 2.3.2.c. Loại bỏ 1 nút trên cây - DelNode là nút có 02 cây con Sử dụng phương pháp: Chuyển 02 cây con của DelNode về thành một cây con:  Theo phương pháp này chúng ta sẽ chuyển cây con phải của DelNode về thành cây con phải của cây con có nút gốc là nút phảinhất trong cây con trái của DelNode hoặc  Chuyển cây con trái của DelNode về thành cây con trái củacây con có nút gốc là nút trái nhất trong cây con phải của DelNode  Sau khi chuyển thì DelNode sẽ trở thành nút lá hoặc nút chỉ có 01 cây con và chúng ta hủy DelNode như đối với trường hợp ở trên. 33 Ví dụ 3:Huỷ nút 25 có 02 nút gốc con Chúng ta sẽ chuyển cây con phải của DelNode (DelNode- >BST_Right) về thành cây con phải của cây con có nút gốc là nút phải nhất trong cây con trái của DelNode (nút MRNode) sau đó hủy DelNode 34 B1: MRNode->BST_Right = DelNode->BST_Right B2: DelNode->BST_Right = NULL 35 Kết quả sau khi huỷ: Tiến hành các bước để hủy DelNode: B3: PrDelNode->BST_Left = DelNode->BST_Left B4: DelNode->BST_Left = NULL 36 SỬ DỤNG PHẦN TỬ THẾ MẠNG  Sử dụng phần tử thế mạng là nút phải nhất trong cây con trái của DelNode (MRNode), hoặc là nút trái nhất trong cây con phải của DelNode (MLNode).  Sau khi chuyển toàn bộ nội dung dữ liệu của nút thế mạng cho DelNode (DelNode_Key = MRNode->Key hoặc DelNode->Key = MLNode->Key) thì chúng ta sẽ hủy nút thế mạng như đối với trường hợp c1) và c2) ở trên. 37  Ví dụ: Giả sử cần hủy nút có Key = 25 (DelData = 25). Chúng ta sẽ chọn phần tử thế mạng MLNode là nút trái nhất trong cây con phải của DelNode (trái nhất trong DelNode->BST_Right) để hủy, 38 Chuyển dữ liệu trong MLNode về cho DelNode: DelNode->Key = MLNode->Key 39 Tiến hành hủy MLNode (hủy nút lá): PrMLNode->BST_Left = NULL 40  Kết quả sau khi hủy: 41 2.3.2.d. Hủy toàn bộ cây Thao tác chỉ đơn giản là việc thực hiện nhiều lần thao tác hủy một nút trên cây nhị phân tìm kiếm cho đến khi cây trở thành rỗng. Hàm thực hiện việc hủy tất cả các nút trong cây nhị phân tìm kiếm BSTree. void BSTDelete(BSTType &BSTree) { BSTType DelNode = BSTree; while (BSTDeleteNodeTRS(BSTree, DelNode->Key) == 1) DelNode = BSTree; return; } 42 BÀI TẬP a. Áp dụng giải thuật tạo cây nhị phân tìm kiếm để vẽ cây có 11 phần tử với thứ tự các khóa được nhập vào như sau: 20 17 32 10 3 27 14 40 19 25 35 b. Cho biết kết quả duyệt cây theo thứ tự NLR, LRN. Có nhận xét gì về kết quả duyệt cây theo thứ tự LNR ?