今天你学C++了吗？——AVL树
♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥
♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥
♥♥♥我们一起努力成为更好的自己~♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥
✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨在前面的博客中，我们已经学习了很多C++里面的容器，这一篇博客我们开始学习AVL树，准备好了吗~我们发车去探索C++的奥秘啦~🚗🚗🚗🚗🚗🚗
目录
AVL的概念
AVL树的结构
AVL树的插入
AVL树插入值流程
平衡因子更新
更新原则
更新停止条件
插入结点和平衡因子更新代码实现
旋转处理
旋转的原则
左单旋(右边高往左旋）
右单旋(左边高往右旋）
左右双旋
右左双旋
AVL树的查找
总代码
AVL的概念
什么是AVL呢？
AVL树是一种自平衡的二叉搜索查找树，在C++中常用于实现高效的动态集合操作，例如插入、删除和查找。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们于1962年首次提出这一数据结构。AVL树的出现是为了控制搜索二叉树的平衡，所以AVL树引入了一个平衡因子的概念~
- AVL树要求任何节点的两个子树的高度差（称为平衡因子）的绝对值不超过1。
- 平衡因子定义为：平衡因子 = 左子树高度 - 右子树高度。（当然也可以是【右子树高度 - 左子树高度】）
- 如果插入或删除节点导致树的平衡性被破坏，AVL树会通过旋转操作（单旋转或双旋转）重新恢复平衡，这个是我们后面的重点讲解部分~
有的人可能会说，既然是平衡的，那么为什么不是高度差为0呢？这一点事实上是很难做到的，因为要保证每一个节点高度差为0，那么只有满二叉树才可以满足这个条件了~这样不就只可以表示满二叉树了吗！高度差为0看似完美，但在实际节点数分布下（如2个节点、4个节点等）往往无法实现。所以高度差不超过1的规则，既保证了树的平衡性，又允许树根据节点数灵活调整结构，避免因过度限制导致构建失败。这种设计在保持高效操作的同时，实现了平衡性与灵活性的统一！
我们可以来看看例子：（以【右子树高度 - 左子树高度】为标准）
不难看出下面的这样一颗二叉树就是AVL树，每一个结点的左右子树高度差都不大于1~
但是下面的这一棵二叉树就不是AVL树，结点10的左右子树高度差为2，不满足条件~
AVL树的结构
结合前面博客中二叉搜索树的结构二叉搜索树，那么AVL树是平衡的二叉搜索树，那么肯定有二叉搜索树的大体结构~
二叉搜索树的结点应该保存三个数据：
1、当前结点保存的数据
2、当前结点的左子树地址
3、当前结点的右子树地址
AVL树结点还需要添加部分内容，一个是平衡因子，一个是双亲指针~
平衡因子好理解，双亲指针有什么作用呢？在后面我们会进行解释~
知道了结点的定义，我们就可以这样定义AVL树的结构：
//AVL树结点结构 template struct AVLTreeNode { pair _kv;//保存的数据类型 AVLTreeNode* _left;//左孩子结点指针 AVLTreeNode* _right;//右孩子结点指针 AVLTreeNode* _parent;//双亲结点指针 int _bf;//平衡因子 //初始化 AVLTreeNode(const pair& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) { } }; //AVL树结构 template class AVLTree { typedef AVLTreeNode Node; private: Node* _root = nullptr;//根节点 public: //功能实现 };知道了AVL树的结构，接下来我们就可以对AVL树进行插入，删除等操作了
AVL树的插入
我们首先来看看对AVL树的插入数据操作~
AVL树插入值流程
- 插入操作：依据二叉搜索树的规则来插入一个值。
- 平衡因子更新：新结点插入后，仅会对祖先结点的高度产生影响，进而可能改变部分祖先结点的平衡因子。因此，需要沿着从新增结点到根结点的路径更新平衡因子。在最坏的情况下，可能需要一直更新到根结点；而在某些情况下，更新到中间某个结点就可以停止了，在后续会详细分析具体情况。
- 插入结束条件：
- 若在更新平衡因子的过程中没有出现不平衡的情况，那么插入操作结束。
- 若在更新平衡因子的过程中出现了不平衡，对不平衡的子树进行旋转操作。旋转操作在调整平衡的同时，会降低子树的高度，使得不再影响上一层结点，此时插入操作结束。
平衡因子更新
更新原则
- 我们实现的AVL树平衡因子的计算公式为：平衡因子 = 右子树高度 - 左子树高度。
- 只有当子树的高度发生变化时，才会影响当前结点的平衡因子。
- 插入结点会导致高度增加，所以：
- 若新增结点位于父结点（parent）的右子树，那么父结点的平衡因子加1（parent的平衡因子++）。
- 若新增结点位于父结点（parent）的左子树，那么父结点的平衡因子减1（parent平衡因子--）。
- 父结点所在子树的高度是否发生变化，决定了是否需要继续向上更新平衡因子。
更新停止条件
- 平衡因子变为0的情况：当更新操作完成后，若父结点（parent）的平衡因子等于0，且在更新过程中其平衡因子变化为 -1→0 或者 1→0，这表明在更新之前，父结点的子树呈现一边高一边低的状态，而新增结点被插入到了较低的那一边。如此一来，插入操作后父结点所在的子树高度并未发生改变，也就不会对父结点的父结点的平衡因子产生影响，此时更新操作可以结束。
- 平衡因子变为1或 -1的情况：更新结束后，若父结点的平衡因子为1或 -1，且在更新前和更新过程中其平衡因子变化为 0→1 或者 0→ -1，这意味着在更新之前，父结点的子树两边高度是相等的。然而，新增结点插入之后，父结点所在的子树出现了一边高一边低的情况。虽然此时父结点所在的子树仍然符合平衡要求，但是子树的高度增加了1，这会对父结点的父结点的平衡因子产生影响，所以需要继续向上进行更新操作。
- 平衡因子变为2或 -2的情况：更新完成后，若父结点的平衡因子为2或 -2，且在更新前和更新过程中其平衡因子变化为 1→2 或者 -1→ -2，这说明在更新之前，父结点的子树就是一边高一边低的状态，而新增结点插入到了较高的那一边，导致父结点所在的子树较高的那一边变得更高，从而破坏了子树的平衡状态，父结点所在的子树不再符合平衡要求，需要进行旋转处理。旋转操作有两个目标：一是将父结点的子树调整至平衡状态；二是降低父结点子树的高度，使其恢复到插入结点之前的高度。因此，旋转操作完成后，无需再继续向上进行更新，插入操作结束。（旋转策略我们后面会重点讲解）
- 更新到根结点的情况：在不断向上更新的过程中，如果更新操作一直进行到根结点，即便根结点的平衡因子为1或 -1，更新操作也会停止。
插入结点和平衡因子更新代码实现
有了上面的这些画图理解和理论基础，接下来我们来进行代码实现：
//插入结点 bool insert(const pair& kv) { if (_root == nullptr)//不存在根结点 { //插入结点就是根结点 _root = new Node(kv); return true;//插入成功 } //存在根结点——找到应该插入的位置 Node* parent = nullptr; Node* cur = _root; while (cur) { if (kv.first _kv.first)//比当前结点小，插入当前结点左子树 { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first)//比当前结点大，插入当前结点右子树 { parent = cur; cur = cur->_right; } else//相等就不进行插入，插入失败 { return false; } } //parent即为插入结点父结点 cur = new Node(kv); //判断是插入父结点左边还是右边 if (kv.first _kv.first) { parent->_left = cur; } else if (kv.first > parent->_kv.first) { parent->_right = cur; } cur->_parent = parent; //平衡因子更新 while (parent) { //我们实现的AVL树平衡因子的计算公式为：平衡因子 = 右子树高度 - 左子树高度 if (parent->_left == cur) //插入结点在左子树,父结点平衡因子-- { parent->_bf--; } else if (parent->_right == cur) //插入结点在右子树，父结点平衡因子++ { parent->_bf++; } //分情况讨论 //1、父结点平衡因子更新为0，不需要继续向上更新 if (parent->_bf == 0) break; //2、父结点平衡因子更新为-1或者1，需要继续向上更新 //如果当前父结点为根结点，parent会到空，跳出循环 else if (parent->_bf == -1 || parent->_bf == 1) { cur = parent; parent = parent->_parent; } //3、父结点平衡因子更新为-2或者2，已经不平衡需要旋转处理 else if (parent->_bf == -2 || parent->_bf == 2) { //旋转处理 break; } //其他情况，说明更新有问题 else { assert(false); } } //更新结束 return true; }总的逻辑写完了，接下来就是我们的旋转处理了，我们继续来看看~
旋转处理
在前面我们已经进行了平衡因子的更新，我们可以发现当有结点的平衡因子达到2或者-2的时候，这个时候就不是平衡二叉树了，那么我们就需要进行旋转处理~
旋转的原则
- 保持搜索树的规则（高度差_right;//cur
Node* subRL = subR->_left;//B
//更改指向
subR->_left = parent;
parent->_right = subRL;
//修改变动结点（subR，subRL，parent）的parent
if(subRL)//subRL可能为空
subRL->_parent = parent;
parent->_parent = subR;
//subR可能成为整棵树的根结点，需要进行判断更新subR的parent
Node* parentParent = parent->_parent;
if (parentParent == nullptr)
{
//subR成为整棵树的根结点
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)//判断原节点是父亲的左/右结点
{
parentParent->_left == subR;
}
else
{
parentParent->_right = subR;
}
//更新subR父结点
subR->_parent = parentParent;
}
//更新平衡因子
parent->_bf = subR->_bf = 0;
}
右单旋(左边高往右旋）
相信有了左单旋的基础，右单旋就更加简单了~
我们依然进行画图理解：
前面我们提到过h是可以代表任意高度的，这里我们讨论几种情况：
情况一：h==0
情况二：h==1
情况三：h==2
情况四：h==3
我们可以发现不论是哪一种情况，都是可以进行相同的右单旋操作，也就有了我们的通用方案~
接下来，我们就进行代码实现：
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right;//b //旋转操作 parent->_left = subLR; subL->_right = parent; //更新相应结点parent if (subLR)//h可能等于0，那么subLR可能为空 subLR->_parent = parent; Node* parentParent = parent->_parent;//保存父结点的父亲 if (parentParent == nullptr)//说明原来的父结点是根结点 { _root = subL; subL->_parent = nullptr; } else { if (parentParent->_left == parent)//父结点是左孩子 { parentParent->_left = subL; } else { //父结点是右孩子 parentParent->_right = subL; } subL->_parent = parentParent; } parent->_parent = subL; //更新平衡因子 subL->_bf = parent->_bf = 0; }代码大致上是差不多的，只是逻辑上有一些区别~
有了左单旋和右单旋，接下来，我们来看看更加复杂的情况~
左右双旋
在有些情况下，我们仅仅进行左单旋或者右单旋是无法解决问题的，比如说下面的例子~
示例：不再是单纯的左边高，结点10是左边高，而结点5是右边高~也就可以发现插入节点之后parent和cur结点平衡因子异号~
显然进行简单的单旋操作就不能解决问题了~单旋之后依然是不平衡的~
我们继续以一个通用的例子进行分析：
我们可以看到在b子树新增加结点导致5结点右边高，10结点左边高，简单的单旋无法重新设置平衡，我们需要进行双旋，双旋就是利用两次单旋，经过第一次单旋让10结点变成单纯的左边高，再一次单旋就可以达到平衡~
我们对b子树进行进一步的拆分
b子树新增加的结点点有下面的三种情况，我们来进行逐一分析：
情况一：新增加结点在e子树
第一步：以5（subL）为旋转点进行左单旋
第二步；以10结点（parent）为旋转点进行右单旋
经过两步单旋操作之后，这就平衡了~
情况二：新增加结点在f子树
情况三：新增结点就是b子树（也就是h==0）
这三种情况都是先进行左单旋再进行右单旋，操作是一样的，那么我们就可以进行代码复用，使用前面的左右单旋代码，这里比较麻烦的是平衡因子的更新~
我们可以看到三种情况的平衡因子是不一样的，我们可以根据结点插入后subLR的平衡因子来进行分情况讨论更新平衡因子~
代码实现：
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; //根据没有旋转前subLR的平衡因子分情况讨论 int bf = subLR->_bf; //先以subL为旋转点左旋 RotateL(subL); //再以parent为旋转点右旋 RotateR(parent); //每一个结点父结点已经更新，只需要修改平衡因子 if (bf == -1)//插入在e子树 { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1)//插入在f子树 { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0)//插入在b子树自己 { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else//其他情况，说明有问题 { assert(false); } }右左双旋
知道了左右双旋，那么右左双旋就好分析了~
我们同样用一个通用的例子来进行分析：
我们直接画图理解
对b子树进行进一步拆分：
b子树新增加的结点点有下面的三种情况，我们来进行逐一分析：
情况一：新增加结点在e子树
情况二：新增加结点在f子树
第一步：以15（subR）为旋转点进行右单旋
第二步；以10结点（parent）为旋转点进行左单旋
完整图
情况三：新增结点就是b子树（也就是h==0）
这三种情况都是先进行右单旋再进行左单旋，操作是一样的，那么我们就可以进行代码复用，使用前面的左右单旋代码，这里比较麻烦的是平衡因子的更新~
根据经验，我们可以利用结点插入后subRL的平衡因子来进行分情况讨论更新平衡因子~
代码实现：
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; //根据没有旋转前subRL的平衡因子分情况讨论 int bf = subRL->_bf; //先以subR为旋转点右旋 RotateR(subR); //再以parent为旋转点左旋 RotateL(parent); //每一个结点父结点已经更新，只需要修改平衡因子 if (bf == -1)//插入在e子树 { subRL->_bf = 0; subR->_bf = 1; parent->_bf = 0; } else if (bf == 1)//插入在f子树 { subRL->_bf = 0; subR->_bf = 0; parent->_bf = -1; } else if (bf == 0)//插入在b子树自己 { subRL->_bf = 0; subR->_bf = 0; parent->_bf = 0; } else//其他情况，说明有问题 { assert(false); } }AVL树的查找
我们知道AVL树是二叉平衡搜索树，那么我们就可以使用二叉搜索树的查找逻辑~
- 初始化：从根节点开始遍历
- 循环比较：
- 条件：只要当前节点不为空且未找到目标值，继续循环。
- 比较操作：
- 若目标值等于当前节点值，查找成功，返回当前节点。
- 若目标值小于当前节点值，移动到左子节点。
- 若目标值大于当前节点值，移动到右子节点。
- 终止条件：
- 找到目标节点，返回结果。
- 当前节点为空，说明目标值不存在。
代码实现：
//查找结点 Node* Find(const K&key)//查找key { Node* cur = _root; while (cur) { if (cur->_kv.first > key)//key在左子树 { cur = cur->_left; } else if (cur->_kv.first _right; } else { return cur;//相等，返回当前结点 } } //没有找到返回空 return nullptr; }AVL树的实现就结束了~
总代码
#include #include #include using namespace std; //AVL树结点结构 template struct AVLTreeNode { pair _kv;//保存的数据类型 AVLTreeNode* _left;//左孩子结点指针 AVLTreeNode* _right;//右孩子结点指针 AVLTreeNode* _parent;//双亲结点指针 int _bf;//平衡因子 //初始化 AVLTreeNode(const pair& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) { } }; //AVL树结构 template class AVLTree { typedef AVLTreeNode Node; private: Node* _root = nullptr;//根节点 public: //功能实现 //查找结点 Node* Find(const K&key)//查找key { Node* cur = _root; while (cur) { if (cur->_kv.first > key)//key在左子树 { cur = cur->_left; } else if (cur->_kv.first _right; } else { return cur;//相等，返回当前结点 } } //没有找到返回空 return nullptr; } //插入结点 bool insert(const pair& kv) { if (_root == nullptr)//不存在根结点 { //插入结点就是根结点 _root = new Node(kv); return true;//插入成功 } //存在根结点——找到应该插入的位置 Node* parent = nullptr; Node* cur = _root; while (cur) { if (kv.first _kv.first)//比当前结点小，插入当前结点左子树 { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first)//比当前结点大，插入当前结点右子树 { parent = cur; cur = cur->_right; } else//相等就不进行插入，插入失败 { return false; } } //parent即为插入结点父结点 cur = new Node(kv); //判断是插入父结点左边还是右边 if (kv.first _kv.first) { parent->_left = cur; } else if (kv.first > parent->_kv.first) { parent->_right = cur; } cur->_parent = parent; //平衡因子更新 while (parent) { //我们实现的AVL树平衡因子的计算公式为：平衡因子 = 右子树高度 - 左子树高度 if (parent->_left == cur) //插入结点在左子树,父结点平衡因子-- { parent->_bf--; } else if (parent->_right == cur) //插入结点在右子树，父结点平衡因子++ { parent->_bf++; } //分情况讨论 //1、父结点平衡因子更新为0，不需要继续向上更新 if (parent->_bf == 0) break; //2、父结点平衡因子更新为-1或者1，需要继续向上更新 //如果当前父结点为根结点，parent会到空，跳出循环 else if (parent->_bf == -1 || parent->_bf == 1) { cur = parent; parent = parent->_parent; } //3、父结点平衡因子更新为-2或者2，已经不平衡需要旋转处理 else if (parent->_bf == -2 || parent->_bf == 2) { //旋转处理 //插入在右子树(右边高）——左单旋 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } 插入在左子树(左边高）——左单旋 else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } //parent与cur平衡因子异号需要进行双旋 //左右双旋 else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } //右左双旋 else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } break; } //其他情况，说明更新有问题 else { assert(false); } } //更新结束 return true; } void RotateL(Node* parent) { Node* subR = parent->_right;//cur Node* subRL = subR->_left;//B //更改指向 subR->_left = parent; parent->_right = subRL; //修改变动结点（subR，subRL，parent）的parent if(subRL)//subRL可能为空 subRL->_parent = parent; parent->_parent = subR; //subR可能成为整棵树的根结点，需要进行判断更新subR的parent Node* parentParent = parent->_parent; if (parentParent == nullptr) { //subR成为整棵树的根结点 _root = subR; subR->_parent = nullptr; } else { if (parentParent->_left == parent)//判断原节点是父亲的左/右结点 { parentParent->_left == subR; } else { parentParent->_right = subR; } //更新subR父结点 subR->_parent = parentParent; } //更新平衡因子 parent->_bf = subR->_bf = 0; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right;//b //旋转操作 parent->_left = subLR; subL->_right = parent; //更新相应结点parent if (subLR)//h可能等于0，那么subLR可能为空 subLR->_parent = parent; Node* parentParent = parent->_parent;//保存父结点的父亲 if (parentParent == nullptr)//说明原来的父结点是根结点 { _root = subL; subL->_parent = nullptr; } else { if (parentParent->_left == parent)//父结点是左孩子 { parentParent->_left = subL; } else { //父结点是右孩子 parentParent->_right = subL; } subL->_parent = parentParent; } parent->_parent = subL; //更新平衡因子 subL->_bf = parent->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; //根据没有旋转前subLR的平衡因子分情况讨论 int bf = subLR->_bf; //先以subL为旋转点左旋 RotateL(subL); //再以parent为旋转点右旋 RotateR(parent); //每一个结点父结点已经更新，只需要修改平衡因子 if (bf == -1)//插入在e子树 { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1)//插入在f子树 { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0)//插入在b子树自己 { subLR->_bf = 0; subL->_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; //先以subR为旋转点右旋 RotateR(subR); //再以parent为旋转点左旋 RotateL(parent); //每一个结点父结点已经更新，只需要修改平衡因子 if (bf == -1)//插入在e子树 { subRL->_bf = 0; subR->_bf = 1; parent->_bf = 0; } else if (bf == 1)//插入在f子树 { subRL->_bf = 0; subR->_bf = 0; parent->_bf = -1; } else if (bf == 0)//插入在b子树自己 { subRL->_bf = 0; subR->_bf = 0; parent->_bf = 0; } else//其他情况，说明有问题 { assert(false); } } };♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
✨✨✨✨✨✨个人主页✨✨✨✨✨✨
