Giới thiệu về cây AVL

Cây tìm kiếm nhị phân (BST) có nhược điểm lớn khi bị mất cân bằng — trong trường hợp xấu nhất, nó suy biến thành danh sách liên kết, khiến độ phức tạp thao tác tìm kiếm, chèn, xóa lên tới O(N). Để khắc phục điều này, hai nhà toán học người Nga G.M. Adelson-Velskii và E.M. Landis đã đề xuất một cấu trúc gọi là cây AVL, đảm bảo độ cao của cây luôn duy trì ở mức O(log N) thông qua việc kiểm soát chặt chẽ sự chênh lệch chiều cao giữa các cây con.

Một cây nhị phân được coi là cây AVL nếu thỏa mãn hai điều kiện sau:

1. Mỗi nút trong cây đều có cây con trái và phải là cây AVL.
2. Chênh lệch chiều cao giữa cây con phải và cây con trái của mọi nút không vượt quá 1 (theo giá trị tuyệt đối).

Cấu trúc nút trong cây AVL

So với cây BST thông thường, mỗi nút trong cây AVL cần thêm hai thông tin quan trọng:

• Yếu tố cân bằng (balance factor - bf): Được tính bằng công thức chiều_cao(phải) - chiều_cao(trái). Giá trị này chỉ nhận ba khả năng: -1, 0, hoặc 1.
• Con trỏ cha (parent pointer): Giúp di chuyển ngược lên trên để cập nhật yếu tố cân bằng và phát hiện mất cân bằng nhanh chóng.

Do đó, cấu trúc cây AVL là dạng ba nhánh (trái, phải, cha). Lớp cây AVL chỉ cần quản lý một biến thành viên là con trỏ gốc _root.

template<typename K, typename V>
struct AVLNode {
    K _key;
    V _value;
    int _bf; // balance factor
    AVLNode* _left;
    AVLNode* _right;
    AVLNode* _parent;

