C++数据结构之AVL树的实现

什么是AVL树

AVL树是一种自平衡二叉查找树，也就是说它通过旋转操作来保持树的平衡。

在AVL树中，任何节点的两个子树高度差不超过1。如果高度差大于1，则需要通过旋转操作来调整树的平衡。

AVL树提供了比红黑树更快的插入和删除操作，但是在读取数据时红黑树更快。

AVL树的实现

结构体定义

我们可以先定义一个结构体来表示AVL树中的节点：

struct Node  
{  
    int value;          // 当前节点的值  
    int height;         // 当前节点的高度  
    Node* left;         // 左子树指针  
    Node* right;        // 右子树指针  

    Node(int v)  
    {  
        value = v;  
        height = 1;  
        left = right = nullptr;  
    }  
};  

在这个结构体中，value表示节点存储的值，height表示当前节点的高度，left和right分别表示左右子树的指针。

插入操作

AVL树的插入操作比较复杂，需要分为以下几个步骤：

• 向树中插入新节点
• 更新节点的高度
• 判断是否需要进行左旋或右旋或LR旋或RL旋操作

我们可以定义一个Insert函数来实现上述操作：

Node* Insert(Node* root, int value)  
{  
    // 向树中插入新节点  
    if (root == nullptr)  
        return new Node(value);  

    if (value < root->value)  
        root->left = Insert(root->left, value);  
    else  
        root->right = Insert(root->right, value);  

    // 更新节点的高度  
    root->height = max(GetHeight(root->left), GetHeight(root->right)) + 1;  

    // 判断是否需要进行左旋或右旋或LR旋或RL旋操作  
    int balance = GetBalance(root);  
    if (balance > 1 && value < root->left->value)  
        return RightRotate(root);  
    if (balance < -1 && value > root->right->value)  
        return LeftRotate(root);  
    if (balance > 1 && value > root->left->value)  
        return LeftRightRotate(root);  
    if (balance < -1 && value < root->right->value)  
        return RightLeftRotate(root);  

    return root;  
}

其中，GetHeight函数用于获取节点的高度，GetBalance函数用于获取节点的平衡因子（左子树高度减去右子树高度）。

LeftRotate、RightRotate、LeftRightRotate、RightLeftRotate分别表示左旋、右旋、LR旋、RL旋操作。

删除操作

AVL树的删除操作也比较复杂，需要分为以下几个步骤：

• 找到待删除的节点
• 删除节点
• 更新祖先节点的高度
• 判断是否需要进行左旋或右旋或LR旋或RL旋操作

我们可以定义一个Delete函数来实现上述操作：

Node* Delete(Node* root, int value)  
{  
    // 找到待删除的节点  
    if (root == nullptr)  
        return root;  

    if (value < root->value)  
        root->left = Delete(root->left, value);  
    else if (value > root->value)  
        root->right = Delete(root->right, value);  
    else  
    {  
        // 删除节点  
        if (root->left == nullptr || root->right == nullptr)  
            root = (root->left == nullptr ? root->right : root->left);  
        else  
        {  
            Node* cur = root->right;  
            while (cur->left != nullptr)  
                cur = cur->left;  
            root->value = cur->value;  
            root->right = Delete(root->right, cur->value);  
        }  
    }  

    if (root == nullptr)  
        return root;  

    // 更新祖先节点的高度  
    root->height = max(GetHeight(root->left), GetHeight(root->right)) + 1;  

    // 判断是否需要进行左旋或右旋或LR旋或RL旋操作  
    int balance = GetBalance(root);  
    if (balance > 1 && GetBalance(root->left) >= 0)  
        return RightRotate(root);  
    if (balance > 1 && GetBalance(root->left) < 0)  
        return LeftRightRotate(root);  
    if (balance < -1 && GetBalance(root->right) <= 0)  
        return LeftRotate(root);  
    if (balance < -1 && GetBalance(root->right) > 0)  
        return RightLeftRotate(root);  

    return root;  
}

其中，GetHeight函数与Insert函数中一样，GetBalance函数也与Insert函数中一样，LeftRotate、RightRotate、LeftRightRotate、RightLeftRotate也与Insert函数中一样。

示例

我们可以使用以下示例来测试我们实现的AVL树：

int main()  
{  
    Node* root = nullptr;  

    root = Insert(root, 10);  
    root = Insert(root, 20);  
    root = Insert(root, 30);  
    root = Insert(root, 40);  
    root = Insert(root, 50);  
    root = Insert(root, 25);  

    cout << "AVL Tree is:\n";  
    Print(root);  
    cout << endl;  

    root = Delete(root, 50);  

    cout << "AVL Tree after deletion is:\n";  
    Print(root);  
    cout << endl;  

    return 0;  
}  

其中，Print函数用于将AVL树的结构打印出来：

void Print(Node* root)  
{  
    if (root == nullptr)  
        return;  

    cout << root->value << " ";  
    Print(root->left);  
    Print(root->right);  
}  

执行以上程序会得到如下运行结果：

AVL Tree is:
30 20 10 25 40 50
AVL Tree after deletion is:
25 20 10 30 40

从结果可以看出，我们实现的AVL树能够正确地插入和删除节点，并且能够保持树的平衡。