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. 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.

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.

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