Cài đặt cây AVL (AVL Tree) trong C++

Cây AVL là cây tìm kiếm nhị phân tự cân bằng: chênh lệch chiều cao hai cây con của mọi nút ≤ 1. Các phép xoay (rotation) duy trì tính cân bằng sau chèn/xóa.

Các phép xoay

• LL (Left-Left): Xoay phải đơn.
• RR (Right-Right): Xoay trái đơn.
• LR (Left-Right): Xoay trái nút con trái, rồi xoay phải nút cha.
• RL (Right-Left): Xoay phải nút con phải, rồi xoay trái nút cha.

Ví dụ minh họa (chèn, duyệt, hiển thị)

#include <iostream>
#include <algorithm>
using namespace std;

struct Node { int key; Node *left, *right; };

class AVL {
    Node *root = nullptr;
    int height(Node *n) { return n ? max(height(n->left), height(n->right)) + 1 : 0; }
    int balanceFactor(Node *n) { return height(n->left) - height(n->right); }

    Node* rotateRight(Node *y) {
        Node *x = y->left; y->left = x->right; x->right = y;
        cout << "Right Rotation "; return x;
    }
    Node* rotateLeft(Node *x) {
        Node *y = x->right; x->right = y->left; y->left = x;
        cout << "Left Rotation "; return y;
    }
    Node* balance(Node *n) {
        int bf = balanceFactor(n);
        if (bf > 1) {
            if (balanceFactor(n->left) >= 0) return rotateRight(n);
            else { n->left = rotateLeft(n->left); return rotateRight(n); }
        } else if (bf < -1) {
            if (balanceFactor(n->right) <= 0) return rotateLeft(n);
            else { n->right = rotateRight(n->right); return rotateLeft(n); }
        }
        return n;
    }
    Node* insert(Node *n, int key) {
        if (!n) return new Node{key, nullptr, nullptr};
        if (key < n->key) n->left = insert(n->left, key);
        else n->right = insert(n->right, key);
        return balance(n);
    }
    void inorder(Node *n) { if (n) { inorder(n->left); cout << n->key << ' '; inorder(n->right); } }
    void preorder(Node *n) { if (n) { cout << n->key << ' '; preorder(n->left); preorder(n->right); } }
    void postorder(Node *n) { if (n) { postorder(n->left); postorder(n->right); cout << n->key << ' '; } }
    void display(Node *n, int level) {
        if (!n) return;
        display(n->right, level+1);
        if (n == root) cout << "Root -> ";
        for (int i=0; ikey << endl;
        display(n->left, level+1);
    }
public:
    void insert(int key) { root = insert(root, key); }
    void inorder() { inorder(root); cout << endl; }
    void preorder() { preorder(root); cout << endl; }
    void postorder() { postorder(root); cout << endl; }
    void display() { display(root, 0); }
};

int main() {
    AVL tree;
    for (int x : {13,10,15,5,11,4,8,16,14,3,7,9,52}) tree.insert(x);
    cout << "Inorder: "; tree.inorder();
    cout << "Preorder: "; tree.preorder();
    cout << "Postorder: "; tree.postorder();
    cout << "Tree:\n"; tree.display();
}

Kết quả (đoạn)

Inorder: 3 4 5 7 8 9 10 11 13 14 15 16 52
Preorder: 10 5 4 3 8 7 9 13 11 15 14 16 52
Postorder: 3 4 7 9 8 5 11 14 16 15 13 10
Tree:
            52
       16
            15
                14
    13
            11
       10
            9
                8
       5
                7
            4
                3