Cây AVL: Giới thiệu
Bạn đã bao giờ tự hỏi xảy ra điều gì nếu dữ liệu đưa vào cây tìm kiếm nhị phân (BST) đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần? Điều này sẽ trông giống như hình dưới đây:
Nói chung, hiệu suất xấu nhất của cây tìm kiếm nhị phân (BST) gần như bằng các giải thuật tìm kiếm tuần tự, tức là Ο(n). Với dữ liệu thời gian thực, không thể dự đoán mẫu dữ liệu và tần suất của nó. Do đó, cần phải 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â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 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 minh họa ba cây, trong đó cây đầu tiên là cân bằng, cây thứ hai và thứ ba 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ố là 1.
Balance Factor = height(left-sutree) - height(right-sutree)
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 lớn hơn 1, cây sẽ được cân bằng bằng cách sử dụng các kỹ thuật quay AVL được trình bày dưới đây.
Kỹ thuật quay cây AVL
Để cây tự cân bằng, 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.
Tiếp theo, chúng ta sẽ tìm hiểu chi tiết về 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, 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à phức tạp hơn so với hai kỹ thuật quay đơn đã được giới thiệu. Để hiểu kỹ thuật này nhanh hơn, bạn cần ghi chú từng hành động được thực hiện khi quay. 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, 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 vì hiệu số (Balance Factor) bằng 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 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 dõi những bài viết tiếp theo để tìm hiểu thêm về các chủ đề khác trong cấu trúc dữ liệu và giải thuật.
