⚖️ Cây AVL

Trang trước đã chỉ ra điểm yếu của BST thông thường: nếu dữ liệu được chèn vào theo một thứ tự “xấu” (ví dụ đã sắp sẵn tăng dần), cây sẽ lệch hẳn về một phía, chiều cao tiến gần tới n thay vì log n, và mọi thao tác tìm/thêm/xóa tụt từ O(log n) xuống O(n) - mất sạch lợi thế mà BST hứa hẹn.

Cây AVL (đặt theo tên hai nhà phát minh Adelson-Velsky và Landis) giải quyết vấn đề này bằng cách tự động điều chỉnh hình dạng sau mỗi lần chèn hoặc xóa, đảm bảo cây không bao giờ lệch quá mức - nhờ vậy chiều cao luôn ở cỡ O(log n), bất kể bạn chèn dữ liệu theo thứ tự nào.

Hệ số cân bằng (balance factor)

Để biết một node có “lệch” hay không, AVL tree gắn cho mỗi node một con số gọi là hệ số cân bằng: chiều cao cây con trái trừ chiều cao cây con phải.

def height(node):
    return node.height if node else -1   # node rỗng có height = -1

def balance_factor(node):
    if node is None:
        return 0
    return height(node.left) - height(node.right)

Một cây được coi là AVL hợp lệ khi hệ số cân bằng của mọi node đều nằm trong khoảng [-1, 1]. Hễ một node nào đó có hệ số cân bằng là -2 hoặc 2 sau khi chèn/xóa, cây cần được “sửa lại” ngay lập tức bằng phép xoay (rotation).

Phép xoay - sửa lệch mà không phá vỡ tính chất BST

Ý tưởng của xoay cây: đổi vai trò cha-con giữa hai node liền kề, chuyển bớt “trọng lượng” từ nhánh đang nặng sang nhánh đang nhẹ, nhưng vẫn giữ nguyên thứ tự trái-nhỏ-phải-lớn của BST (thứ tự inorder của cây không đổi trước và sau khi xoay).

Có 4 tình huống mất cân bằng, ứng với 4 cách xoay:

1. Lệch trái-trái (LL) - nhánh trái của nhánh trái quá nặng. Xử lý bằng xoay phải (right rotation): đưa con trái lên làm gốc mới, gốc cũ tụt xuống làm con phải của nó.

def rotate_right(node):
    child = node.left
    node.left = child.right   # cây con phải của child "dời chỗ" sang bên node
    child.right = node
    update_height(node)       # cập nhật height cho node TRƯỚC (nó ở dưới sau khi xoay)
    update_height(child)
    return child               # child trở thành gốc mới của cây con này

2. Lệch phải-phải (RR) - đối xứng với LL, xử lý bằng xoay trái (left rotation), hoàn toàn tương tự nhưng đổi trái ↔ phải.

3. Lệch trái-phải (LR) - nhánh trái nặng, nhưng phần nặng nằm ở con phải của nhánh trái đó. Xoay phải một lần không giải quyết được - cần xoay trái nhánh con trái trước (biến nó về dạng LL), rồi mới xoay phải toàn bộ.

4. Lệch phải-trái (RL) - đối xứng với LR: xoay phải nhánh con phải trước, rồi xoay trái toàn bộ.

def rotate(node):
    bf = balance_factor(node)
    if bf > 1:                                  # lệch trái
        if balance_factor(node.left) >= 0:
            return rotate_right(node)             # LL
        else:
            node.left = rotate_left(node.left)    # LR: sửa con trái trước
            return rotate_right(node)
    elif bf < -1:                                # lệch phải
        if balance_factor(node.right) <= 0:
            return rotate_left(node)              # RR
        else:
            node.right = rotate_right(node.right)  # RL: sửa con phải trước
            return rotate_left(node)
    return node   # đã cân bằng, không cần xoay

Khi nào cần xoay?

Sau mỗi lần chèn hoặc xóa một node, hàm insert/remove phải đi ngược từ node vừa thay đổi lên tới gốc, cập nhật height và kiểm tra balance_factor tại từng node trên đường đi - hễ phát hiện một node lệch (|balance_factor| > 1) thì gọi rotate() để sửa ngay tại đó. Vì chiều cao cây AVL luôn là O(log n), đường đi này cũng chỉ dài O(log n), nên chèn/xóa trên AVL tree vẫn giữ nguyên độ phức tạp O(log n) - chỉ tốn thêm một hằng số công việc cho việc xoay.

AVL tree đổi lấy gì?

So với BST thường, AVL tree đảm bảo O(log n) cho mọi trường hợp (kể cả worst case), đổi lại mỗi node phải lưu thêm trường height, và mỗi lần chèn/xóa tốn thêm công sức kiểm tra + xoay cây. Trong thực tế, nếu dữ liệu chèn vào tương đối ngẫu nhiên, một BST thường đã đủ tốt; AVL tree phát huy giá trị rõ nhất khi cần đảm bảo hiệu năng ổn định bất kể thứ tự dữ liệu đầu vào - ví dụ khi dùng làm chỉ mục (index) trong cơ sở dữ liệu hoặc hệ thống cần độ trễ dự đoán được.