Cây cân bằng

Cấu trúc dữ liệu Cây cân bằng tương đối: Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1 (theo định nghĩa của Adelson-Velskii và Landis). Cây cân bằng tương đối còn gọi là cây AVL (AVL Tree).
Nội dung trích xuất từ tài liệu:
Cây cân bằng 3. Cây cân bằng (Balanced Tree)3.1. Định nghĩa – Cấu trúc dữ liệu Cây cân bằng tương đối:  Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1 (theo định nghĩa của Adelson-Velskii và Landis).  Cây cân bằng tương đối còn gọi là cây AVL (AVL Tree). Cây cân bằng hoàn toàn:  Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì số nút của cây con trái và số nút của cây con phải của nút đó hơn kém nhau không quá 1.  Cây nhị phân cân bằng hoàn toàn là cây nhị phân cân bằng tương đối. 1Ví dụ:AVL Tree AVL Tree 23.1. Định nghĩa – Cấu trúc dữ liệu (tt) Để ghi nhận mức độ cân bằng tại mỗi nút gốc cây con, dùng thêm thành phần Bal trong cấu trúc dữ liệu của mỗi nút.typedef struct BALNode{ T Key; int Bal; BALNode *BALLeft; BALNode *BALRight;}BALOneNode;typedef BALOneNode * BALType; Để quản lý cây cân bằng, chỉ cần quản lý địa chỉ nút gốc của cây BALType BALTree; 33.1. Định nghĩa – Cấu trúc dữ liệu (tt) Giá trị chỉ số cân bằng Bal tại 1 nút gốc của cây con trong cây cân bằng tương đối bằng hiệu số giữa chiều cao cây con trái và chiều cao cây con phải của nút đó. Giá trị chỉ số cân bằng Bal tại 1 nút gốc của cây con trong cây cân bằng hoàn toàn = hiệu số giữa số nút cây con trái và số nút cây con phải của nút đó. Nếu tại mọi nút trong cây nhị phân mà thỏa mãn điều kiện -1 3.2. Các thao tác trên cây cân bằngCác thao tác trên cây cân bằng áp dụng cho cây nhị phân tìm kiếm cân bằng tương đối.3.2.a Thêm 1 nút vào cây cân bằng3.2.b. Hủy một nút khỏi cây cân bằng 3.2.a Thêm 1 nút vào cây cân bằng  Thêm một nút NewNode có thành phần dữ liệu là NewData vào trong cây cân bằng BALTree sao cho sau khi thêm BALTree vẫn là một cây cân bằng.  Để thực hiện điều này cần tìm kiếm vị trí của nút cần thêm là nút con trái hoặc nút con phải của một nút PrNewNode tương tự như trong cây nhị phân tìm kiếm.  Sau khi thêm NewNode vào cây con trái hoặc cây con phải của PrNewNode thì chỉ số cân bằng của các nút từ PrNewNode trở về các nút trước sẽ bị thay đổi dây chuyền và chúng ta phải lần ngược từ 53.2.a Thêm 1 nút vào cây cân bằng Nếu phát hiện tại một nút AncestorNode có sự thay đổi vượt quá phạm vi cho phép (bằng –2 hoặc +2) thì tiến hành cân bằng lại cây ngay tại nút AncestorNode này. Việc cân bằng lại cây tại nút AncestorNode được tiến hành cụ thể theo các trường hợp như sau:Trường hợp 1: Nếu AncestorNode->Bal = -2: AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1) AncRL và AncRR đều có chiều cao là h+1 (AncR->Bal = 0) AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) 63.2.a Thêm 1 nút vào cây cân bằng Nếu phát hiện tại một nút AncestorNode có sự thay đổi vượt quá phạm vi cho phép (bằng –2 hoặc +2) thì chúng ta tiến hành cân bằng lại cây ngay tại nút AncestorNode này. Việc cân bằng lại cây tại nút AncestorNode được tiến hành cụ thể theo các trường hợp như sau:Trường hợp 1: Nếu AncestorNode->Bal = -2: AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1) AncRL và AncRR đều có chiều cao là h+1 (AncR->Bal = 0) AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) 73.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: (lệch phải)Gọi: AncL = AncestorNode->BAL_Left AncR = AncestorNode->BAL_Right=>AncL có chiều cao là h và AncR có chiều cao là h+2 (h 0)=>Có ít nhất 1 cây con của AncR có chiều cao là h+1Gọi: AncRL = AncR->BAL_Left AncRR = AncR->BAL_Right 83.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2:a1) AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1)Để cân bằng lại AncestorNode, thực hiện việc quay đơn cây con phải AncR của nút này lên thành nút gốc; chuyển AncestorNode thành nút con trái của nút gốc và AncestorNode có hai cây con là AncL và AncRL (BAL_Right Rotation).Cây con AncestorNode sau khi quay cây con phải AncR sẽ là một cây cân bằng. 93.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2:a1) AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1) 10 Ví dụ:Việc thêm nút có Key = 50 vào cây nhị phân tìm kiếm cân bằng sau đâysẽ làm cho cây mất cân bằng và chúng ta phải cân bằng lại theo trườnghợp này: trở thành nút gốctrở thành nút phải của 19 11 Thực hiện quay cây con phải của BALTree, cây nhị phân tìm kiếm sau khi quay trở thành cây nhị phân tìm kiếm cân bằng như sau: 123.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2:b1) AncRL và AncRR đều có chiều cao là h+1 (AncR->Bal = 0) 13 Vd 1.b: 40 25 25 44 19 40 ...