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

以下是一个简化版的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;
}

这段代码实现了AVL树的插入操作，包括单旋转和双旋转。在插入新键值后，会检查并进行必要的平衡调整。在主函数中，我们进行了几次插入操作，并输出了根节点的键值，以验证AVL树的性质。