›
›

Cấu trúc dữ liệu và giải thuật - Chương 7: Cây (tree)

pdf 131 trang vanle 4540
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Chương 7: Cây (tree)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_7_cay_tree.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chương 7: Cây (tree)

  1. Chương 7: CÂY (Tree)
  2. Nội dung 2  Cấu trúc cây (Tree)  Cấu trúc cây nhị phân (Binary Tree)  Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)  Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree) Chương 7: Cây (Tree)
  3. Tree – Định nghĩa 3  Cây là một tập hợp T các phần tử (gọi là nút của cây) trong đĩ cĩ 1 nút đặc biệt được gọi là gốc, các nút cịn lại được chia thành những tập rời nhau T1, T2 , , Tn theo quan hệ phân cấp trong đĩ Ti cũng là một cây  A tree is a set of one or more nodes T such that:  i. there is a specially designated node called a root  ii. The remaining nodes are partitioned into n disjointed set of nodes T1, T2, ,Tn, each of which is a tree Chương 7: Cây (Tree)
  4. Tree – Ví dụ 4  Sơ đồ tổ chức của một cơng ty Cơng ty A R&D Kinh doanh Tài vụ Sản xuất Nội địa Quốc tế TV CD Amplier Châu âu Mỹ Các nước Chương 7: Cây (Tree)
  5. Tree – Ví dụ 5  Cây thư mục Chương 7: Cây (Tree)
  6. Tree – Ví dụ 6 Chương 7: Cây (Tree)
  7. Tree – Ví dụ Chương 7: Cây (Tree)
  8. Tree – Ví dụ 8  Khơng phải cây Nhận xét: Trong cấu trúc cây khơng tồn tại chu trình Chương 7: Cây (Tree)
  9. Tree - Một số khái niệm cơ bản 9  Bậc của một nút (Degree of a Node of a Tree):  Là số cây con của nút đĩ. Nếu bậc của một nút bằng 0 thì nút đĩ gọi là nút lá (leaf node)  Bậc của một cây (Degree of a Tree):  Là bậc lớn nhất của các nút trong cây. Cây cĩ bậc n thì gọi là cây n-phân  Nút gốc (Root node):  Là nút khơng cĩ nút cha  Nút lá (Leaf node):  Là nút cĩ bậc bằng 0 Chương 7: Cây (Tree)
  10. Tree - Một số khái niệm cơ bản 10  Nút nhánh:  Là nút cĩ bậc khác 0 và khơng phải là gốc  Mức của một nút (Level of a Node):  Mức (gốc (T) ) = 0  Gọi T1, T2, T3, , Tn là các cây con của T0 Mức(T1) = Mức(T2) = = Mức(Tn) = Mức(T0) + 1 Chương 7: Cây (Tree)
  11. Tree – Ví dụ Chương 7: Cây (Tree)
  12. Tree – Ví dụ 12 Nút gốc (root node) Owner Manager Chef Waitress Waiter Cook Helper nút lá (leaf node) Chương 7: Cây (Tree)
  13. Tree – Ví dụ 13 Tree nodes Tree edges Chương 7: Cây (Tree)
  14. Tree – Ví dụ 14 Gốc(root) Nút trong cha và con lá Chương 7: Cây (Tree)
  15. A Tree Has Levels 15 LEVEL 0 Owner Jake Manager Chef Brad Carol Waitress Waiter Cook Helper Joyce Chris Max Len Chương 7: Cây (Tree)
  16. Level One 16 Owner Jake Manager Chef LEVEL 1 Brad Carol Waitress Waiter Cook Helper Joyce Chris Max Len Chương 7: Cây (Tree)
  17. Level Two 17 Owner Jake Manager Chef Brad Carol LEVEL 2 Waitress Waiter Cook Helper Joyce Chris Max Len Chương 7: Cây (Tree)
  18. Định nghĩa Node18 0 là tổ tiên của tất cả các node Gốc Nodes 1-6 là con cháu của node 0 Node 0 Node 1,2,3 con của gốc Node 1 Node 2 Node 3 Node 1 là cha của Nodes 4,5 Node 4 Node 5 Node 6 lá Node 4, 5 là anh em Chương 7: Cây (Tree)
  19. Một số khái niệm cơ bản 19  Độ dài đường đi từ gốc đến nút x: Px = số nhánh cần đi qua kể từ gốc đến x  Độ dài đường đi tổng của cây: PT  PX X T trong đĩ Px là độ dài đường đi từ gốc đến X  Độ dài đường đi trung bình: PI = PT/n (n là số nút trên cây T)  Rừng cây: là tập hợp nhiều cây trong đĩ thứ tự các cây là quan trọng Chương 7: Cây (Tree)
  20. Depth-first Search 20 Chương 7: Cây (Tree)
  21. Breadth-first Search 21 Chương 7: Cây (Tree)
  22. Nội dung 22  Cấu trúc cây (Tree)  Cấu trúc cây nhị phân (Binary Tree)  Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)  Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree) Chương 7: Cây (Tree)
  23. Binary Tree – Định nghĩa 23  Cây nhị phân là cây mà mỗi nút cĩ tối đa 2 cây con Chương 7: Cây (Tree)
  24. Binary Tree – Ví dụ 24 Cây con Cây con trái phải Hình ảnh một cây nhị phân Chương 7: Cây (Tree)
  25. Binary Tree – Ví dụ  Cây lệch trái và cây lệch phải Chương 7: Cây (Tree)
  26. Binary Tree – Ví dụ  A full binary tree Chương 7: Cây (Tree)
  27. Binary Tree – Ví dụ 27  Cây nhị phân dùng để biểu diễn một biểu thức tốn học: Chương 7: Cây (Tree)
  28. Binary Tree – Một số tính chất 28 i  Số nút nằm ở mức i ≤ 2 h-1  Số nút lá ≤ 2 , với h là chiều cao của cây  Chiều cao của cây h ≥ log2N, với N là số nút trong cây h  Số nút trong cây ≤ 2 -1với h là chiều cao của cây Xem them gtrinh trang 142 Chương 7: Cây (Tree)
  29. Binary Tree 29  Cây nhị phân đầy đủ 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 k=3 2k+1, 2k+2 Chương 7: Cây (Tree)
  30. Binary Tree - Biểu diễn  In general, any binary tree can be represented using an array, but ? Chương 7: Cây (Tree)
  31. Binary Tree - Biểu diễn 31  Sử dụng một biến động để lưu trữ các thơng tin của một nút:  Thơng tin lưu trữ tại nút  Địa chỉ nút gốc của cây con trái trong bộ nhớ  Địa chỉ nút gốc của cây con phải trong bộ nhớ  Khai báo cấu trúc cây nhị phân: struct TNode { DataType data; TNode *pLeft, *pRight; }; typedef TNode* Tree;  Để quản lý cây nhị phân chỉ cần quản lý địa chỉ nút gốc: Tree root; Chương 7: Cây (Tree)
  32. Binary Tree - Biểu diễn 32 a b c d e f g h i j k Chương 7: Cây (Tree)
  33. Binary Tree - Duyệt cây nhị phân 33  Cĩ 3 kiểu duyệt chính cĩ thể áp dụng trên cây nhị phân:  Duyệt theo thứ tự trước - preorder (Node-Left-Right: NLR)  Duyệt theo thứ tự giữa - inorder (Left-Node-Right: LNR)  Duyệt theo thứ tự sau - postorder (Left-Right-Node: LRN)  Tên của 3 kiểu duyệt này được đặt dựa trên trình tự của việc thăm nút gốc so với việc thăm 2 cây con Chương 7: Cây (Tree)
  34. Binary Tree - Duyệt cây nhị phân 34  Duyệt theo thứ tự trước NLR (Node-Left-Right)  Kiểu duyệt này trước tiên thăm nút gốc sau đĩ thăm các nút của cây con trái rồi đến cây con phải  Thủ tục duyệt cĩ thể trình bày đơn giản như sau: void NLR (Tree t) { if (t != NULL) { // Xử lý t tương ứng theo nhu cầu NLR(t->pLeft); NLR(t->pRight); } } Chương 7: Cây (Tree)
  35. Binary Tree - Duyệt cây nhị phân NLR 35 A B C D E F G H I J K L M N O P Kết quả: A B D H I N E J O K C F L P G M Chương 7: Cây (Tree)
  36. Binary Tree - Duyệt cây nhị phân 36  Duyệt theo thứ tự giữa LNR (Left-Node-Right)  Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đĩ thăm nút gốc rồi đến cây con phải  Thủ tục duyệt cĩ thể trình bày đơn giản như sau: void LNR(Tree t) { if (t != NULL) { LNR(t->pLeft); //Xử lý nút t theo nhu cầu LNR(t->pRight); } } Chương 7: Cây (Tree)
  37. Binary Tree - Duyệt cây nhị phân LNR 37 A B C D E F G H I J K L M N O P Kết quả: H D N I B J O E K A F P L C M G Chương 7: Cây (Tree)
  38. Binary Tree - Duyệt cây nhị phân 38  Duyệt theo thứ tự giữa LRN (Left-Right-Node)  Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đĩ thăm đến cây con phải rồi cuối cùng mới thăm nút gốc  Thủ tục duyệt cĩ thể trình bày đơn giản như sau: void LRN(Tree t) { if (t != NULL) { LRN(t->pLeft); LRN(t->pRight); // Xử lý tương ứng t theo nhu cầu } } Chương 7: Cây (Tree)
  39. Binary Tree - Duyệt cây nhị phân LRN 39 A B C D E F G H I J K L M N O P Kết quả: H N I D O J K E B P L F M G C A Chương 7: Cây (Tree)
  40. Binary Tree - Duyệt cây nhị phân LRN 40  Một ví dụ quen thuộc trong tin học về ứng dụng của duyệt theo thứ tự sau là việc xác định tồng kích thước của một thư mục trên đĩa Chương 7: Cây (Tree)
  41. Binary Tree - Duyệt cây nhị phân LRN 41  Tính tốn giá trị của biểu thức dựa trên cây biểu thức (3 + 1) 3/(9 – 5 + 2) – (3 (7 – 4) + 6) = –13 Chương 7: Cây (Tree)
  42. Một cách biểu diễn cây nhị phân khác 42  Đơi khi, khi định nghĩa cây nhị phân, người ta quan tâm đến cả quan hệ 2 chiều cha con chứ khơng chỉ một chiều như định nghĩa ở phần trên.  Lúc đĩ, cấu trúc cây nhị phân cĩ thể định nghĩa lại như sau: typedef struct tagTNode { DataType Key; struct tagTNode* pParent; struct tagTNode* pLeft; struct tagTNode* pRight; }TNODE; typedef TNODE *TREE; Chương 7: Cây (Tree)
  43. Một cách biểu diễn cây nhị phân khác 43 Chương 7: Cây (Tree)
  44. Mộ số thao tác trên cây 44  Đếm số node  Đếm số node lá  Tính chiều cao Chương 7: Cây (Tree)
  45. Đếm số node 45 Chương 7: Cây (Tree)
  46. Đếm số node 46  Số node (EmptyTree) = 0  Số node (Tree) = 1 + Số node (Tree.Left) + Số node (Tree.Right) Chương 7: Cây (Tree)
  47. Đếm số node lá 47 Chương 7: Cây (Tree)
  48. Đếm số node lá 48 Số nút lá (EmptyTree) = 0 Số nút lá(RootOnly) = 1 Số nút lá(Tree) = Số nút lá (Tree.Left) + Số nút lá (Tree.Right) Chương 7: Cây (Tree)
  49. Tính chiều cao 49 Chương 7: Cây (Tree)
  50. Tính chiều cao 50 Height(Tree) = 1 + maximum(Height(Tree.Left), Height(Tree.Right)) Depth(EmptyTree) = -1 Chương 7: Cây (Tree)
  51. Nội dung 51  Cấu trúc cây (Tree)  Cấu trúc cây nhị phân (Binary Tree)  Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)  Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree) Chương 7: Cây (Tree)
  52. Binary Search Tree  Trong chương 6, chúng ta đã làm quen với một số cấu trúc dữ liệu động. Các cấu trúc này cĩ sự mềm dẻo nhưng lại bị hạn chế trong việc tìm kiếm thơng tin trên chúng (chỉ cĩ thể tìm kiếm tuần tự)  Nhu cầu tìm kiếm là rất quan trọng. Vì lý do này, người ta đã đưa ra cấu trúc cây để thỏa mãn nhu cầu trên  Tuy nhiên, nếu chỉ với cấu trúc cây nhị phân đã định nghĩa ở trên, việc tìm kiếm cịn rất mơ hồ  Cần cĩ thêm một số ràng buộc để cấu trúc cây trở nên chặt chẽ, dễ dùng hơn  Một cấu trúc như vậy chính là cây nhị phân tìm kiếm Chương 7: Cây (Tree)
  53. Binary Search Tree - Định nghĩa 53  Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đĩ tại mỗi nút, khĩa 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 khĩa của tất cả các nút thuộc cây con phải  Nhờ ràng buộc về khĩa trên CNPTK, việc tìm kiếm trở nên cĩ định hướng  Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N  Trong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét CNPTK Chương 7: Cây (Tree)
  54. Binary Search Tree – Ví dụ 54 44 18 88 13 37 59 108 15 23 40 55 71 Chương 7: Cây (Tree)
  55. Binary Search Tree – Ví dụ 55 Chương 7: Cây (Tree)
  56. Binary Search Tree – Ví dụ 56 Chương 7: Cây (Tree)
  57. Cây nhị phân và tìm kiếm nhị phân 57 34 41 56 63 72 89 95 0 1 2 3 4 5 6 Chương 7: Cây (Tree)
  58. Cây nhị phân và tìm kiếm nhị phân 58 34 41 56 63 72 89 95 0 1 2 3 4 5 6 34 41 56 72 89 95 0 1 2 4 5 6 Chương 7: Cây (Tree)
  59. Cây nhị phân và tìm kiếm nhị phân 59 34 41 56 63 72 89 95 0 1 2 3 4 5 6 34 41 56 72 89 95 0 1 2 4 5 6 34 56 72 95 0 2 4 6 Chương 7: Cây (Tree)
  60. Binary Search Tree (BST) 60 63 41 89 34 56 72 95 Chương 7: Cây (Tree)
  61. Binary Search Tree – Biểu diễn 61  Cấu trúc dữ liệu của CNPTK là cấu trúc dữ liệu biểu diễn cây nhị phân nĩi chung (???)  Thao tác duyệt cây trên CNPTK hồn tồn giống như trên cây nhị phân (???)  Chú ý: khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khĩa Chương 7: Cây (Tree)
  62. Binary Search Tree – Duyệt cây 62 Duyệt giữa trên CNPTK 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 Duyệt inorder: 1 3 5 6 10 12 13 18 20 25 29 32 35 37 41 50 Chương 7: Cây (Tree)
  63. Binary Search Tree – Duyệt cây 63 Duyệt sau trên CNPTK 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 Duyệt postorder: Chương 7: Cây (Tree)
  64. Binary Search Tree – Duyệt cây 64 Duyệt trước trên CNPTK 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 Duyệt preorder: Chương 7: Cây (Tree)
  65. Binary Search Tree – Tìm kiếm 65 Tìm kiếm trên CNPTK 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 KhácGiốngNode nhau gốcnhau nhỏlớn hơnhơn Số node duyệt: 5 Tìm kiếm 13 Tìm thấy Số lần so sánh: 9 Chương 7: Cây (Tree)
  66. Binary Search Tree – Tìm kiếm 66 Tìm kiếm trên CNPTK 25 10 37 3 18 29 50 1 6 12 20 35 41 5 13 32 NodeKhác nhaugốc nhỏlớn hơnhơn Số node duyệt: 5 Tìm kiếm 14 Khơng tìm thấy Số lần so sánh: 10 Chương 7: Cây (Tree)
  67. Binary Search Tree – Tìm kiếm 67  Tìm một phần tử x trong CNPTK (dùng đệ quy): TNode* searchNode(Tree T, DataType X) { if (T) { if(T->Key == X) return T; if(T->Key > X) return searchNode(T->pLeft, X); return searchNode(T->pRight, X); } return NULL; } Chương 7: Cây (Tree)
  68. Binary Search Tree – Tìm kiếm 68  Tìm một phần tử x trong CNPTK (dùng vịng lặp): TNode * searchNode(Tree T, DataType x) { TNode *p = T; while (p != NULL) { if(x == p->Key) return p; else if(x Key) p = p->pLeft; else p = p->pRight; } return NULL; } Chương 7: Cây (Tree)
  69. Binary Search Tree – Tìm kiếm 69  Nhận xét:  Số lần so sánh tối đa phải thực hiện để tìm phần tử X là h, với h là chiều cao của cây  Như vậy thao tác tìm kiếm trên CNPTK cĩ n nút tốn chi phí trung bình khoảng O(log2n) Chương 7: Cây (Tree)
  70. Binary Search Tree – Thêm 70  Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTK  Ta cĩ thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút ngồi sẽ là tiện lợi nhất do ta cĩ thể thực hiện quá trình tương tự thao tác tìm kiếm  Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm  Hàm insert trả về giá trị: –1 khi khơng đủ bộ nhớ 0 khi gặp nút cũ 1 khi thêm thành cơng Chương 7: Cây (Tree)
  71. Binary Search Tree – Thêm 71  Thêm một phần tử vào cây int insertNode (Tree &T, DataType X) { if (T) { if(T->data == X) return 0; if(T->data > X) return insertNode(T->pLeft, X); else return insertNode(T->pRight, X); } T = new TNode; if (T == NULL) return -1; T->data = X; T->pLeft = T->pRight = NULL; return 1; } Chương 7: Cây (Tree)
  72. Binary Search Tree – Thêm 72  Ví dụ tạo cây với dãy: 4, 6, 1, 2, 5, 7, 3 4 1 6 2 5 7 3 Chương 7: Cây (Tree)
  73. Binary Search Tree – Thêm 73  Ví dụ tạo cây với dãy: 30, 12, 17, 49, 22, 65, 51, 56, 70, 68 30 12 49 17 65 22 51 70 56 68 Chương 7: Cây (Tree)
  74. Binary Search Tree – Hủy một phần tử cĩ khĩa X 74  Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK  Cĩ 3 trường hợp khi hủy nút X cĩ thể xảy ra:  X là nút lá  X chỉ cĩ 1 con (trái hoặc phải)  X cĩ đủ cả 2 con Chương 7: Cây (Tree)
  75. Binary Search Tree – Hủy một phần tử cĩ khĩa X 75  Trường hợp 1: X là nút lá  Chỉ đơn giản hủy X vì nĩ khơng mĩc nối đến phần tử nào khác T/h 1: hủy X=40 44 18 88 13 37 59 108 15 23 40 55 71 Chương 7: Cây (Tree)
  76. Binary Search Tree – Hủy một phần tử cĩ khĩa X 76  Trường hợp 2: X chỉ cĩ 1 con (trái hoặc phải)  Trước khi hủy X ta mĩc nối cha của X với con duy nhất của nĩ 44 T/h 2: hủy X=37 18 88 13 37 59 108 15 23 55 71 Chương 7: Cây (Tree)
  77. Binary Search Tree – Hủy một phần tử cĩ khĩa X 77  Trường hợp 3: X cĩ đủ 2 con:  Khơng thể hủy trực tiếp do X cĩ đủ 2 con  Hủy gián tiếp:  Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này cĩ tối đa một con  Thơng tin lưu tại Y sẽ được chuyển lên lưu tại X  Sau đĩ, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu  Vấn đề: chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK Chương 7: Cây (Tree)
  78. Binary Search Tree – Hủy một phần tử cĩ khĩa X 78  Trường hợp 3: X cĩ đủ 2 con:  Cĩ 2 phần tử thỏa mãn yêu cầu:  Phần tử trái nhất trên cây con phải  Phần tử phải nhất trên cây con trái  Việc chọn lựa phần tử nào là phần tử thế mạng hồn tồn phụ thuộc vào ý thích của người lập trình  Ở đây, ta sẽ chọn phần tử phải nhất trên cây con trái làm phân tử thế mạng Chương 7: Cây (Tree)
  79. Binary Search Tree – Hủy một phần tử cĩ khĩa X 79  Trường hợp 3: X cĩ đủ 2 con:  Khi hủy phần tử X=18 ra khỏi cây, phần tử 23 là phần tử thế mạng: T/h 3: hủy X=18 44 18 88 13 23 37 59 108 15 23 40 55 71 30 Chương 7: Cây (Tree)
  80. Binary Search Tree – Hủy một phần tử cĩ khĩa X 80  Trường hợp 3: X cĩ đủ 2 con:  Hàm delNode trả về giá trị 1, 0 khi hủy thành cơng hoặc khơng cĩ X trong cây: int delNode(Tree &T, DataType X)  Hàm searchStandFor tìm phần tử thế mạng cho nút p void searchStandFor(Tree &p, Tree &q) Chương 7: Cây (Tree)
  81. Binary Search Tree – Hủy một phần tử cĩ khĩa X 81 int delNode(Tree &T, DataType X) { if (T == NULL) return 0; if (T->data > X) return delNode(T->pLeft, X); if (T->data pRight, X); TNode* p = T; if (T->pLeft == NULL) T = T->pRight; else if (T->pRight == NULL) T = T->pLeft; else // T cĩ đủ 2 con searchStandFor(p, T->pRight); delete p; } Chương 7: Cây (Tree)
  82. Binary Search Tree – Hủy một phần tử cĩ khĩa X 82  Tìm phần tử thế mạng void searchStandFor(Tree &p, Tree &q) { if (q->pLeft) searchStandFor(p, q->pLeft); else { p->data = q->data; p = q; q = q->pRight; } } Chương 7: Cây (Tree)
  83. Binary Search Tree – Hủy một phần tử cĩ khĩa X 83  Ví dụ xĩa 51: Chương 7: Cây (Tree)
  84. Binary Search Tree – Hủy một phần tử cĩ khĩa X 84  Ví dụ xĩa 83: Chương 7: Cây (Tree)
  85. Binary Search Tree – Hủy một phần tử cĩ khĩa X 85  Ví dụ xĩa 36: Chương 7: Cây (Tree)
  86. Binary Search Tree – Hủy một phần tử cĩ khĩa X 86  Xĩa nút gốc (2 lần): Chương 7: Cây (Tree)
  87. Binary Search Tree – Hủy một phần tử cĩ khĩa X 87  Ví dụ xĩa 15: Chương 7: Cây (Tree)
  88. Binary Search Tree – Hủy một phần tử cĩ khĩa X 88  42 là thế mạng Chương 7: Cây (Tree)
  89. Binary Search Tree – Hủy một phần tử cĩ khĩa X 89 Chương 7: Cây (Tree)
  90. Binary Search Tree – Hủy một phần tử cĩ khĩa X 90  Kết quả xố lần 1: Chương 7: Cây (Tree)
  91. Binary Search Tree – Hủy một phần tử cĩ khĩa X 91  Ví dụ xĩa 42 Chương 7: Cây (Tree)
  92. Binary Search Tree – Hủy một phần tử cĩ khĩa X 92 Chương 7: Cây (Tree)
  93. Binary Search Tree – Hủy một phần tử cĩ khĩa X 93 Chương 7: Cây (Tree)
  94. Binary Search Tree – Hủy một phần tử cĩ khĩa X 94  Xĩa 15, sau đĩ 42: Chương 7: Cây (Tree)
  95. Binary Search Tree – Hủy tồn bộ cây 95  Việc tồn bộ cây cĩ thể được thực hiện thơng qua thao tác duyệt cây theo thứ tự sau. Nghĩa là ta sẽ hủy cây con trái, cây con phải rồi mới hủy nút gốc void removeTree(Tree &T) { if(T) { removeTree(T->pLeft); removeTree(T->pRight); delete(T); } } Chương 7: Cây (Tree)
  96. Binary Search Tree 96  Nhận xét:  Tất cả các thao tác searchNode, insertNode, delNode đều cĩ độ phức tạp trung bình O(h), với h là chiều cao của cây  Trong trong trường hợp tốt nhất, CNPTK cĩ n nút sẽ cĩ độ cao h = log2(n). Chi phí tìm kiếm khi đĩ sẽ tương đương tìm kiếm nhị phân trên mảng cĩ thứ tự  Trong trường hợp xấu nhất, cây cĩ thể bị suy biến thành 1 danh sách liên kết (khi mà mỗi nút đều chỉ cĩ 1 con trừ nút lá). Lúc đĩ các thao tác trên sẽ cĩ độ phức tạp O(n)  Vì vậy cần cĩ cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n) Chương 7: Cây (Tree)
  97. Binary Search Tree 97  1,2,3,4,5 1 2 3 4 5 Chương 7: Cây (Tree)
  98. Nội dung 98  Cấu trúc cây (Tree)  Cấu trúc cây nhị phân (Binary Tree)  Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)  Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree) Chương 7: Cây (Tree)
  99. AVL Tree - Định nghĩa 99  Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nĩ độ cao của cây con trái và của cây con phải chênh lệch khơng quá một. Chương 7: Cây (Tree)
  100. AVL Tree – Ví dụ 100 44 23 88 13 37 59 108 15 30 40 55 71 Chương 7: Cây (Tree)
  101. AVL Tree 101  Lịch sử cây cân bằng (AVL Tree):  AVL là tên viết tắt của các tác giả người Nga đã đưa ra định nghĩa của cây cân bằng Adelson-Velskii và Landis (1962)  Từ cây AVL, người ta đã phát triển thêm nhiều loại CTDL hữu dụng khác như cây đỏ-đen (Red-Black Tree), B-Tree,  Cây AVL cĩ chiều cao O(log2(n)) Chương 7: Cây (Tree)
  102. AVL Tree 102  Chỉ số cân bằng của một nút:  Định nghĩa: Chỉ số cân bằng của một nút là hiệu của chiều cao cây con phải và cây con trái của nĩ.  Đối với một cây cân bằng, chỉ số cân bằng (CSCB) của mỗi nút chỉ cĩ thể mang một trong ba giá trị sau đây:  CSCB(p) = 0 Độ cao cây trái (p) = Độ cao cây phải (p)  CSCB(p) = 1 Độ cao cây trái (p) Độ cao cây phải (p)  Để tiện trong trình bày, chúng ta sẽ ký hiệu như sau: p- >balFactor = CSCB(p);  Độ cao cây trái (p) ký hiệu là hL  Độ cao cây phải(p) ký hiệu là hR Chương 7: Cây (Tree)
  103. AVL Tree – Biểu diễn 103 #define LH -1 /* Cây con trái cao hơn */ #define EH 0 /* Hai cây con bằng nhau */ #define RH 1 /* Cây con phải cao hơn */ struct AVLNode{ char balFactor; // Chỉ số cân bằng DataType data; tagAVLNode* pLeft; tagAVLNode* pRight; }; typedef AVLNode* AVLTree; Chương 7: Cây (Tree)
  104. AVL Tree – Biểu diễn 104  Trường hợp thêm hay hủy một phần tử trên cây cĩ thể làm cây tăng hay giảm chiều cao, khi đĩ phải cân bằng lại cây  Việc cân bằng lại một cây sẽ phải thực hiện sao cho chỉ ảnh hưởng tối thiểu đến cây nhằm giảm thiểu chi phí cân bằng  Các thao tác đặc trưng của cây AVL:  Thêm một phần tử vào cây AVL  Hủy một phần tử trên cây AVL  Cân bằng lại một cây vừa bị mất cân bằng Chương 7: Cây (Tree)
  105. AVL Tree 105  Các trường hợp mất cân bằng:  Ta sẽ khơng khảo sát tính cân bằng của 1 cây nhị phân bất kỳ mà chỉ quan tâm đến các khả năng mất cân bằng xảy ra khi thêm hoặc hủy một nút trên cây AVL  Như vậy, khi mất cân bằng, độ lệch chiều cao giữa 2 cây con sẽ là 2  Cĩ 6 khả năng sau:  Trường hợp 1 - Cây T lệch về bên trái : 3 khả năng  Trường hợp 2 - Cây T lệch về bên phải: 3 khả năng Chương 7: Cây (Tree)
  106. AVL Tree 106  Trường hợp 1: cây T lệch về bên trái T T L T1 L T1 h-1 h-1 R R h-1 h h-1 h L1 R1 L1 R1 T L T1 h-1 R h h L1 L1 Chương 7: Cây (Tree)
  107. AVL Tree 107  Trường hợp 2: cây T lệch về bên phải T T R T1 R T1 h-1 h-1 L L h-1 h-1 h h L1 R1 L1 R1 T R T1 h-1 L h h L1 R1 Chương 7: Cây (Tree)
  108. AVL Tree 108  Các trường hợp mất cân bằng:  Các trường hợp lệch về bên phải hồn tồn đối xứng với các trường hợp lệch về bên trái.  Vì vậy, chỉ cần khảo sát trường hợp lệch về bên trái.  Trong 3 trường hợp lệch về bên trái, trường hợp T1 lệch phải là phức tạp nhất. Các trường hợp cịn lại giải quyết rất đơn giản. Chương 7: Cây (Tree)
  109. AVL Tree - Cân bằng lại cây AVL 109  T/h 1.1: cây T1 lệch về bên trái. Ta thực hiện phép quay đơn Left-Left T T1 L T1 T h-1 h R L1 h-1 h h-1 h-1 L1 R1 R1 R Chương 7: Cây (Tree)
  110. AVL Tree - Cân bằng lại cây AVL 110  T/h 1.2: cây T1 khơng lệch. Ta thực hiện phép quay đơn Left- Left T T1 L T1 T h-1 h R L1 h h h h-1 L1 R1 R1 R Chương 7: Cây (Tree)
  111. AVL Tree - Cân bằng lại cây AVL 111  T/h 1.3: cây T1 lệch về bên phải. Ta thực hiện phép quay kép Left-Right  Do T1 lệch về bên phải ta khơng thể áp dụng phép quay đơn đã áp dụng trong 2 trường hợp trên vì khi đĩ cây T sẽ chuyển từ trạng thái mất cân bằng do lệch trái thành mất cân bằng do lệch phải ? cần áp dụng cách khác Chương 7: Cây (Tree)
  112. T T 112 L T1 T1 h-1 h-1 R R T2 h-1 h h-1 L1 R1 L1 R1 L2 R2 T2 T1 T h-1 h-1 L1 L2 R2 R Chương 7: Cây (Tree)
  113. AVL Tree - Cân bằng lại cây AVL 113  Lưu ý:  Trước khi cân bằng cây T cĩ chiều cao h+2 trong cả 3 trường hợp 1.1, 1.2 và 1.3  Sau khi cân bằng:  Trường hợp 1.1 và 1.3 cây cĩ chiều cao h+1  Trường hợp 1.2 cây vẫn cĩ chiều cao h+2. Đây là trường hợp duy nhất sau khi cân bằng nút T cũ cĩ chỉ số cân bằng ≠ 0  Thao tác cân bằng lại trong tất cả các trường hợp đều cĩ độ phức tạp O(1) Chương 7: Cây (Tree)
  114. AVL Tree - Cân bằng lại cây AVL 114  T/h 1.1: cây T1 lệch về bên trái. Ta thực hiện phép quay đơn Left-Left T T1 L T1 T h-1 h R L1 h-1 h h-1 h-1 L1 R1 R1 R Chương 7: Cây (Tree)
  115. AVL Tree - Cân bằng lại cây AVL 115  Quay đơn Left-Left: void rotateLL(AVLTree &T) //quay đơn Left-Left { AVLNode* T1 = T->pLeft; T->pLeft = T1->pRight; T1->pRight = T; switch(T1->balFactor) { case LH: T->balFactor = EH; T1->balFactor = EH; break; case EH: T->balFactor = LH; T1->balFactor = RH; break; } T = T1; } Chương 7: Cây (Tree)
  116. AVL Tree - Cân bằng lại cây AVL 116  Quay đơn Right-Right: void rotateRR (AVLTree &T)//quay đơn Right-Right { AVLNode* T1 = T->pRight; T->pRight = T1->pLeft; T1->pLeft = T; switch(T1->balFactor) { case RH: T->balFactor = EH; T1->balFactor= EH; break; case EH: T->balFactor = RH; T1->balFactor= LH; break; } T = T1; } Chương 7: Cây (Tree)
  117. AVL Tree - Cân bằng lại cây AVL 117  Quay kép Left-Right: void rotateLR(AVLTree &T)//quay kép Left-Right { AVLNode* T1 = T->pLeft; AVLNode* T2 = T1->pRight; T->pLeft = T2->pRight; T2->pRight = T; T1->pRight = T2->pLeft; T2->pLeft = T1; switch(T2->balFactor) { case LH: T->balFactor = RH; T1->balFactor = EH; break; case EH: T->balFactor = EH; T1->balFactor = EH; break; case RH: T->balFactor = EH; T1->balFactor = LH; break; } T2->balFactor = EH; T = T2; } Chương 7: Cây (Tree)
  118. AVL Tree - Cân bằng lại cây AVL 118  Quay kép Right-Left void rotateRL(AVLTree &T) //quay kép Right-Left { AVLNode* T1 = T->pRight; AVLNode* T2 = T1->pLeft; T->pRight = T2->pLeft; T2->pLeft = T; T1->pLeft = T2->pRight; T2->pRight = T1; switch(T2->balFactor) { case RH: T->balFactor = LH; T1->balFactor = EH; break; case EH: T->balFactor = EH; T1->balFactor = EH; break; case LH: T->balFactor = EH; T1->balFactor = RH; break; } T2->balFactor = EH; T = T2; } Chương 7: Cây (Tree)
  119. AVL Tree - Cân bằng lại cây AVL 119  Cân bằng khi cây bị lêch về bên trái: int balanceLeft(AVLTree &T) //Cân bằng khi cây bị lêch về bên trái { AVLNode* T1 = T->pLeft; switch(T1->balFactor) { case LH: rotateLL(T); return 2; case EH: rotateLL(T); return 1; case RH: rotateLR(T); return 2; } return 0; } Chương 7: Cây (Tree)
  120. AVL Tree - Cân bằng lại cây AVL 120  Cân bằng khi cây bị lêch về bên phải int balanceRight(AVLTree &T ) //Cân bằng khi cây bị lêch về bên phải { AVLNode* T1 = T->pRight; switch(T1->balFactor) { case LH: rotateRL(T); return 2; case EH: rotateRR(T); return 1; case RH: rotateRR(T); return 2; } return 0; } Chương 7: Cây (Tree)
  121. AVL Tree - Thêm một phần tử trên cây AVL 121  Việc thêm một phần tử vào cây AVL diễn ra tương tự như trên CNPTK  Sau khi thêm xong, nếu chiều cao của cây thay đổi, từ vị trí thêm vào, ta phải lần ngược lên gốc để kiểm tra xem cĩ nút nào bị mất cân bằng khơng. Nếu cĩ, ta phải cân bằng lại ở nút này  Việc cân bằng lại chỉ cần thực hiện 1 lần tại nơi mất cân bằng  Hàm insertNode trả về giá trị –1, 0, 1 khi khơng đủ bộ nhớ, gặp nút cũ hay thành cơng. Nếu sau khi thêm, chiều cao cây bị tăng, giá trị 2 sẽ được trả về int insertNode(AVLTree &T, DataType X) Chương 7: Cây (Tree)
  122. AVL Tree - Thêm một phần tử trên cây AVL 122 int insertNode(AVLTree &T, DataType X) { int res; if (T) { if (T->key == X) return 0; //đã cĩ if (T->key > X) { res = insertNode(T->pLeft, X); if(res balFactor) { case RH: T->balFactor = EH; return 1; case EH: T->balFactor = LH; return 2; case LH: balanceLeft(T); return 1; } } } insertNode2 Chương 7: Cây (Tree)
  123. AVL Tree - Thêm một phần tử trên cây AVL 123 int insertNode(AVLTree &T, DataType X) { else // T->key pRight, X); if(res balFactor) { case LH: T->balFactor = EH; return 1; case EH: T->balFactor = RH; return 2; case RH: balanceRight(T); return 1; } } } insertNode3 Chương 7: Cây (Tree)
  124. AVL Tree - Thêm một phần tử trên cây AVL 124 int insertNode(AVLTree &T, DataType X) { T = new TNode; if(T == NULL) return -1; //thiếu bộ nhớ T->key = X; T->balFactor = EH; T->pLeft = T->pRight = NULL; return 2; // thành cơng, chiều cao tăng } Chương 7: Cây (Tree)
  125. AVL Tree - Hủy một phần tử trên cây AVL 125  Cũng giống như thao tác thêm một nút, việc hủy một phần tử X ra khỏi cây AVL thực hiện giống như trên CNPTK  Sau khi hủy, nếu tính cân bằng của cây bị vi phạm ta sẽ thực hiện việc cân bằng lại  Tuy nhiên việc cân bằng lại trong thao tác hủy sẽ phức tạp hơn nhiều do cĩ thể xảy ra phản ứng dây chuyền  Hàm delNode trả về giá trị 1, 0 khi hủy thành cơng hoặc khơng cĩ X trong cây. Nếu sau khi hủy, chiều cao cây bị giảm, giá trị 2 sẽ được trả về: int delNode(AVLTree &T, DataType X) Chương 7: Cây (Tree)
  126. AVL Tree - Hủy một phần tử trên cây AVL 126 int delNode(AVLTree &T, DataType X) { int res; if(T==NULL) return 0; if(T->key > X) { res = delNode (T->pLeft, X); if(res balFactor) { case LH: T->balFactor = EH; return 2; case EH: T->balFactor = RH; return 1; case RH: return balanceRight(T); } } // if(T->key > X) } delNode2 Chương 7: Cây (Tree)
  127. AVL Tree - Hủy một phần tử trên cây AVL 127 int delNode(AVLTree &T, DataType X) { if(T->key pRight, X); if(res balFactor) { case RH: T->balFactor = EH; return 2; case EH: T->balFactor = LH; return 1; case LH: return balanceLeft(T); } } // if(T->key < X) } delNode3 Chương 7: Cây (Tree)
  128. AVL Tree - Hủy một phần tử trên cây AVL 128 int delNode(AVLTree &T, DataType X) { else //T->key == X { AVLNode* p = T; if(T->pLeft == NULL) { T = T->pRight; res = 2; } else if(T->pRight == NULL) { T = T->pLeft; res = 2; } else //T cĩ đủ cả 2 con { res = searchStandFor(p,T->pRight); if(res balFactor) { case RH: T->balFactor = EH; return 2; case EH: T->balFactor = LH; return 1; case LH: return balanceLeft(T); } } delete p; return res; } } Chương 7: Cây (Tree)
  129. AVL Tree - Hủy một phần tử trên cây AVL 129 int searchStandFor(AVLTree &p, AVLTree &q) //Tìm phần tử thế mạng { int res; if(q->pLeft) { res = searchStandFor(p, q->pLeft); if(res balFactor) { case LH: q->balFactor = EH; return 2; case EH: q->balFactor = RH; return 1; case RH: return balanceRight(T); } } else { p->key = q->key; p = q; q = q->pRight; return 2; } } Chương 7: Cây (Tree)
  130. AVL Tree 130  Nhận xét:  Thao tác thêm một nút cĩ độ phức tạp O(1)  Thao tác hủy một nút cĩ độ phức tạp O(h)  Với cây cân bằng trung bình 2 lần thêm vào cây thì cần một lần cân bằng lại; 5 lần hủy thì cần một lần cân bằng lại Chương 7: Cây (Tree)
  131. AVL Tree 131  Nhận xét:  Việc hủy 1 nút cĩ thể phải cân bằng dây chuyền các nút từ gốc cho đên phần tử bị hủy trong khi thêm vào chỉ cần 1 lần cân bằng cục bộ  Độ dài đường tìm kiếm trung bình trong cây cân bằng gần bằng cây cân bằng hồn tồn log2n, nhưng việc cân bằng lại đơn giản hơn nhiều  Một cây cân bằng khơng bao giờ cao hơn 45% cây cân bằng hồn tồn tương ứng dù số nút trên cây là bao nhiêu Chương 7: Cây (Tree)