如何在AVL树中高效插入并保持平衡：一步步掌握旋转与平衡因子 —— 旋转篇

AVL树种旋转的规则

在AVL树中，旋转是为了保持树的平衡性。AVL树是一种自平衡的二叉搜索树，它要求每个节点的左右子树的高度差不能超过1。当插入或删除节点后，可能会导致树的平衡因子（左右子树的高度差）超出允许的范围（-1、0、1）。为了恢复平衡，AVL树会使用旋转来调整树的结构。

旋转类型
根据不平衡的类型，AVL树有四种基本的旋转方式：

• 单右旋转（Right Rotation） - 适用于左子树过高的情况。
• 单左旋转（Left Rotation） - 适用于右子树过高的情况。
• 左-右双旋转（Left-Right Rotation） - 适用于左子树的右子树过高的情况。
• 右-左双旋转（Right-Left Rotation） - 适用于右子树的左子树过高的情况。

在上一篇文章当中，我们已经知道了关于AVL树的结构
下面重新展示出来：

template<class K, class V>
struct AVLTreeNode 
{
    // 每个节点包含的元素和指针
    pair<K, V> _kv;           // 存储键值对
    AVLTreeNode<K, V>* _left;  // 左子树指针
    AVLTreeNode<K, V>* _right; // 右子树指针
    AVLTreeNode<K, V>* _parent; // 父节点指针
    int _bf;                   // 平衡因子

    // 构造函数
    AVLTreeNode(const pair<K, V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _bf(0)
    {}
};

template<class K, class V>
class AVLTree 
{
    typedef AVLTreeNode<K, V> Node;  // 节点类型
public:

    // 其他操作（插入、删除、查找等）可以在此添加

private:
    Node* _root;  // 根节点指针
};

右单旋

抽象的来看右单旋的图（我们可以在最后在看这个图，先有一个大概印象）

1. 最基础的情况
   

我们肉眼看到的是在 5 结点插入了一个左子树 1 结点，原先平衡的树，在新插入一个节点之后就不平衡了，其grandfather的平衡因子由-1变为了-2， 不满足AVL树的平衡条件，所以这种情况下，我们就需要通过旋转，以此达到让插入之后形成的这颗树平衡，可以看见，这颗树是左边高，所以需要向右进行旋转，即左高往右旋转，所以旋转之后的图形即是上图的最右侧图形，而且，5 变成了 10的父节点，10变成了 5 的右子树

2. 情况1上增加一个高度的情况
   

同样的，在左子树叶子结点插入左子树，也是通过右旋转，以此达到平衡

3. 再次添加难度
   

4. 最复杂的情况
   

右单旋代码

根据上面图片理解下面的代码

void RotateR(Node* parent)
{
    // 获取父节点的左子节点
    Node* subL = parent->_left;
    
    // 获取左子节点的右子节点
    Node* subLR = subL->_right;

    // 修改父节点的左子节点为 subLR
    parent->_left = subLR;

    // 如果 subLR 不为空，更新 subLR 的父节点为 parent
    if (subLR)
        subLR->_parent = parent;

    // 获取 parent 的父节点，方便之后修改，这个地方因为parent可能不是根节点，所以可能会继续向上进行平衡调整
    Node* parentParent = parent->_parent;

    // 将左子节点 subL 的右子节点指向 parent，parent 的父节点指向 subL
    subL->_right = parent;
    parent->_parent = subL;

    // 如果 parent 是根节点，则需要修改树的根
    // 如果 parent 是子树的一部分，则只需修改父节点的指向
    if (parentParent == nullptr)
    {
        // 如果 parent 没有父节点（即 parent 是树的根节点），修改根节点
        _root = subL;
        subL->_parent = nullptr;  // subL 的父节点应为 null
    }
    else
    {
        // 如果 parent 有父节点（即 parent 只是子树的一部分），更新父节点的左/右指针
        if (parent == parentParent->_left)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }
        
        // 更新 subL 的父节点为 parent 的父节点
        subL->_parent = parentParent;
    }

    // 将 parent 和 subL 的平衡因子都设置为 0
    // 因为旋转后，两个节点的平衡因子应该都变为 0
    parent->_bf = subL->_bf = 0;
}

