Cây AVL

Trong khoa học máy tính, một Cây AVL là một cây tìm kiếm nhị phân tự cân bằng, và là cấu trúc dữ liệu đầu tiên có khả năng này. Trong một cây AVL, tại mỗi nút chiều cao của hai cây con sai khác nhau không quá một. Hiệu quả là các phép chèn (insertion), và xóa (deletion) luôn chỉ tốn thời gian O(log n) trong cả trường hợp trung bình và trường hợp xấu nhất. Phép bổ sung và loại bỏ có thể cần đến việc tái cân bằng bằng một hoặc nhiều phép quay.

Cây AVL được gọi theo tên của hai người đề xuất chúng, G.M. Adelson-Velsky và E.M. Landis, được công bố trong bài báo của họ vào năm 1962: "An algorithm for the organization of information." (Một thuật toán về tổ chức thông tin)

Cây AVL thường được so sánh với cây đỏ đen vì chúng hỗ trợ các phép toán như nhau và cùng tốn thời gian O(log n) cho các phép toán cơ sở. Cây AVL thường thi hành tốt hơn cây đỏ đen đối với các ứng dụng sâu sắc.^[1] Các thuật toán cân bằng cây AVL được cung cấp trong nhiều giáo trình về khoa học máy tính.

Định nghĩa

Hệ số cân bằng

Hệ số cân bằng của cây T là hiệu số giữa các chiều cao của cây con trái và cây con phải của nó. Ký hiệu hệ số cân bằng của cây con gôc u là balance(u). Hệ số cân bằng của cây T là balance(T).

balance(u)= height(u.right)-height(u.left)

Nếu với mọi đỉnh u của T ta có balance(u)= 0 thì T được gọi là cây cân bằng hoàn toàn; Nếu balance(T) > 0, nghĩa là cây con phải cao hơn cây con trái T được gọi là cây lệch phải; Nếu balance(T)< 0, nghĩa là cây con trái cao hơn cây con phải T được gọi là cây lệch trái.

Cân bằng AVL và cây AVL

Các cây tìm kiếm nhị phân được xây dựng theo phương pháp chèn thông thường có thể có những biến dạng mất cân đối nghiêm trọng, chẳng hạn có thể hoàn toàn lệch phải (tất cả các nút trong chỉ có con phải) hoặc lệch trái (tất cả các nút trong chỉ có con trái). Trong các trường hợp này chi phí cho việc tìm kiếm trong trường hợp xấu nhất đạt tới n (n là số nút trên cây). Nếu có một cây tìm kiếm nhị phân cân bằng hoàn toàn, chi phí đó chỉ xấp xỉ log₂n. Tuy nhiên nhiều khi không thể xây dựng một cây tìm kiếm nhị phân như vậy cho mọi dãy khóa. G.M. Adelson-Velsky và E.M. Landis đã đề xuất một tiêu chuẩn cân bằng (sau này gọi là cân bằng AVL), giảm nhẹ hơn so với cân bằng hoàn toàn. Cây T được gọi là cân bằng AVL nếu tại mỗi nút u của nó hệ số cân bằng có trị số tuyệt đối không vượt quá 1. Điều đó cũng có nghĩa là với mọi nút u của T, balance(u) chỉ nhận một trong ba giá trị -1, 0, 1. Khi đó cây T cũng được gọi là cây AVL. Nếu cây con gốc tại đỉnh u là cân bằng AVL, ta cũng gọi đỉnh u là cân bằng AVL. Như vậy các lá là cân bằng AVL, cây chỉ gồm một nút gốc là cây AVL, cây chỉ gồm 2 nút là cây AVL. Cây gồm 3 nút có thể cân bằng AVL, cũng có thể không.

Phép chèn

Phép chèn và tính cân bằng AVL

Giả sử có một cây tìm kiếm nhị phân cân bằng AVL và u là một nút của T và một nút mới v được chèn vào u. Do v chỉ có thể được chèn vào đúng một trong hai cây con của u nên nhiều nhất là v có thể làm tăng chiều cao của một trong hai cây con đó. Nếu v không làm tăng chiều cao của cây con nào hoặc v làm tăng chiều cao của một cây con nhưng trước đó cây con này có chiều cao nhỏ hơn hoặc bằng chiều cao của cây con kia thì tính cân bằng AVL tại đỉnh u vẫn giữ nguyên. Tính cân bằng AVL tại u chỉ có thể bị phá vỡ khi v làm tăng chiều cao của cây con có chiều cao lớn hơn trong hai cây con của u.

Cũng như vậy, nếu v không làm tăng chiều cao của chính u thì v không làm thay đổi hệ số cân bằng tại các đỉnh tiền bối của u.

Mặt khác, nút v luôn được thêm vào với tư cách là con của một nút trước đó là lá hoặc nửa lá.

Nếu đỉnh cha của v trước khi thêm v là nửa lá, thì chiều cao của cây con gốc cha của v không thay đổi sau khi thêm v còn hệ số cân bằng tại đỉnh cha này bằng 0. Khi đó tất cả các nút tiền bối của cha của v không thay đổi hệ số cân bằng. Tính cân bằng AVL được giữ vững trên toàn bộ cây T.

