Avl Tree Là Gì

     

Điều gì sẽ xảy ra nếu dữ liệu nhập vào cây tìm kiếm nhị phân (BST) là ở dưới dạng đã được sắp thứ tự (giảm dần hoặc tăng dần). Nó sẽ trông giống như hình dưới đây:


*

Nói chung, hiệu suất trong trường hợp xấu nhất của cây tìm kiếm nhị phân (BST) cũng tương đương với các giải thuật tìm kiếm tuyến tính, hay còn gọi là Ο (n). Với dữ liệu thời gian thực, chúng ta không thể dự đoán được mẫu dữ liệu và những tần số của nó. Chính vì thế, điều cần thiết phải phát sinh ở đây là phải cân bằng cây tìm kiếm nhị phân đang có.Bạn đang xem: Avl tree là gì

Cây AVL (viết tắt của tên các nhà phát minh Landis, Adelson, và Velski) là cây tìm kiếm nhị phân được đánh giá là có độ cân bằng cao. Cây AVL có thể kiểm tra độ cao của các cây con bên phải và cây con bên trái và bảo đảm chắc chắn rằng hiệu số giữa chúng là không lớn hơn 1. Hiệu số này còn được gọi là Balance Factor (Nhân tố cân bằng).

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

Dưới đây là hình ví dụ minh họa các cây, trong đó cây đầu tiên là có độ cân bằng cao, cây thứ 2 và thứ 3 là không cân bằng.


*

Trong cây thứ 2, cây con bên phải có độ cao là 0 và cây con bên trái của C có độ cao là 2, do đó hiệu số của nó là 2. Trong cây thứ 3, cây con bên trái có độ cao là 0 và cây con bên phải của A có độ cao là 2, do đó hiệu số của nó cũng là 2. Trong khi đó cây AVL chỉ chấp nhận hiệu số (hay Nhân tố cân bằng) là 1.

BalanceFactor = height (left-sutree) − height (right-sutree)Nếu hiệu số giữa độ cao của các cây con bên phải và cây con bên trái là cao hơn 1 thì cây được cân bằng thông qua việc sử dụng một số kỹ thuật quay AVL được trình bày như dưới đây.

Kỹ thuật quay cây AVL

Để làm cho cây tự cân bằng, một cây AVL có thể được thực hiện bốn loại kỹ thuật quay như sau:

Kỹ thuật quay tráiKỹ thuật quay phảiKỹ thuật quay trái-phảiKỹ thuật quay phải-trái

2 kỹ thuật quay đầu tiên là các kỹ thuật quay đơn và 2 kỹ thuật quay còn lại là các kỹ thuật quay ghép.

Phần tiếp theo chúng ta sẽ tìm hiểu chi tiết mỗi một kỹ thuật quay với hình minh họa tương đối đơn giản và dễ hiểu.

Kỹ thuật quay trái cây AVL

Nếu một cây trở nên không cân bằng khi có một nút được chèn vào trong cây con ở bên phải của cây con bên phải thì chúng ta sẽ thực hiện kỹ thuật quay trái đơn như sau:


*

Trong hình minh họa ở trên, nút A không còn cân bằng khi một nút (nút C) được thêm vào cây con bên phải của một cây con bên phải của nút A. Chúng ta sẽ thực hiện kỹ thuật quay trái để giúp A trở thành cây con bên trái của B.

Kỹ thuật quay phải cây AVL

Cây AVL đã không còn cân bằng nếu một nút được thêm vào cây con bên trái của cây con bên trái. Để cây giữ được cân bằng, chúng ta sẽ thực hiện kỹ thuật quay phải như dưới đây:


*

Như hình minh họa, nút không cân bằng sẽ trở thành cây con bên phải của cây con bên trái của nó khi ta thực hiện kỹ thuật quay phải.

Xem thêm: Từ Điển Anh Việt " Freely Là Gì ?, Từ Điển Anh Free Or Freely

Kỹ thuật quay trái-phải cây AVL

Kỹ thuật quay ghép là phức tạp hơn so với 2 kỹ thuật quay đơn như đã giới thiệu ở trên. Để hiểu về kỹ thuật quay ghép này nhanh hơn, bạn cần phải ghi chú mỗi một hành động được thực hiện trong khi thực hiện kỹ thuật quay. Một kỹ thuật quay trái-phải chính là sự kết hợp của kỹ thuật quay trái được theo sau bởi kỹ thuật quay phải.

Trạng tháiHành động

*

Một loại kỹ thuật quay ghép khác đó chính là kỹ thuật quay phải-trái. Kỹ thuật này là sự kết hợp của kỹ thuật quay phải được theo sau bởi kỹ thuật quay trái.

Trạng tháiHành động

Một nút đã được thêm vào trong cây con ở bên trái của cây con bên phải. Điều này đã làm cho nút A trở nên không cân bằng bởi vì khi đó hiệu số (Balance Factor) là 2.

Đầu tiên, chúng ta cần thực hiện kỹ thuật quay phải đối với nút C, để làm cho C trở thành cây con bên phải của chính cây con bên trái B. Bây giờ, nút B đã trở thành cây con bên phải của nút A.

Bây giờ nút A vẫn chưa cân bằng bởi vì có xuất hiện cây con bên phải của cây con bên phải của chính nó. Do đó cần phải thực hiện kỹ thuật quay trái.

Xem thêm: Nhạc Hires Là Gì - Sự Khác Nhau Giữa Nhạc Mp3, Lossless Và Hi


Bây giờ cây đã ở trạng thái cân bằng.

kimsa88
cf68