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

Cây AVL là gì?

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

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

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

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

Trong cây thứ hai, cây con bên trái của C có độ cao là 2 và cây con bên phải có độ cao là 0, do đó hiệu số là 2. Trong cây thứ ba, cây con bên phải của A có độ cao là 2 và cây con bên trái có độ cao là 0, do đó hiệu số 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 trái và cây con bên phải là lớn hơn 1 thì cây được cân bằng bởi sử dụng một số kỹ thuật quay AVL được trình bày 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ể thực hiện 4 loại kỹ thuật quay 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

Hai kỹ thuật quay đầu tiên là các kỹ thuật quay đơn và hai 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 từng kỹ thuật quay với hình minh họa đơ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 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 có thể thực hiện kỹ thuật quay trái đơn như sau:

Trong hình minh họa trên, nút A trở nên không cân bằng khi một nút (nút C) được chèn vào cây con bên phải của cây con bên phải của nút A. Chúng ta thực hiện kỹ thuật quay trái để làm 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 trở nên không cân bằng nếu một nút được chèn vào cây con bên trái của cây con bên trái. Để cây cân bằng, chúng ta thực hiện kỹ thuật quay phải như sau:

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ó bằng kỹ thuật quay phải.

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

Kỹ thuật quay ghép là khá phức tạp so với hai kỹ thuật quay đơn vừa giới thiệu trên. Để hiểu kỹ thuật quay này nhanh hơn, bạn cần phải ghi chú từng hành động được thực hiện trong khi quay. Một kỹ thuật quay trái-phải 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 chèn vào trong cây con bên phải của cây con bên trái. Điều này làm nút C trở nên không cân bằng. Với tình huống này, cây AVL có thể thực hiện 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 không cân bằng, đó là do 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 để làm 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

Một loại kỹ thuật quay ghép khác 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ái	Hành động
	Một nút đã được chèn 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 nút A trở nên không cân bằng bởi vì hiệu số (Balance Factor) là 2.
	Đầu tiên, chúng ta thực hiện kỹ thuật quay phả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 không cân bằng bởi vì xuất hiện cây con bên phải của cây con bên phải của nó. Do đó cần phải thực hiện một kỹ thuật quay trái.
	Một kỹ thuật quay trái được thực hiện làm cho B trở thành nút gốc mới của cây con. Nút A trở thành cây con bên trái của cây con B bên phải của nó.
	Bây giờ cây đã cân bằng.

Theo Tutorialspoint

Bài trước: Cây tìm kiếm nhị phân (Binary Search Tree)

Bài tiếp: Cây khung (Spanning Tree) trong cấu trúc dữ liệu và giải thuật