Cây AVL là một dạng cây tìm kiếm nhị phân tự cân bằng, được phát minh bởi Georgy Adelson-Velsky và Evgenii Landis vào năm 1962. Cây AVL đảm bảo độ cao của cây luôn ở mức logarit so với số nút, giúp các thao tác tìm kiếm, chèn và xóa đều chạy trong O(log n). Điều này khiến cây AVL trở thành lựa chọn phổ biến trong các hệ thống cần độ trễ thấp và hiệu năng dự đoán được.
Tại sao cần cây tự cân bằng?
Cây tìm kiếm nhị phân thông thường (BST) có nhược điểm: nếu dữ liệu đầu vào đã được sắp xếp hoặc gần như đã sắp xếp, cây sẽ biến dạng thành một danh sách liên kết — độ cao O(n). Khi đó tìm kiếm mất O(n) thay vì O(log n), hiệu năng sụt giảm nghiêm trọng. Cây AVL giải quyết bài toán này bằng cách duy trì yếu tố cân bằng (balance factor) tại mỗi nút, được định nghĩa là hiệu độ cao giữa cây con trái và cây con phải. Yếu tố này chỉ được phép nhận giá trị -1, 0 hoặc 1.
Cơ chế xoay (Rotation)
Khi chèn hoặc xóa nút làm vi phạm điều kiện cân bằng, cây AVL thực hiện một trong bốn loại xoay để khôi phục:
- Xoay phải (Right Rotation – LL): Nút bị lệch trái-trái, xoay nhánh phải của nút con trái lên làm gốc mới.
- Xoay trái (Left Rotation – RR): Nút bị lệch phải-phải, đối xứng với LL.
- Xoay trái-phải (Left-Right Rotation – LR): Nút bị lệch trái-phải, xoay trái nút con trái rồi xoay phải nút gốc.
- Xoay phải-trái (Right-Left Rotation – RL): Nút bị lệch phải-trái, xoay phải nút con phải rồi xoay trái nút gốc.
Mỗi xoay chỉ tác động cục bộ trên vài nút, chi phí O(1). Do đó độ phức tạp chèn/xóa vẫn giữ nguyên O(log n).
So sánh với cây đỏ-đen (Red-Black Tree)
Cây đỏ-đen cũng là cây tự cân bằng nhưng cho phép độ cao tối đa 2·log₂(n+1), nới lỏng điều kiện cân bằng hơn AVL. Ưu điểm: ít xoay hơn khi chèn/xóa, nhanh hơn thực tế trong các thư viện chuẩn (std::map, TreeMap, dict của Python). Cây AVL cân bằng chặt hơn, độ cao thực tế nhỏ hơn — ưu thế khi thao tác tìm kiếm chiếm đa số (read-heavy workload).
Ứng dụng thực tế
- Hệ thống cơ sở dữ liệu: chỉ mục B-tree biến thể dùng ý tưởng cân bằng tương tự.
- Bộ nhớ ảo: Linux kernel dùng cây đỏ-đen (rb-tree) để quản lý vùng nhớ, nhưng AVL vẫn xuất hiện trong các module cần độ chính xác cao.
- Trình biên dịch: bảng ký hiệu (symbol table) thường triển khai bằng cây cân bằng để tra cứu định danh O(log n).
- Game development: quản lý thực thể theo tọa độ (quad-tree, k-d tree) — biến thể của cây cân bằng.
Cây AVL trong thư viện chuẩn và các ngôn ngữ
Hầu hết ngôn ngữ lập trình đều có sẵn cấu trúc câu cân bằng trong thư viện chuẩn, thường dựa trên cây đỏ-đen vì hiệu năng thực tế tốt hơn. Trong C++, std::map và std::set dùng cây đỏ-đen; trong Java, TreeMap và TreeSet cũng vậy; trong Python, dict dùng bảng băm chứ không phải cây. Tuy vậy, cây AVL vẫn xuất hiện trong các thư viện chuyên dụng cho bản đồ, chỉ mục văn bản và cơ sở dữ liệu nhúng, nơi mà thời gian tìm kiếm cực ngắn quan trọng hơn chi phí ghi thêm một chút.
Do đó khi làm dự án thực tế, câu hỏi đầu tiên nên là: đã có sẵn cấu trúc dữ liệu nào trong thư viện chuẩn chưa? Tự viết cây AVL chỉ đáng làm khi bạn cần thêm chỉ số phụ, so sánh theo tiêu chí riêng, hoặc muốn hiểu sâu thuật toán để phỏng vấn hay thi đấu.
Chi phí bộ nhớ và hằng số thực tế
Kiểm tra cân bằng tại mỗi nút tốn thêm vài phép so sánh cho mỗi lần chèn hoặc xóa. Đổi lại, cây AVL có số lần xoay ít hơn cây đỏ-đen trong nhiều trường hợp, và chiều cao nhỏ hơn nên cache CPU được tận dụng tốt hơn. Với bộ nhớ là yếu tố giới hạn — ví dụ trên thiết bị nhúng hay hệ thống chỉ vài trăm kilobyte RAM — cây AVL thường là lựa chọn hợp lý hơn vì không cần thêm trường màu cho mỗi nút.
Triển khai minh họa trong Python
Dưới đây là khung mã đơn giản cho nút AVL và xoay phải:
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def height(node):
return node.height if node else 0
def right_rotate(y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(height(y.left), height(y.right))
x.height = 1 + max(height(x.left), height(x.right))
return x
Mã đầy đủ bao gồm cập nhật chiều cao, tính balance factor, và điều phối 4 trường hợp xoay. Bạn có thể tham khảo Wikipedia: AVL tree để xem pseudocode hoàn chỉnh.
Khi nào nên dùng cây AVL?
Chọn cây AVL khi: ứng dụng read-heavy (tìm kiếm nhiều hơn ghi), cần độ trễ tìm kiếm thấp nhất có thể, và kích thước dữ liệu vừa phải (vài chục nghìn đến vài triệu phần tử). Với ghi nhiều (write-heavy), cây đỏ-đen thường hiệu quả hơn nhờ ít xoay hơn. Đối với dữ liệu cực lớn trên đĩa, B-tree và biến thể (B+ tree, LSM tree) là lựa chọn chuẩn.
Tóm lại, cây AVL là minh chứng điển hình cho việc thêm một ràng buộc thông minh (yếu tố cân bằng -1..1) biến một cấu trúc dữ liệu cơ bản thành công cụ mạnh mẽ, dự đoán được hiệu năng. Hiểu rõ xoay cây giúp lập trình viên thiết kế thuật toán và hệ thống tốt hơn.
