Cây AVL - AVL Tree (Cấu trúc dữ liệu và giải thuật)

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

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

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ái
• Kỹ thuật quay phải
• Kỹ thuật quay trái-phải
• Kỹ 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.

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ái	Hành động
	Một nút đã được thêm vào trong cây con ở bên phải của cây con bên trái. Điều này đã giúp nút C trở nên không còn cân bằng. Với tình huống này, cây AVL có thể thực hiện các kỹ thuật quay trái-phải.
	Đầu tiên, thực hiện phép quay trái trên cây con ở bên trái của C. Điều này đã làm cho A trở thành cây con ở bên trái của B.
	Bây giờ nút C vẫn chưa cân bằng, đó là vì đã xuất hiện cây con bên trái của cây con bên trái.
	Bây giờ chúng ta sẽ thực hiện kỹ thuật quay phải để giúp cho B trở thành nút gốc mới của cây này. Nút C bây giờ đã trở thành cây con bên phải của chính cây conở bên trái của nó.
	Bây giờ cây đã cân bằng.

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