    AVLNode(const K& key, const V& value)
        : _key(key), _value(value), _bf(0)
        , _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

Cập nhật yếu tố cân bằng sau chèn

Khi chèn một nút mới vào cây, ta cần cập nhật yếu tố cân bằng dọc theo đường đi từ nút mới đến gốc:

• Nếu nút mới nằm ở phía trái của một nút cha, thì yếu tố cân bằng của nút cha giảm đi 1 (_bf--).
• Nếu nút mới nằm ở phía phải, yếu tố cân bằng tăng lên 1 (_bf++).

Việc dùng con trỏ _parent giúp duyệt ngược lên rất hiệu quả mà không cần duyệt lại toàn bộ cây.

Phát hiện và xử lý mất cân bằng

Sau khi cập nhật _bf, xét từng nút cha dọc đường đi:

• Nếu _bf == 0: Chiều cao của cây con tại nút này đã tăng, nhưng bản thân nút vẫn cân bằng. Tiếp tục kiểm tra nút cha tiếp theo.
• Nếu _bf == 1 hoặc -1: Cây con tại nút này chưa mất cân bằng, nhưng chiều cao tổng thể đã tăng → cần tiếp tục kiểm tra lên trên.
• Nếu _bf == 2 hoặc -2: Mất cân bằng xảy ra → thực hiện phép xoay để khôi phục.

Xoay cây để khôi phục cân bằng

Tùy theo cấu hình mất cân bằng, ta áp dụng một trong bốn loại xoay:

1. Xoay trái đơn (Left Rotation)

Dùng khi cây con phải quá sâu: parent->_bf == 2 && subR->_bf == 1.

Các bước:

1. Gán subRL = subR->_left.
2. Xoay: subR->_left = parent, parent->_right = subRL.
3. Cập nhật con trỏ cha: parent->_parent = subR, nếu subRL tồn tại thì subRL->_parent = parent.
4. Cập nhật gốc nếu parent là nút gốc.

void rotateLeft(AVLNode*& parent) {
    AVLNode* subR = parent->_right;
    AVLNode* subRL = subR->_left;

    parent->_right = subRL;
    if (subRL) subRL->_parent = parent;

    subR->_left = parent;
    AVLNode* ppNode = parent->_parent;
    parent->_parent = subR;

    if (!ppNode) {
        _root = subR;
        subR->_parent = nullptr;
    } else {
        if (ppNode->_left == parent) ppNode->_left = subR;
        else ppNode->_right = subR;
        subR->_parent = ppNode;
    }

    parent->_bf = subR->_bf = 0;
}

2. Xoay phải đơn (Right Rotation)

Dùng khi cây con trái quá sâu: parent->_bf == -2 && subL->_bf == -1.

Thao tác tương tự như xoay trái, nhưng đổi vai trò trái/phải.

void rotateRight(AVLNode*& parent) {
    AVLNode* subL = parent->_left;
    AVLNode* subLR = subL->_right;

    parent->_left = subLR;
    if (subLR) subLR->_parent = parent;

    subL->_right = parent;
    AVLNode* ppNode = parent->_parent;
    parent->_parent = subL;

    if (!ppNode) {
        _root = subL;
        subL->_parent = nullptr;
    } else {
        if (ppNode->_left == parent) ppNode->_left = subL;
        else ppNode->_right = subL;
        subL->_parent = ppNode;
    }

    parent->_bf = subL->_bf = 0;
}

3. Xoay kép Trái-Phải (Left-Right Rotation)

Xảy ra khi: parent->_bf == -2 && subL->_bf == 1 — dạng "gấp khúc".

Cách xử lý: Thực hiện xoay trái tại subL, rồi xoay phải tại parent.

Lưu ý đặc biệt: Sau khi xoay, giá trị _bf của các nút phụ thuộc vào yếu tố cân bằng của nút trung gian subLR:

• Nếu subLR->_bf == 0: cả ba nút đều về 0.
• Nếu subLR->_bf == -1: parent->_bf = 1, subL->_bf = 0.
• Nếu subLR->_bf == 1: parent->_bf = 0, subL->_bf = -1.

4. Xoay kép Phải-Trái (Right-Left Rotation)

Ngược lại với LR: parent->_bf == 2 && subR->_bf == -1.

Thực hiện xoay phải tại subR, rồi xoay trái tại parent.

Tương tự, giá trị _bf sau cùng phụ thuộc vào subRL->_bf.

Kiểm tra tính hợp lệ của cây AVL

Để xác minh cây vẫn duy trì tính chất AVL, ta viết hàm kiểm tra đệ quy:

• Tính chiều cao từng cây con.
• Kiểm tra chênh lệch chiều cao có khớp với _bf không.
• Đảm bảo _bf nằm trong khoảng [-1, 1].

int getHeight(AVLNode* node) {
    if (!node) return 0;
    return std::max(getHeight(node->_left), getHeight(node->_right)) + 1;
}

bool isValidAVL(AVLNode* root) {
    if (!root) return true;

    int leftH = getHeight(root->_left);
    int rightH = getHeight(root->_right);
    int balance = rightH - leftH;

    if (balance != root->_bf || balance < -1 || balance > 1) {
        std::cout << "Loi can bang tai khoa: " << root->_key << "\n";
        return false;
    }

    return std::abs(balance) <= 1
        && isValidAVL(root->_left)
        && isValidAVL(root->_right);
}

Đánh giá và ứng dụng

Cây AVL là một cấu trúc cân bằng tuyệt đối, luôn đảm bảo thời gian truy vấn là O(log N). Nhờ vậy, nó rất phù hợp cho các hệ thống yêu cầu truy vấn nhanh và ổn định. Tuy nhiên, do chi phí tái cân bằng cao (nhiều lần xoay), các thao tác chèn/xóa có thể chậm hơn so với các cấu trúc linh hoạt hơn như cây đỏ-đen. Trong thực tế, cây AVL thường được dùng trong các cơ sở dữ liệu nội bộ hoặc hệ thống nhúng nơi độ trễ truy vấn là yếu tố then chốt.