C++第三十六弹---二叉搜索树的性能飞跃：AVL树原理与实现

#include <iostream>

struct AVLNode {
    int key;
    int height;
    AVLNode *left;
    AVLNode *right;
    AVLNode(int key) : key(key), height(0), left(nullptr), right(nullptr) {}
};

int getHeight(AVLNode *node) {
    return node ? node->height : 0;
}

AVLNode* rightRotate(AVLNode *p) {
    AVLNode *q = p->left;
    AVLNode *r = q->right;

    q->right = p;
    p->left = r;

    p->height = std::max(getHeight(p->left), getHeight(p->right)) + 1;
    q->height = std::max(getHeight(q->left), getHeight(q->right)) + 1;

    return q;
}

AVLNode* leftRotate(AVLNode *p) {
    AVLNode *q = p->right;
    AVLNode *r = q->left;

    q->left = p;
    p->right = r;

    p->height = std::max(getHeight(p->left), getHeight(p->right)) + 1;
    q->height = std::max(getHeight(q->left), getHeight(q->right)) + 1;

    return q;
}

AVLNode* insert(AVLNode *node, int key) {
    if (node == nullptr) {
        return new AVLNode(key);
    }

    if (key < node->key) {
        node->left = insert(node->left, key);
        if (getHeight(node->left) - getHeight(node->right) == 2) {
            if (key < node->left->key) {
                node = rightRotate(node);
            } else {
                node->left = leftRotate(node->left);
                node = rightRotate(node);
            }
        }
    } else {
        node->right = insert(node->right, key);
        if (getHeight(node->right) - getHeight(node->left) == 2) {
            if (key > node->right->key) {
                node = leftRotate(node);
            } else {
                node->right = rightRotate(node->right);
                node = leftRotate(node);
            }
        }
    }

    node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1;
    return node;
}

int main() {
    AVLNode *root = nullptr;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    // 此时，AVL树的根节点的键值应为30
    std::cout << "Root key after insertions: " << root->key << std::endl;
    return 0;
}