Cây AVL

Bách khoa toàn thư ngỏ Wikipedia

Trong khoa học tập PC, một Cây AVL là 1 trong cây thám thính kiếm nhị phân tự động thăng bằng, và là cấu tạo tài liệu thứ nhất với tài năng này. Trong một cây AVL, bên trên từng nút độ cao của nhị cây con cái sai không giống nhau không thực sự một. Hiệu trái ngược là những luật lệ chèn (insertion), và xóa (deletion) luôn luôn chỉ tốn thời hạn O(log n) nhập cả tình huống tầm và tình huống xấu xa nhất. Phép bổ sung cập nhật và vô hiệu rất có thể sử dụng việc tái mét thăng bằng vì thế một hoặc nhiều luật lệ con quay.

Bạn đang xem: avl tree là gì

Cây AVL được gọi theo đuổi thương hiệu của nhị người khuyến nghị bọn chúng, G.M. Adelson-Velsky và E.M. Landis, được công tía nhập bài xích báo của mình nhập năm 1962: "An algorithm for the organization of information." (Một thuật toán về tổ chức triển khai thông tin)

Cây AVL thông thường được đối chiếu với cây đỏ chót thâm vì thế bọn chúng tương hỗ những luật lệ toán như nhau và nằm trong tốn thời hạn O(log n) cho những luật lệ toán hạ tầng. Cây AVL thông thường thực hiện đảm bảo chất lượng rộng lớn cây đỏ chót thâm so với những phần mềm thâm thúy.^[1] Các thuật toán thăng bằng cây AVL được cung ứng trong tương đối nhiều giáo trình về khoa học tập PC.

Định nghĩa[sửa | sửa mã nguồn]

Hệ số cân nặng bằng[sửa | sửa mã nguồn]

Hệ số thăng bằng của cây T là hiệu số trong những độ cao của cây con cái trái ngược và cây con cái cần của chính nó. Ký hiệu thông số thăng bằng của cây con cái gôc u là balance(u). Hệ số thăng bằng của cây T là balance(T).

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

Nếu với từng đỉnh u của T tớ với balance(u)= 0 thì T được gọi là cây thăng bằng trả toàn; Nếu balance(T) > 0, tức thị cây con cái cần cao hơn nữa cây con cái trái ngược T được gọi là cây chếch phải; Nếu balance(T)< 0, tức thị cây con cái trái ngược cao hơn nữa cây con cái cần T được gọi là cây chếch trái ngược.

Cân vì thế AVL và cây AVL[sửa | sửa mã nguồn]

Các cây thám thính kiếm nhị phân được xây cất theo đuổi cách thức chèn thường thì rất có thể với những biến dị mất mặt bằng phẳng nguy hiểm, ví dụ điển hình rất có thể trọn vẹn chếch cần (tất cả những nút nhập chỉ mất con cái phải) hoặc chếch trái ngược (tất cả những nút nhập chỉ mất con cái trái). Trong những tình huống này ngân sách mang lại việc thám thính kiếm nhập tình huống xấu xa nhất đạt cho tới n (n là số nút bên trên cây). Nếu với cùng một cây thám thính kiếm nhị phân thăng bằng trọn vẹn, ngân sách bại liệt chỉ xấp xỉ log₂n. Tuy nhiên nhiều lúc không thể xây cất một cây thám thính kiếm nhị phân như thế mang lại từng sản phẩm khóa. G.M. Adelson-Velsky và E.M. Landis đang được khuyến nghị một chi phí chuẩn chỉnh thăng bằng (sau này gọi là thăng bằng AVL), hạn chế nhẹ nhàng rộng lớn đối với thăng bằng trọn vẹn. Cây T được gọi là thăng bằng AVL nếu như bên trên từng nút u của chính nó thông số thăng bằng với trị số vô cùng ko vượt lên trước quá 1. Điều này cũng Có nghĩa là với từng nút u của T, balance(u) chỉ nhận một trong những tía độ quý hiếm -1, 0, 1. Khi bại liệt cây T cũng khá được gọi là cây AVL. Nếu cây con cái gốc bên trên đỉnh u là thăng bằng AVL, tớ cũng gọi đỉnh u là thăng bằng AVL. Như vậy những lá là thăng bằng AVL, cây chỉ bao gồm một nút gốc là cây AVL, cây chỉ bao gồm 2 nút là cây AVL. Cây bao gồm 3 nút rất có thể thăng bằng AVL, cũng rất có thể ko.

Phép chèn[sửa | sửa mã nguồn]

Phép chèn và tính thăng bằng AVL[sửa | sửa mã nguồn]

Giả sử với cùng một cây thám thính kiếm nhị phân thăng bằng AVL và u là 1 trong nút của T và một nút mới nhất v được chèn nhập u. Do v chỉ rất có thể được chèn nhập chính một trong những nhị cây con cái của u nên tối đa là v rất có thể thực hiện tăng độ cao của một trong những nhị cây con cái bại liệt. Nếu v ko thực hiện tăng độ cao của cây con cái nào hoặc v thực hiện tăng độ cao của một cây con cái tuy nhiên trước bại liệt cây con cái này còn có độ cao nhỏ rộng lớn hoặc vì thế độ cao của cây con cái bại liệt thì tính thăng bằng AVL bên trên đỉnh u vẫn không thay đổi. Tính thăng bằng AVL bên trên u chỉ rất có thể bị đánh tan Khi v thực hiện tăng độ cao của cây con cái với độ cao to hơn nhập nhị cây con cái của u.

