[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)
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
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. |
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:
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.