[Thuật toán] Cây căn bằng - Phần 2

Share:

[Thuật toán] Cây căn bằng - Phần 1

3.1. 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. Ta có 6 khả năng sau:

Trường hợp 1: cây T lệch về bên trái (có 3 khả năng)

Cây T lệch về bên phải - tinhoccoban.net

Trường hợp 2: cây T lệch về bên phải

 
Cây T lệch về bên phải - tinhoccoban.net
Cây T lệch về bên phải

Ta có thể thấy rằng các trường hợp lệch về bên phải hoàn toàn đối xứng với các trường hợp lệch về bên trái. Vì vậy ta 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.

Sau đây, ta sẽ khảo sát và giải quyết từng trường hợp nêu trên

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
Cây T1 lệch về bên trái.- tinhoccoban.net
Cây T1 lệch về bên trái.

T/h 1.2: cây T1 không lệch. Ta thực hiện phép quay đơn Left-Left
Ttoán quay đơn Left-Left:
          B1:     T là gốc; T1 = T->pLeft;
T->pLeft = T1->pRight;
           T1->pRight = T;
B2:// đặt lại chỉ số cân bằng
Nếu T1->balFactor = LH thì:
 T->balFactor = EH;
T1->balFactor = EH;
break;
Nếu T1->balFactor = EH thì:
T->balFactor = LH;
T1->balFactor = RH;
break;
          B3:// T trỏ đến gốc mới
T = T1;


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ẽ 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.
Hình vẽ dưới đây minh họa phép quay kép áp dụng cho trường hợp này:
cây T1 lệch về bên phải. Ta thực hiện phép quay kép Left-Right - tinhoccoban.net

Ttoán quay kép Left - Right
B1:    gốc T;
T1 = T->pLeft; T2 = T1->pRight; T->pLeft = T2->pRight;
T2->pRight = T;T1->pRight = T2->pLeft;T2->pLeft = T1;
B2: //đặt lại chỉ số cân bằng
Nếu T2->balFactor = LH thì:
T->balFactor = RH; T1->balFactor = EH; break;
Nếu T2->balFactor = EH thì:
 T->balFactor = EH; T1->balFactor = EH; break;
Nếu T2->balFactor = RH thì:
T->balFactor = EH; T1->balFactor = LH; break;
B3:
T2->balFactor = EH;
T = T2;





Lưu ý rằng, 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, trong 2 trường hợp 1.1 và 1.3 cây có chiều cao h+1; còn ở trường hợp 1.2 cây vẫn có chiều cao h+2. Và trường hợp này cũng 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 khác 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).
Với những xem xét trên, xét tương tự cho trường hợp cây T lệch về bên phải, ta có thể xây dựng 2 hàm quay đơn và 2 hàm quay kép sau:

3.2.THÊM MỘT PHẦN TỬ TRÊN CÂY AVL:

Việc thêm một phần tử vào cây AVL diễn ra tương tự như trên CNPTK. Tuy nhiên, 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 tìm ngược lên gốc để kiểm tra các nút 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.

TToán: Giả sử cần thêm vào một nút mang thông tin X.
1. Tìm kiếm vị trí thích hợp để thêm nút X (đưa ra thông báo nếu đã có nút X rồi)
2. Thêm nút X vào cây
3. Cân bằng lại cây.
         

3.3. HỦY MỘT PHẦN TỬ TRÊN CÂY AVL:

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. Chỉ 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.