【C++进阶学习】第七弹——AVL树——树形结构存储数据的经典模块

#include <iostream>
 
using namespace std;
 
class AVLTreeNode {
public:
    int key;
    int height;
    AVLTreeNode *left;
    AVLTreeNode *right;
 
    AVLTreeNode(int key) : key(key), height(0), left(nullptr), right(nullptr) {}
};
 
class AVLTree {
public:
    AVLTreeNode *root;
 
    AVLTree() : root(nullptr) {}
 
    int Height(AVLTreeNode *node) {
        if (node == nullptr) {
            return 0;
        }
        return node->height;
    }
 
    int GetBalance(AVLTreeNode *node) {
        if (node == nullptr) {
            return 0;
        }
        return Height(node->left) - Height(node->right);
    }
 
    AVLTreeNode* SingleRotateWithLeft(AVLTreeNode *node) {
        AVLTreeNode *temp = node->left;
        node->left = temp->right;
        temp->right = node;
 
        // 更新高度
        node->height = max(Height(node->left), Height(node->right)) + 1;
        temp->height = max(Height(temp->left), node->height) + 1;
 
        return temp;
    }
 
    AVLTreeNode* SingleRotateWithRight(AVLTreeNode *node) {
        AVLTreeNode *temp = node->right;
        node->right = temp->left;
        temp->left = node;
 
        // 更新高度
        node->height = max(Height(node->left), Height(node->right)) + 1;
        temp->height = max(node->height, Height(temp->right)) + 1;
 
        return temp;
    }
 
    AVLTreeNode* DoubleRotateWithLeft(AVLTreeNode *node) {
        // 先对node的左子节点进行右旋转
        node->left = SingleRotateWithRight(node->left);
 
        // 再对node进行左旋转
        return SingleRotateWithLeft(node);
    }
 
    AVLTreeNode* DoubleRotateWithRight(AVLTreeNode *node) {
        // 先对node的右子节点进行左旋转
        node->right = SingleRotateWithLeft(node->right);
 
        // 再对node进行右旋转
        return SingleRotateWithRight(node);
    }
 
    AVLTreeNode* Insert(AVLTreeNode *node, int key) {
        if (node == nullptr) {
            return new AVLTreeNode(key);
        }
 
        if (key < node->key) {
            node->left = Insert(node->left, key);
 
            // 如果插入后不平衡，则需要旋转
            if (GetBalance(node) == 2) {
                if (key < node->left->key) {
                    node = SingleRotateWithLeft(node);
                } else {
                    node = DoubleRotateWithLeft(node);
                }
            }
        } else if (key > node->key) {
            node->right = Insert(node->right, key);
 
            // 如果插入后不平衡，则需要旋转
            if (G