Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 9: Cây nhị phân

 quy chính nó để thêm một nút mới có thể 
lớn bằng chiều cao của cây. Thoạt nhìn, dường như là mỗi lần gọi đệ quy đều dẫn 
đến một lần quay đơn hoặc quay kép cho cây con tương ứng, nhưng thực ra, nhiều 
nhất là chỉ có một phép quay (đơn hoặc kép) là được thực hiện. Để nhìn thấy điều 
này, chúng ta biết rằng các phép quay được thực hiện chỉ trong các hàm 
right_balance và left_balance, và các hàm này được gọi chỉ khi chiều cao 
của cây con có tăng lên. Tuy nhiên, khi các hàm này thực hiện xong, các phép 
quay đã làm cho chiều cao cây con trở về giá trị ban đầu, như vậy, đối với các lần 
gọi đệ quy trước đó chưa kết thúc, chiều cao cây con tương ứng sẽ không thay đổi, 
và sẽ không có một phép quay hay một sự thay đổi các thông số cân bằng nào 
nữa. 
Phần lớn việc thêm vào cây AVL không dẫn đến phép quay. Ngay cả khi phép 
quay là cần thiết, nó thường xảy ra gần với nút lá vừa được thêm vào. Mặc dù giải 
thuật thêm vào một cây AVL là phức tạp, nhưng chúng ta có lý do để tin rằng 
thời gian chạy của nó không khác bao nhiêu so với việc thêm vào một cây nhị 
phân tìm kiếm bình thường có cùng chiều cao. Chúng ta còn có thể hy vọng rằng 
chiều cao của cây AVL nhỏ hơn rất nhiều chiều cao của cây nhị phân tìm kiếm 
bình thường, và như vậy cả hai việc thêm vào và loại bỏ nút sẽ hiệu quả hơn 
nhiều so với cây nhị phân tìm kiếm bình thường. 
Chương 9 – Cây nhị phân 
Giáo trình Cấu trúc Dữ liệu và Giải thuật 230
9.5.3. Loại một nút 
Việc loại một nút x ra khỏi một cây AVL cũng theo ý tưởng tương tự, cũng bao 
gồm phép quay đơn và phép quay kép. Chúng ta sẽ phác thảo các bước của giải 
thuật dưới đây, hiện thực cụ thể của hàm xem như bài tập. 
1. Chúng ta chỉ cần xem xét trường hợp nút x cần loại có nhiều nhất là một 
cây con, vì đối với trường hợp x có hai cây con, chúng ta sẽ tìm nút y là nút 
kế trước nó (hoặc nút kế sau nó) trong thứ tự duyệt inorder để loại thay cho 
nó. Từ nút con trái của x nếu di chuyển sang phải cho đến khi không thể di 
chuyển được nữa, chúng ta gặp một nút y không có con phải. Lúc đó chúng 
ta sẽ chép dữ liệu trong y vào x, không thay đổi thông số cân bằng cũng 
như con trái và con phải của x. Cuối cùng nút y sẽ được loại đi thay cho nút 
x theo các bước dưới đây. 
2. Gọi nút cần loại là x. Loại nút x ra khỏi cây. Do x có nhiều nhất một con, 
việc loại x đơn giản chỉ là nối tham chiếu từ nút cha của x đến nút con của 
nó (hoặc NULL nếu x không có con nào). Chiều cao cây con có gốc là x giảm 
đi 1, và điều này có thể ảnh hưởng đến các nút nằm trên đường đi từ 
x ngược về gốc của cây. Vì vậy trong quá trình duyệt cây để xuống đến 
nút x, chúng ta cần lưu vết bằng cách sử dụng ngăn xếp để có thể xử lý lần 
ngược về. Để đơn giản, chúng ta có thể dùng hàm đệ quy với tham biến 
shorter kiểu bool cho biết chiều cao của cây con có bị giảm đi hay 
không. Các việc cần làm tại mỗi nút phụ thuộc vào trị của tham biến 
shorter mà con nó trả về sau khi việc gọi đệ quy xuống cây con kết thúc, 
vào thông số cân bằng của nó, và đôi khi phụ thuộc vào cả thông số cân 
bằng của nút con của nó. 
Hình 9.20 – Thêm nút vào cây AVL: các trường hợp cần có phép quay. 
Chương 9 – Cây nhị phân 
Giáo trình Cấu trúc Dữ liệu và Giải thuật 231
3. Biến bool shorter được khởi gán trị true. Các bước sau đây sẽ được thực 
hiện tại mỗi nút nằm trên đường đi từ nút cha của x cho đến nút gốc của 
cây. Trong khi mà tham biến shorter trả lên còn là true, việc giải quyết 
cứ tiếp tục cho đến khi có một nút nhận được trị trả về của tham biến này 
là false. Một khi có một cây con nào đó báo rằng chiều cao của nó không 
bị giảm đi thì các nút trên của nó sẽ không bị ảnh hưởng gì cả. Ngược lại, 
gọi nút p là nút vừa gọi đệ quy xuống nút con xong và nhận thông báo 
shorter là true, cần xét các trường hợp sau: 
Trường hợp 1: Nút p hiện tại có thông số cân bằng là equal_height. 
Thông số này sẽ thay đổi tùy thuộc vào cây con trái hay cây con phải của 
nó đã bị ngắn đi. Biến shorter đổi thành false. 
Trường hợp 2: Nút p hiện tại có thông số cân bằng không là 
equal_height. Cây con vốn cao hơn vừa bị ngắn đi. Thông số cân 
bằng của p chỉ cần đổi về equal_height. Trường hợp này cây gốc p cũng 
bị giảm chiều cao nên tham biến shorter vẫn là true để trả lên trên cho 
cha của p giải quyết tiếp. 
Trường hợp 3: Nút p hiện tại có thông số cân bằng không là 
equal_height. Cây con vốn thấp hơn vừa bị ngắn đi. Như vậy tại nút 
p vi phạm điều kiện của cây AVL, và chúng ta thực hiện phép quay để 
khôi phục lại sự cân bằng như sau. Gọi q là gốc của cây con cao hơn của p, 
có 3 trường hợp tương ứng với thông số cân bằng trong q: 
Trường hợp 3a: Thông số cân bằng của q là equal_height. Thực 
hiện một phép quay đơn để thay đổi các thông số cân bằng của p và q, 
trạng thái cân bằng sẽ được khôi phục, shorter đổi thành false. 
Trường hợp 3b: Thông số cân bằng của q giống với thông số cân 
bằng của p. Thực hiện một phép quay đơn để chuyển các thông số 
này thành equal_height, shorter vẫn là true. 
Trường hợp 3c: Thông số cân bằng của q ngược với thông số cân 
bằng của p. Thực hiện một phép quay kép (trước hết quay quanh q, 
sau đó quay quanh p), thông số cân bằng của gốc mới sẽ là 
equal_height, các thông số cân bằng của p và q được biến đổi thích 
hợp, shorter vẫn là true. 
Trong các trường hợp 3a, b, c, chiều của các phép quay phụ thuộc vào cây con 
trái hay cây con phải bị ngắn đi. Hình 9.21 minh họa một vài trường hợp, và một 
ví dụ loạïi một nút được minh họa trong hình 9.22. 
Chương 9 – Cây nhị phân 
Giáo trình Cấu trúc Dữ liệu và Giải thuật 232
Hình 9.21 – Các trường hợp loại một nút ra khỏi cây AVL. 
Chương 9 – Cây nhị phân 
Giáo trình Cấu trúc Dữ liệu và Giải thuật 233
Hình 9.22 – Ví dụ loại một nút ra khỏi cây AVL. 
Chương 9 – Cây nhị phân 
Giáo trình Cấu trúc Dữ liệu và Giải thuật 234
9.5.4. Chiều cao của cây AVL 
Việc tìm chiều cao của một cây AVL trung bình là một việc rất khó, do đó việc 
xác định số bước trung bình cần thực hiện bởi các giải thuật trong phần này cũng 
không dễ. Cách dễ nhất cho chúng ta là xác định những gì sẽ xảy ra trong trường 
hợp xấu nhất, và các kết quả này sẽ cho chúng ta thấy rằng các hành vi của cây 
AVL trong trường hợp xấu nhất cũng không tệ hơn các hành vi của các cây ngẫu 
nhiên. Bằng chứng thực nghiệm cho thấy các hành vi trung bình của các cây AVL 
tốt hơn rất nhiều so với các cây ngẫu nhiên, hầu như nó còn tốt ngang với những 
gì sẽ có được từ một cây cân bằng hoàn toàn. 
Để xác định chiều cao tối đa có thể có được của một cây AVL có n nút, chúng 
ta sẽ xem thử với một chiều cao h cho trước, cây AVL sẽ có số nút tối thiểu là bao 
nhiêu. Gọi Fh là một cây như vậy, thì cây con trái và cây con phải của nút gốc của 
Fh 
sẽ là Fl và Fr. Một trong hai cây con này phải có chiều cao là h-1, giả sử cây Fl, 
và cây con còn lại có chiều cao h-1 hoặc h-2. Do Fh có số nút tối thiểu của một cây 
AVL có chiều cao h, Fl cũng phải có số nút tối thiểu của cây AVL cao h-1 (có 
nghĩa là Fl có dạng Fh-1), và Fr phải có chiều cao h-2 với số nút tối thiểu (Fr có 
dạng Fh-2). 
Các cây được tạo bởi quy tắc trên, nghĩa là các cây thỏa điều kiện cây AVL 
nhưng càng thưa càng tốt, được gọi là các cây Fibonacci. Một số ít cây đầu tiên có 
thể được thấy trong hình 9.23. 
Với ký hiệu |T| biểu diễn số nút trong cây T, chúng ta có công thức sau: 
 | Fh | = | Fh-1 | + | Fh-2 | + 1. 
