移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——14.AVL树

AVL树是一种自平衡的二叉搜索树，由于其高度平衡的性质，使得AVL树在查找、插入和删除操作上具有良好的性能，可以在O(log n)的时间复杂度内完成这些操作。这种树的每个节点都有一个额外的属性“平衡因子”，用于保持树的平衡。

一、AVL树的定义

AVL树由乔治·阿德尔森-维尔斯基和叶甫根尼·兰波特于1962年发明。AVL树的每个节点的平衡因子是该节点左子树的高度减去右子树的高度。对于任意节点，平衡因子的取值范围为{-1, 0, 1}，这意味着AVL树的左右子树的高度差不能超过1。

二、AVL树的基本操作

1. 插入操作

在AVL树中插入一个节点时，如果插入后导致树不平衡，则需要进行旋转操作来恢复平衡。插入时分为以下几种情况：

• LL情况：在左子树的左侧插入，进行一次右旋转。
• RR情况：在右子树的右侧插入，进行一次左旋转。
• LR情况：在左子树的右侧插入，先左旋后右旋转。
• RL情况：在右子树的左侧插入，先右旋后左旋转。

下面是AVL树插入的C++示例代码：

#include <iostream>
using namespace std;

// AVL树节点结构
struct AVLNode {
    int key, height;
    AVLNode *left, *right;

    AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};

class AVLTree {
public:
    AVLNode* root;

    AVLTree() : root(nullptr) {}

    // 获取节点高度
    int getHeight(AVLNode* node) {
        return node ? node->height : 0;
    }

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

    // 获取平衡因子
    int getBalanceFactor(AVLNode* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

    // 右旋操作
    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 key) {
        if (!node) 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 // 不允许重复值
            return node;

        updateHeight(node);

        int balance = getBalanceFactor(node);

        // 左左情况
        if (balance > 1 && key < node->left->key)
            return rightRotate(node);
        // 右右情况
        if (balance < -1 && key > node->right->key)
            return leftRotate(node);
        // 左右情况
        if (balance > 1 && key > node->left->key) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        // 右左情况
        if (balance < -1 && key < node->right->key) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    void insert(int key) {
        root = insert(root, key);
    }

    // 中序遍历
    void inOrder(AVLNode* node) {
        if (!node) return;
        inOrder(node->left);
        cout << node->key << " ";
        inOrder(node->right);
    }

    void printInOrder() {
        inOrder(root);
        cout << endl;
    }
};

int main() {
    AVLTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(40);
    tree.insert(50);
    tree.insert(25);

    cout << "中序遍历结果: ";
    tree.printInOrder(); // 输出排序后的结果，应该是：10 20 25 30 40 50

    return 0;
}

三、AVL树的应用场景

AVL树由于其查找、插入、删除操作时间复杂度均为O(log n)，因此非常适合用于需要动态数据结构的场景，例如：

• 数据库索引：在数据库中，AVL树可以用于索引数据表，快速查找和插入记录。
• 内存管理：在操作系统中，AVL树可用于管理内存块的分配和回收。
• 网络路由：在网络中，AVL树可用于存储路由表，快速查找路由信息。

总结

AVL树是一种高效的平衡二叉搜索树，凭借其良好的性能和广泛的应用，成为了数据结构与算法课程中的重要内容。通过上述的插入操作实现示例，我们可以更深入地理解其工作原理，并为实际项目中的数据存储和管理提供支持。