39
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 77
Cây nhị phân tìm kiếm cân bằng
(AVL Tree)
! Vì sao phải cân bằng ?
! Định nghĩa
! Ví dụ
! Mô tả cấu trúc dữ liệu
! Thao tác điều chỉnh cây
! Ví dụ tạo cây
! Các đánh giá
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 78
AVL Tree
Vìsao phải cân bằng ?
! Cây BST có thể không cân bằng
Tom
Nancy
Alan
Bob
Ellen
Jane
Wendy
Cây bị lệch
à Chi phí O(N)
Trường hợp nào cây
BST trở nên bị lệch ?
Cần có 1 phương
pháp để duy trì độ cân
bằng cho cây !
40
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 79

Cây AVL ?
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 82
AVL Tree
Môtảcấu trúc dữ liệu
! Thêm vào mỗi nút trong cây 1 field Bal,
diễn tả trạng thái của nút đó:
! Bal = -1: nút lệch trái (cây con trái cao hơn
cây con phải)
! Bal = 0: nút cân bằng (cây con trái cao bằng
cây con phải)
! Bal = +1: nút lệch phải (cây con phải cao hơn
cây con trái)
42
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 83
AVL Tree
Môtảcấu trúc dữ liệu
10
20
30
15
40
26
27
25
1
0
-1
0
1
0

intData;
intBal; // Hệ số cân bằng (-1,0,1)
tagBT_NODE*pLeft; // con trỏ đến nút con trái
tagBT_NODE*pRight; // con trỏ đến nút con phải
} AVLT_NODE;// Cấu trúc nút của cây AVL
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 86
AVL Tree
Môtảcấu trúc dữ liệu
// Định nghĩa các cấu trúc dữ liệu … (tiếp theo)
typedef struct AVL_TREE {
intCount; // Số nút trong cây
AVLT_NODE*pRoot; // con trỏ đến nút gốc
};// Cấu trúc cây AVL