Hình 9.23 – Các cây Fibonacci 
Chương 9 – Cây nhị phân 
Giáo trình Cấu trúc Dữ liệu và Giải thuật 235
với | F0 | = 1 và | F1 | = 2. Bằng cách thêm 1 vào cả hai vế, chúng ta thấy 
con số | Fh |+1 thỏa định nghĩa của các số Fibonacci bậc 2. Bằng cách tính các 
số Fibonacci chúng ta có 
 | Fh |+1 ≈ 
Lấy logarit hai vế và chỉ giữ lại các số lớn chúng ta có 
 h ≈ 1.44 lg | Fh |. 
Kết quả cho thấy một cây AVL n nút thưa nhất sẽ có chiều cao xấp xỉ 1.44 lg 
n. Một cây nhị phân cân bằng hoàn toàn có n nút có chiều cao bằng lg n, còn cây 
suy thoái sẽ có chiều cao là n. Thời gian chạy các giải thuật trên cây AVL được 
bảo đảm không vượt quá 44 phần trăm thời gian cần thiết đối với cây tối ưu. 
Trong thực tế, các cây AVL còn tốt hơn rất nhiều. Điều này có thể được chứng 
minh như sau, ngay cả đối với các cây Fibonacci - các cây AVL trong trường hợp 
xấu nhất – thời gian tìm kiếm trung bình chỉ có 4 phần trăm lớn hơn cây tối ưu. 
Phần lớn các cây AVL sẽ không thưa thớt như các cây Fibonacci, và do đó thời 
gian tìm kiếm trung bình trên các cây AVL trung bình rất gần với cây tối ưu. 
Thực nghiệm cho thấy số lần so sánh trung bình khoảng lg n + 0.25 khi n lớn. 
1 1+ 5
 ⎯ ⎯⎯ 
 5 2
h+2 
Chương 9 – Cây nhị phân 
Giáo trình Cấu trúc Dữ liệu và Giải thuật 236