Cũng như thế, nếu như v ko thực hiện tăng độ cao của chủ yếu u thì v ko thực hiện thay cho thay đổi thông số thăng bằng bên trên những đỉnh chi phí bối của u.

Mặt không giống, nút v luôn luôn được thêm vô với tư cơ hội là con cái của một nút trước này là lá hoặc nửa lá.

Xem thêm: light up là gì

Nếu đỉnh phụ vương của v trước lúc tăng v là nửa lá, thì độ cao của cây con cái gốc phụ vương của v không bao giờ thay đổi sau thời điểm tăng v còn thông số thăng bằng bên trên đỉnh phụ vương này vì thế 0. Khi bại liệt toàn bộ những nút chi phí bối của phụ vương của v không bao giờ thay đổi thông số thăng bằng. Tính thăng bằng AVL được lưu giữ vững vàng bên trên toàn cỗ cây T.

Nếu đỉnh phụ vương của v trước lúc tăng v là lá, gọi u là đỉnh chi phí bối của v với nấc tối đa tuy nhiên tính thăng bằng AVL bị đánh tan.

Như vậy tư tình huống sau rất có thể đánh tan tính thăng bằng AVL bên trên u

Trước Khi chèn cây con cái gốc u chếch trái ngược và v thực hiện tăng độ cao của cây con cái trái ngược.
1. .Sau Khi chèn cây con cái trái ngược chếch trái ngược (Case LL);
2. .Sau Khi chèn cây con cái trái ngược chếch cần (Case LR).
.Trước Khi chèn cây con cái gốc u chếch cần và v thực hiện tăng độ cao của cây con cái cần.
1. .Sau Khi chèn cây con cái cần chếch cần (Case RR);
2. .Sau Khi chèn cây con cái cần chếch trái ngược. (Case RL)

Tái thăng bằng sau luật lệ chèn[sửa | sửa mã nguồn]

Khi tính thăng bằng AVL bên trên u bị đánh tan, cần thiết một hoặc nhị luật lệ con quay nhằm tái mét thăng bằng AVL cây con cái gốc u và chuyển đổi cây T trở nên thăng bằng AVL.

Trường thích hợp 1 (LL)[sửa | sửa mã nguồn]

Thực hiện tại luật lệ con quay cần bên trên u.

Trường thích hợp 2 (LR)[sửa | sửa mã nguồn]

Trước không còn tiến hành luật lệ con quay trái ngược bên trên u.left để lấy về TH1 (LL) tiếp sau đó tiến hành luật lệ con quay cần bên trên u.

Trường thích hợp 3 (RR)[sửa | sửa mã nguồn]

Thực hiện tại luật lệ con quay trái ngược bên trên u.

Xem thêm: m3 là gì

Trường thích hợp 4 (RL)[sửa | sửa mã nguồn]

Trước không còn tiến hành luật lệ con quay cần bên trên u.right để lấy về TH3 (RR) tiếp sau đó tiến hành luật lệ con quay trái ngược bên trên u.

Mã giả[sửa | sửa mã nguồn]

Trong đoạn fake mã sau, height(u) là độ cao của cây con cái của u. Khi đỉnh u là lá, height(u)=1. Với từng đỉnh u ko là lá height(u)=max{height(u.left),height(u.right)}+1. cũng có thể người sử dụng một luật lệ duyệt hậu trật tự nhằm tính hàm height(u) bên trên từng đỉnh bên trên cây T. Tuy nhiên, Khi từng đỉnh vừa mới được chèn nhập cây (luôn là lá) tớ tiếp tục tính lại độ quý hiếm hàm height(v) với từng v là chi phí bối của đỉnh bại liệt.

 CALCULATE-BALANCE(u)
 // Tính thông số thăng bằng và độ cao cây con cái bên trên đỉ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 mét thăng bằng AVL (nếu bị mất mặt cân nặng bằng) những một đỉnh chi phí bối của v bị mất mặt thăng bằng AVL. 
  // Sau bại liệt những  bậc tiền
  bối bên trên nữa sẽ không còn thay cho thay đổi thông số thăng bằng đối với trước lúc đỉnh v được chèn nhập.   
  // v là lá 
  //Tìm đỉnh chi phí bối v sao mang lại v với tri số vô cùng của v  
  u= v
  while u<> T.root and abs(balance(u)) ≤1 vì thế 
      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 bên trên cây AVL[sửa | sửa mã nguồn]

Giả sử cần xóa nút v bên trên cây AVL. Trước không còn tiến hành luật lệ xóa như với cây thám thính kiếm nhị phân thường thì. Khi bại liệt v luôn luôn được thay cho một nút lá hoặc nửa lá với con cái trái ngược. Gọi p là phụ vương của v, v1 là con cái trái ngược của v (có thể NULL). Khi loại v ngoài cây, tớ lấy con cái trái ngược v1 thay cho nhập địa điểm của v. Chiều cao của cây con cái con cái gốc v1 hao hao thông số thăng bằng của chính nó không bao giờ thay đổi, tuy vậy độ cao và thông số thăng bằng của nút phụ vương p rất có thể thay cho thay đổi. Khi bại liệt cũng có thể có 4 tình huống như Khi chèn, tớ chỉ việc vận dụng giấy tờ thủ tục REBALANCE(p).