Cây AVL - Sự cân bằng trong cây tìm kiếm nhị phân

Dữ liệu trong cây tìm kiếm nhị phân (BST) có thể được sắp xếp theo một thứ tự cụ thể như tăng dần hoặc giảm dần. Tuy nhiên, khi dữ liệu không được sắp xếp, hiệu suất của cây BST sẽ giống như thuật toán tìm kiếm tuyến tính với độ phức tạp O(n). Điều cần thiết ở đây là cân bằng cây tìm kiếm nhị phân để đảm bảo hiệu suất tốt nhất.

Cây AVL (được viết tắt từ tên của các nhà phát minh Adelson, Velski và Landis) là một loại 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ây con bên trái và cây con bên phải, và đảm bảo rằng hiệu số giữa chúng không vượt quá 1, gọi là "Balance Factor" (Nhân tố cân bằng).

Dưới đây là một số ví dụ minh họa về cây AVL. Cây đầu tiên là cân bằng, trong khi 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 nút C có độ cao là 2 và cây con bên phải có độ cao là 0, do đó hiệu số là 2. Tương tự, trong cây thứ ba, cây con bên phải của nút A có độ cao là 2 và cây con bên trái có độ cao là 0, lại có hiệu số là 2. Trong khi cây AVL chỉ chấp nhận hiệu số là 1.

Nếu hiệu số giữa độ cao của cây con bên trái và cây con bên phải vượt quá 1, cây sẽ bị mất cân bằng. Các kỹ thuật quay AVL được sử dụng để cân bằng cây như sau:

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

Nếu một nút được chèn vào cây con bên phải của cây con bên phải, kỹ thuật quay trái đơn có thể được thực hiện để cân bằng cây. Trong hình minh họa dưới đây, nút A trở nên không cân bằng khi một nút C được chèn vào cây con bên phải của nút A. Sử dụng kỹ thuật quay trái, nút A sẽ trở thành cây con bên trái của nút B.

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

Cây AVL sẽ mất 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ân bằng cây, chúng ta sử dụng kỹ thuật quay phải. Như hình minh họa dưới đây, 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 trái-phải trong cây AVL là một quá trình kết hợp hai kỹ thuật quay. Để hiểu kỹ thuật này, ta cần ghi nhớ từng hành động được thực hiện trong quá trình quay. Kỹ thuật này bao gồm kỹ thuật quay trái theo sau bởi kỹ thuật quay phải.

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

Một loại kỹ thuật quay 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 và kỹ thuật quay trái.

Với các kỹ thuật quay này, cây AVL có thể tự động cân bằng, đảm bảo sự hiệu quả và hiệu suất tốt nhất cho các thao tác tìm kiếm và thao tác trên cây tìm kiếm nhị phân.