衷心希望读者，可以拿起笔来画图进行思考

左单旋

在分析完右单旋之后，左单旋的思考过程也是如此，当你弄清楚右单旋的过程，左单旋就是轻轻松松，举一反三！！！

左单旋代码

void RotateL(Node* parent)
{
    // 获取父节点的右子节点
    Node* subR = parent->_right;
    
    // 获取右子节点的左子节点
    Node* subRL = subR->_left;

    // 修改父节点的右子节点为 subRL
    parent->_right = subRL;

    // 如果 subRL 不为空，更新 subRL 的父节点为 parent
    if(subRL)
        subRL->_parent = parent;

    // 获取 parent 的父节点，方便之后修改
    Node* parentParent = parent->_parent;

    // 将右子节点 subR 的左子节点指向 parent，parent 的父节点指向 subR
    subR->_left = parent;
    parent->_parent = subR;

    // 如果 parent 是根节点，则需要修改树的根
    // 如果 parent 是子树的一部分，则只需修改父节点的指向
    if (parentParent == nullptr)
    {
        // 如果 parent 没有父节点（即 parent 是树的根节点），修改根节点
        _root = subR;
        subR->_parent = nullptr;  // subR 的父节点应为 null
    }
    else
    {
        // 如果 parent 有父节点（即 parent 只是子树的一部分），更新父节点的左/右指针
        if (parent == parentParent->_left)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }

        // 更新 subR 的父节点为 parent 的父节点
        subR->_parent = parentParent;
    }

    // 将 parent 和 subR 的平衡因子都设置为 0
    // 因为旋转后，两个节点的平衡因子应该都变为 0
    parent->_bf = subR->_bf = 0;
}

左右双旋

左右双旋的情况——即左边高（子树在右子树），所以单独一次左旋或者右旋都是无法处理的，所以需要两者配合进行，才能让平衡因子平衡。

1. 最基础情况
   

2. 情况1增加一些难度
   

3.抽象的描述

左右单旋的代码

void RotateLR(Node* parent)
{
    // 获取父节点的左子节点
    Node* subL = parent->_left;
    
    // 获取左子节点的右子节点
    Node* subLR = subL->_right;

    // 获取 subLR 的平衡因子，用于调整旋转后的平衡因子
    int bf = subLR->_bf;

    // 先对左子节点进行左单旋 (RotateL)
    RotateL(parent->_left);

    // 然后对 parent 进行右单旋 (RotateR)
    RotateR(parent);

    // 根据 subLR 的平衡因子调整旋转后节点的平衡因子
    if (bf == 0)
    {
        // 如果 subLR 的平衡因子是 0，旋转后所有节点的平衡因子都设置为 0
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == -1)
    {
        // 如果 subLR 的平衡因子是 -1，调整父节点、子节点的平衡因子
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    }
    else if (bf == 1)
    {
        // 如果 subLR 的平衡因子是 1，调整父节点、子节点的平衡因子
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        // 处理无效的平衡因子，理应不可能出现
        assert(false);
    }
}

右左单旋

右左单旋的代码

void RotateRL(Node* parent)
{
    // 获取父节点的右子节点
    Node* subR = parent->_right;
    
    // 获取右子节点的左子节点
    Node* subRL = subR->_left;

    // 获取 subRL 的平衡因子，用于调整旋转后的平衡因子
    int bf = subRL->_bf;

    // 先对右子节点进行右单旋 (RotateR)
    RotateR(parent->_right);

    // 然后对 parent 进行左单旋 (RotateL)
    RotateL(parent);

    // 根据 subRL 的平衡因子调整旋转后节点的平衡因子
    if (bf == 0)
    {
        // 如果 subRL 的平衡因子是 0，旋转后所有节点的平衡因子都设置为 0
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == 1)
    {
        // 如果 subRL 的平衡因子是 1，调整父节点、子节点的平衡因子
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = -1;
    }
    else if (bf == -1)
    {
        // 如果 subRL 的平衡因子是 -1，调整父节点、子节点的平衡因子
        subR->_bf = 1;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        // 处理无效的平衡因子，理应不可能出现
        assert(false);
    }
}