AVL树构建和维护

1. AVL树的定义

AVL树是一种自平衡二叉搜索树，得名于其发明者G. M. Adelson-Velsky和E. M. Landis。

AVL树的每个节点都存储一个平衡因子，该因子表示该节点左子树和右子树的高度差。

AVL树的平衡因子必须满足以下条件：

对于每个节点，其左子树和右子树的高度差不能超过1。
对于每个节点，其左子树和右子树的高度差不能超过1。

2. AVL树的构建和维护

旋转法维护平衡

总体代码

#include <iostream>
#include <algorithm>

using namespace std;

// AVL树节点结构
struct AVLNode {
    int value;
    AVLNode* left;
    AVLNode* right;
    int height; // 节点的高度

    AVLNode(int val) : value(val), left(nullptr), right(nullptr), height(1) {}
};

// 获取节点的高度
int getHeight(AVLNode* node) {
    if (node == nullptr) return 0;
    return node->height;
}

// 获取节点的平衡因子
int getBalanceFactor(AVLNode* node) {
    if (node == nullptr) return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// 更新节点的高度
void updateHeight(AVLNode* node) {
    if (node != nullptr) {
        node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    }
}

// 右旋操作
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    // 进行右旋
    x->right = y;
    y->left = T2;

    // 更新节点的高度
    updateHeight(y);
    updateHeight(x);

    return x;
}

// 左旋操作
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    // 进行左旋
    y->left = x;
    x->right = T2;

    // 更新节点的高度
    updateHeight(x);
    updateHeight(y);

    return y;
}

// 插入操作
AVLNode* insert(AVLNode* node, int value) {
    // 1. 执行普通的二叉搜索树插入
    if (node == nullptr) return new AVLNode(value);

    if (value < node->value) {
        node->left = insert(node->left, value);
    } else if (value > node->value) {
        node->right = insert(node->right, value);
    } else {
        return node; // 不允许重复值
    }

    // 2. 更新当前节点的高度
    updateHeight(node);

    // 3. 获取当前节点的平衡因子
    int balance = getBalanceFactor(node);

    // 4. 进行旋转调整，恢复平衡

    // 左左情况 (左子树的左子树过高)
    if (balance > 1 && value < node->left->value) {
        return rightRotate(node);
    }

    // 右右情况 (右子树的右子树过高)
    if (balance < -1 && value > node->right->value) {
        return leftRotate(node);
    }

    // 左右情况 (左子树的右子树过高)
    if (balance > 1 && value > node->left->value) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右左情况 (右子树的左子树过高)
    if (balance < -1 && value < node->right->value) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 5. 返回当前节点
    return node;
}

// 中序遍历打印AVL树
void inOrderTraversal(AVLNode* root) {
    if (root != nullptr) {
        inOrderTraversal(root->left);
        cout << root->value << " ";
        inOrderTraversal(root->right);
    }
}

// 主程序
int main() {
    AVLNode* root = nullptr;

    // 插入节点
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);  // 这将导致右右不平衡，需要左旋
    root = insert(root, 25);  // 这将导致左右不平衡，需要先左旋再右旋
    root = insert(root, 5);   // 这将导致左左不平衡，需要右旋
    root = insert(root, 15);

    // 打印中序遍历
    cout << "In-order traversal of the AVL tree: ";
    inOrderTraversal(root);
    cout << endl;

    return 0;
}