Nếu đỉnh cha của v trước khi thêm v là lá, gọi u là đỉnh tiền bối của v có mức cao nhất mà tính cân bằng AVL bị phá vỡ.

Như vậy bốn trường hợp sau có thể phá vỡ tính cân bằng AVL tại u

Trước khi chèn cây con gốc u lệch trái và v làm tăng chiều cao của cây con trái.
1. .Sau khi chèn cây con trái lệch trái (Case LL);
2. .Sau khi chèn cây con trái lệch phải (Case LR).
.Trước khi chèn cây con gốc u lệch phải và v làm tăng chiều cao của cây con phải.
1. .Sau khi chèn cây con phải lệch phải (Case RR);
2. .Sau khi chèn cây con phải lệch trái. (Case RL)

Tái cân bằng sau phép chèn

Khi tính cân bằng AVL tại u bị phá vỡ, cần một hoặc hai phép quay để tái cân bằng AVL cây con gốc u và biến đổi cây T trở thành cân bằng AVL.

Trường hợp 1 (LL)

Thực hiện phép quay phải tại u.

Trường hợp 2 (LR)

Trước hết thực hiện phép quay trái tại u.left để đưa về TH1 (LL) sau đó thực hiện phép quay phải tại u.

Trường hợp 3 (RR)

Thực hiện phép quay trái tại u.

Trường hợp 4 (RL)

Trước hết thực hiện phép quay phải tại u.right để đưa về TH3 (RR) sau đó thực hiện phép quay trái tại u.

Mã giả

Trong đoạn giả mã sau, height(u) là chiều cao của cây con của u. Khi đỉnh u là lá, height(u)=1. Với mỗi đỉnh u không là lá height(u)=max{height(u.left),height(u.right)}+1. Có thể dùng một phép duyệt hậu thứ tự để tính hàm height(u) tại mọi đỉnh trên cây T. Tuy nhiên, khi mỗi đỉnh mới được chèn vào cây (luôn là lá) ta sẽ tính lại giá trị hàm height(v) với mọi v là tiền bối của đỉnh đó.

 CALCULATE-BALANCE(u)
 // Tính hệ số cân bằng và chiều cao cây con tại đỉnh u.
 if  u.right = Null and u.left=Null then
     begin
         height(u)=1;
         balance(u)=0
     end; 
 else
     if u.right = Null and u.left<>Null then 
         begin
             height(u)=height(u.left)+1;
             balance(u)=height(u)
         end
     else  
         if u.left = Null and u.right<>Null then 
             begin
                 height(u)=height(u.right)+1;
                 balance(u)=-height(u)
             end;
         else
             begin
                 height(u)=max(height(u.left),height(u.right))+1;
                 balance(u)=height(u.left)-height(u.right);
             end;

 REBALANCE(v)
  // Thủ tục này tái cân bằng AVL (nếu bị mất cân bằng) các một đỉnh tiền bối của v bị mất cân bằng AVL. 
  // Sau đó các  bậc tiền
  bối trên nữa sẽ không thay đổi hệ số cân bằng so với trước khi đỉnh v được chèn vào.   
  // v là lá 
  //Tìm đỉnh tiền bối v sao cho v có tri số tuyệt đối của v  
  u= v
  while u<> T.root and abs(balance(u)) ≤1 do 
      begin 
          CALCULATE-BALACE(u)
          u=u.parent;
      end;   
  if balance(u)>2 then 
      if balance(u.left)>0 then
          RIGHT-ROTATE(u)
      else
          begin
              LEFT-ROTATE(u.left);
              RIGHT-ROTATE(u);
          end;
  else
      if balance(u)<-2 then
          if balance(u.right)< 0 then
              LEFT-ROTATE(u)
          else
              begin
                  RIGHT-ROTATE(u.right);
                  LEFT-ROTATE(u);
              end;

Phép xóa trên cây AVL

Giả sử phải xóa nút v trên cây AVL. Trước hết thực hiện phép xóa như với cây tìm kiếm nhị phân thông thường. Khi đó v luôn được thay bằng một nút lá hoặc nửa lá với con trái. Gọi p là cha của v, v1 là con trái của v (có thể NULL). Khi loại v khỏi cây, ta lấy con trái v1 thay vào vị trí của v. Chiều cao của cây con con gốc v1 cũng như hệ số cân bằng của nó không thay đổi, tuy nhiên chiều cao và hệ số cân bằng của nút cha p có thể thay đổi. Khi đó cũng có 4 trường hợp như khi chèn, ta chỉ việc áp dụng thủ tục REBALANCE(p).

Xem thêm

Tham khảo

^ Pfaff, Ben (2004). “Performance Analysis of BSTs in System Software” (PDF). Stanford University.

[1] Pfaff, Ben (2004). “Performance Analysis of BSTs in System Software” (PDF). Stanford University.

[1]