Cây cân bằng (Balanced Tree)

13. 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. 2Ví dụ: AVL Tree AVL Tree 33.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; 43.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 <= Bal <= 1 thì cây là cây cân bằng. Phạm vi từ -1  1 là phạm vi cho phép của chỉ số cân bằng Bal  Nếu Bal = 0: cây con trái & cây con phải đều nhau  Nếu Bal = -1: cây con trái nhỏ hơn cây con phải (lệch phải)  Nếu Bal = +1: cây con trái nhỏ lớn cây con phải (lệch trái) 53.2. Các thao tác trên cây cân bằng Cá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ằng 3.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ừ 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ì 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 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) 83.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+1 Gọi: AncRL = AncR->BAL_Left AncRR = AncR->BAL_Right 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) Để 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. 10 3.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) 11 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 đây sẽ 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ường hợp này: trở thành nút phải của 19 trở thành nút gốc 12  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: 13 3.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) 14  Vd 1.b: 19 25 40 4435 19 25 40 44 32 50 32 50 35 15 3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: c1) AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) Để cân bằng lại AncestorNode thực hiện việc quay kép: quay cây con trái AncRL và quay cây con phải AncR (Double Rotation). Việc quay được tiến hành: Gọi: AncRLL = AncRL->BAL_Left AncRLR = AncRL->BAL_Right => AncRLL và AncRLR có chiều cao tối đa là h => Cây con có nút gốc AncestorNode có thể ở vào một trong ba dạng:  AncRLL có chiều cao là h và AncRLR có chiều cao là h-1 (AncRL->Bal =1; h >= 1)  AncRLL có chiều cao là h-1 và AncRLR có chiều cao là h (AncRL->Bal =-1; h >= 1)  Cả AncRLL và AncRLR đều có chiều cao là h (AncRL->Bal =0; h >= 0) 16 3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: c1) AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1)  AncRLL có chiều cao là h và AncRLR có chiều cao là h-1 (AncRL->Bal =1; h >=1) 17 Ví dụ: Thêm nút có Key = 27 vào cây nhị phân tìm kiếm cân bằng, thực hiện cân bằng lại như 18  Thực hiện quay đơn cây con trái của BALTree->BAL_Right cây nhị phân tìm kiếm sau khi quay trở thành cây nhị phân tìm kiếm như sau: 19  Thực hiện quay đơn 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: 20 3.2.a Thêm 1 nút vào cây cân bằng Trường hợp 2: Nếu AncestorNode->Bal = 2:  Cũng tương tự như trường hợp 1, thực hiện quay đơn hoặc quay kép các nhánh phía ngược lại Gọi: AncL = AncestorNode->BAL_Left AncR = AncestorNode->BAL_Right => AncL có chiều cao là h+2 và AncR có chiều cao là h (h 0) =>Có ít nhất 1 cây con của AncL có chiều cao là h+1 Gọi: AncLL = AncL->BAL_Left AncLR = AncL->BAL_Right Cây con có nút gốc AncestorNode có thể ở vào một trong ba dạng sau:  AncLL có chiều cao là h+1 và AncLR có chiều cao là h (AncL- >Bal = 1)  AncLL và AncLR đều có chiều cao là h+1 (AncL->Bal = 0)  AncLL có chiều cao là h và AncLR có chiều cao là h+1 (AncL- >Bal = -1) 21 3.2.a (tt)Trường hợp 2: Nếu AncestorNode->Bal = 2(lệch trái): a2) AncLL có chiều cao là h+1 và AncLR có chiều cao là h (AncL- >Bal = 1) 22 Minh hoạ quay đơn: 23 3.2.a (tt)Trường hợp 2: Nếu AncestorNode->Bal = 2: b2) AncLL và AncLR đều có chiều cao là h+1 (AncL->Bal = 0) 24  Vd 2.b: 35 50 4020 10 20 35 50 40 70 70 10 44 44 25 3.2.a (tt) Trường hợp 2: Nếu AncestorNode->Bal = 2: c2) AncLL có chiều cao là h và AncLR có chiều cao là h+1 (AncL- >Bal = -1)  Tương tự như T1.3), việc cân bằng lại AncestorNode được thực hiện thông qua phép quay kép: quay cây con phải AncLR và quay cây con trái AncL (Double Rotation). Việc quay được tiến hành: Gọi: AncLRL = AncLR->BAL_Left AncLRR = AncLR->BAL_Right => AncLRL và AncLRR có chiều cao tối đa là h 26 3.2.a (tt) Trường hợp 2: Nếu AncestorNode->Bal = 2: c2) (tt) => Cây con có nút gốc AncestorNode có thể ở vào một trong ba dạng sau: AncLRL có chiều cao là h-1 và AncLRR có chiều cao là h (AncRL->Bal =-1; h >=1) AncLRL có chiều cao là h và AncLRR có chiều cao là h-1 (AncRL->Bal =1; h >= 1) Cả AncLRL và AncLRR đều có chiều cao là h (AncRL->Bal =0; h >= 0) 27 3.2.a (tt) Trường hợp 2: Nếu AncestorNode->Bal = 2: c2) (tt) AncLRL có chiều cao là h-1 và AncLRR có chiều cao là h (AncRL->Bal =-1; h >=1) 28 Ví dụ:  Cây nhị phân tìm kiếm cân bằng sau khi thêm nút có Key = 10 như sau: Thực hiện quay cây con trái của BALTree trở thành nút trái của 50 29  Thực hiện quay cây con trá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: 30 3.2.a (tt) Trường hợp 2: Nếu AncestorNode->Bal = 2: c2) (tt) Cả AncLRL và AncLRR đều có chiều cao là h (AncRL->Bal =0; h >= 0) 31 3.2.a (tt) Trường hợp 2: Nếu AncestorNode->Bal = 2: c2) (tt) AncLRL có chiều cao là h và AncLRR có chiều cao là h-1 (AncRL->Bal =1; h >= 1) 32 Ví dụ:  Cây nhị phân tìm kiếm cân bằng sau khi thêm nút có Key = 44 như sau: Thực hiện quay cây con phải của BALTree->BAL_Left 33 Thực hiện quay cây con phải của BALTree->BAL_Left 34 Cây tìm kiếm trở thành: 35 3.2.b. Hủy một nút khỏi cây cân bằng  Tương tự như trong tháo tác thêm, hủy một nút DelNode có thành phần dữ liệu là DelData ra khỏi cây cân bằng BALTree sao cho sau khi hủyBALTree 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 hủy là nút con trái hoặc nút con phải của một nút PrDelNode tương tự như trong cây nhị phân tìm kiếm.  Việc hủy cũng chia làm ba trường hợp như đối với trong cây nhị phân tìm kiếm:  DelNode là nút lá,  DelNode là nút trung gian có 01 cây con,  DelNode là nút có đủ 02 cây con. 36 Minh hoạ quay kép: 37 3.2.b. Hủy một nút khỏi cây cân bằng (tt)  Trong trường hợp DelNode có đủ 02 cây con, sử dụng phương pháp hủy phần tử thế mạng vì theo phương pháp này sẽ làm cho chiều cao của cây ít biến động hơn phương pháp kia.  Sau khi hủy DewNode ra khỏi 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ừ PrDelNode trở về các nút trước cũng sẽ bị thay đổi dây chuyền và chúng ta phải lần ngược từ PrDelNode về theo các nút trước để theo dõi sự thay đổi này. Nếu phát hiện tại một nút AncNode 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 AncNode này.