1
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.
2
Ví dụ:
AVL Tree
AVL Tree
3
3.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;
4
3.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)
5
3.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ừ