Khác biệt giữa bản sửa đổi của “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 truc 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 cây|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 [[ký hiệu O lớn|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ấu trúc dữ liệu)|phép quay]].

Cây AVL được gọi theo tên của hai người đề xuất chúng, [[Georgii Adelson-Velsky|G.M. Adelson-Velsky]] và [[Yevgeniy Landis|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'')

 

 

==== Trường hợp 1 (LL)====

Thực hiện [[Phép quay cây nhị phâ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.

====Tính chất====

===Giả mã ===

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

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