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

文章目录

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;  // 根节点指针
};

右单旋

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

最基础的情况

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

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

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

再次添加难度
最复杂的情况

在这里插入图片描述

右单旋代码

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

void RotateR(Node* parent)
{// 获取父节点的左子节点Node* subL = parent->_left;// 获取左子节点的右子节点Node* subLR = subL->_right;// 修改父节点的左子节点为 subLRparent->_left = subLR;// 如果 subLR 不为空，更新 subLR 的父节点为 parentif (subLR)subLR->_parent = parent;// 获取 parent 的父节点，方便之后修改，这个地方因为parent可能不是根节点，所以可能会继续向上进行平衡调整Node* parentParent = parent->_parent;// 将左子节点 subL 的右子节点指向 parent，parent 的父节点指向 subLsubL->_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// 因为旋转后，两个节点的平衡因子应该都变为 0parent->_bf = subL->_bf = 0;
}

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

左单旋

在这里插入图片描述

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

左单旋代码

void RotateL(Node* parent)
{// 获取父节点的右子节点Node* subR = parent->_right;// 获取右子节点的左子节点Node* subRL = subR->_left;// 修改父节点的右子节点为 subRLparent->_right = subRL;// 如果 subRL 不为空，更新 subRL 的父节点为 parentif(subRL)subRL->_parent = parent;// 获取 parent 的父节点，方便之后修改Node* parentParent = parent->_parent;// 将右子节点 subR 的左子节点指向 parent，parent 的父节点指向 subRsubR->_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// 因为旋转后，两个节点的平衡因子应该都变为 0parent->_bf = subR->_bf = 0;
}

左右双旋

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

最基础情况

情况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，旋转后所有节点的平衡因子都设置为 0subL->_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，旋转后所有节点的平衡因子都设置为 0subR->_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);}
}