【C++的剃刀】我不允许你还不会AVL树

AVL树是一种自平衡二叉查找树，它确保任一节点的左右子树高度之差最多为1。在AVL树中，插入和删除操作可能导致树失去平衡，因此需要旋转来重新平衡这棵树。

以下是一个简单的AVL树插入操作的示例代码：

#include <iostream>
 
struct AVLNode {
    int key;
    AVLNode *left, *right;
    int height;
 
    AVLNode(int key) : key(key), left(nullptr), right(nullptr), height(0) {}
};
 
class AVLTree {
    AVLNode *root;
 
    int height(AVLNode *node) {
        return node ? node->height : 0;
    }
 
    AVLNode* rightRotate(AVLNode* node) {
        AVLNode* temp = node->left;
        node->left = temp->right;
        temp->right = node;
 
        node->height = std::max(height(node->left), height(node->right)) + 1;
        temp->height = std::max(height(temp->left), height(temp->right)) + 1;
 
        return temp;
    }
 
    AVLNode* leftRotate(AVLNode* node) {
        AVLNode* temp = node->right;
        node->right = temp->left;
        temp->left = node;
 
        node->height = std::max(height(node->left), height(node->right)) + 1;
        temp->height = std::max(height(temp->left), height(temp->right)) + 1;
 
        return temp;
    }
 
    AVLNode* insert(AVLNode* node, int key) {
        if (node == nullptr) {
            return new AVLNode(key);
        }
 
        if (key < node->key) {
            node->left = insert(node->left, key);
        } else if (key > node->key) {
            node->right = insert(node->right, key);
        } else {
            // Key already exists, do nothing.
            return node;
        }
 
        // After insertion, check if the tree is unbalanced and
        // balance it.
        int balance = height(node->left) - height(node->right);
 
        // Left left case
        if (balance > 1 && key < node->left->key) {
            return rightRotate(node);
        }
 
        // Right right case
        if (balance < -1 && key > node->right->key) {
            return leftRotate(node);
        }
 
        // Left right case
        if (balance > 1 && key > node->left->key) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
 
        // Right left case
        if (balance < -1 && key < node->right->key) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
 
        // Update the height of the node.
        node->height = std::max(height(node->left), height(node->right)) + 1;
 
        return node;
    }
 
public:
    AVLTree() : root(nullptr) {}