2024年最新【高阶数据结构】AVL树（动图详解）_avl tree(1)，2024年最新大数据开发基础入门
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！
由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新
cur = parent;
parent = parent->_parent;
当平衡因子出现了2/-2的情况，要对子树进行旋转处理，但也要遵守原则
- 旋转成平衡树
- 保持搜索树的规则
而旋转有四种大情况，对此我们要进行分类：
- 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋
- 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋
- 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋
- 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋
注意：旋转过后无需再往上更新平衡因子了，因为高度已经没有发生变化了，也就不会影响父节点的平衡因子了
//插入
bool Insert(const pair<K, V>& kv)
{
//若为空树，直接插入作为根节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//和二叉搜索树类似，找到该插入的节点位置
Node\* parent = nullptr;
Node\* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)//插入节点值大于当前节点的key
{
parent = cur;
cur = cur->_right;//往右走
}
else if (cur->_kv.first > kv.first)//插入节点值小于当前节点的key
{
parent = cur;
cur = cur->_left;//往左走
}
else
{
//插入的节点key值等于当前位置的key值，插入失败
return false;
}
}
//开始插入
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else if (parent->_kv.first < kv.first)
{
parent->_left = cur;
}
//连接parent
cur->_parent = parent;
//控制平衡
//1、更新平衡因子
while (parent)
{
if (cur == parent->right)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
if (parent->_bf == -1 || parent->_bf == 1)//也可以用abs
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == -2 || parent->_bf == 2)
{
//说明parent所在的子树已经不平衡了，需要旋转
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);//左单旋
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);//右单旋
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);//左右双旋
}
break;
}
else
{
assert(false);//在插入前树的平衡因子就有问题
}
}
return true;
}
四. AVL树的旋转
🥑左单旋
新节点插入较高右子树的右侧 —右右：左单旋
⚡动图展示：
抽象图过程解析：
其中h可以等于0、1、2等等，不过都可以归纳到这种大情况，处理情况都一样，都是引发parent 等于2，cur等于1
左单旋旋转步骤：
- subRL变成parent的右子树（
subL和parent的关系，要注意🔥subL可能为空 ） - parent成为subR的左子树（
parent和subLR的关系） - subR成为根节点（
ppNode 和 subL关系，也要注意🔥parent是子树的根还是整棵树的根 ） - 最后更新平衡因子
为什么要这样旋转？要符合二叉搜索树规则
- subR的左子树的值本身就比parent的值要大，所以可以作为parent的右子树
- parent及其左子树当中结点的值本身就比subR的值小，所以可以作为subR的左子树
平衡因子更新：
可以看见，左单旋后树的高度就平衡了，也就无需继续向上更新平衡因子了
代码实现如下：（详细注释）
void RotateL(Node\* parent)
{
//三叉链
Node\* subR = parent->_right;
Node\* subLR = subR->_left;
Node\* ppNode = parent->_parent;
//subR 和 parent之间的关系
subR->_left = parent;
parent->_parent = subR;
//subRL 和 parent之间的关系
subRL = parent->_right;
if (subRL)
subRL->parent = parent;
//ppNode 和 subR的关系
if (ppNode == nullptr)
{
_root = subR;
subR->_parent = nullptr;//没有父节点，所以为空
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
//更新平衡因子
subR->_bf = parent->_bf = 0;
}
🥑右单旋（和左单旋高度相似）
新节点插入较高左子树的左侧 —左左：右单旋
动图演示：
抽象图过程解析：
右单旋旋转步骤：
与左单旋雷同，看上面就行
同样也要满足二叉搜索树的性质 ：也是和左单旋雷同，看上面就行
平衡因子更新如下：
同样右单旋后，parent的平衡因子为0，左右子树高度相等，也就无需继续往上更新平衡因子了
话不多说上代码：
//右单旋
void RotateR(Node\* parent)
{
Node\* subL = parent->_left;
Node\* subLR = subL->_right;
Node\* ppNode = parent->_parent;
//subL 和 parent的关系
subL->_right = parent;
parent->_parent = subL;
//subLR 和 parent之间的关系
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//ppNode 和 subL的关系
if (ppNode == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left == subL;
}
else
{
ppNode->_right == subL;
}
subL->_parent = ppNode;
}
//更新平衡因子
subL->_bf = parent->_bf = 0;
}
🔥左右单旋
新节点插入较高左子树的右侧 —左右：先左单旋再右单旋 、
动图演示：
在b树或者c树中新增节点，均会引发左右双旋
旋转示意图如下：
1、插入新节点
2、以30为旋转点进行左单旋
3、以90为旋转点进行右单旋
左右单旋的步骤如下：
- 以subL为节点左单旋
- 以parent为节点右单旋
- 更新平衡因子 （这才是重点）
左右双旋后满足二叉搜索树的性质：
实际上就是把subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根（看图理解）
- subLR左子树的节点值比subL的值大，所以可以作为subL的右子树
- subLR右子树的节点值比parent的值小，因此可以作为parent的左子树
- 前两个步骤之后，subL以及子树的值，和parent的值均符合，所以可以当subLR的左右子树
重点来了：（以subLR为突破口 ）
左右双旋后，平衡因子的更新随着subLR原始平衡因子 的不同分为以下三种情况：
-
当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0
-
当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0
-
当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0
经过左右双旋后，即树的高度没有发生变化，所以无需继续往上更新平衡因子
话不多说，代码实现一下吧：
void RotateLR(Node\* parent)
{
Node\* subL = parent->_left;
Node\* subLR = subL->_right;
int bf = subLR->_bf;
//subL节点左单旋
RotateL(subL);
//parent节点进行右单旋
RotateR(parent);
//更新平衡因子
if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if(bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);//旋转前的平衡因子就出错了
}
}
🔥右左单旋
动图演示：
旋转图演示过程：
1、插入新节点
2、以subR的节点进行右单旋
3、以parent的节点进行右单旋
旋转步骤和左右双旋雷同
重点来了：（以subRL为突破口 ）
左右双旋后，平衡因子的更新随着subRL 原始平衡因子 的不同分为三种情况分别对应subRL = 0、1、2情况，此处就不多赘述了，详细可以浏览左右双旋的，情况一样
代码实现
void RotateRL(Node\* parent)
{
Node\* subR = parent->_right;
Node\* subRL = subR->_left;
int bf = subRL->_bf;
//subR右单旋
RotateR(subR);
//parent进行左单旋
RotateL(parent);
if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
五. 验证AVL树
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
-
验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树 -
验证其为平衡树 * 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
- 节点的平衡因子是否计算正确
先验证是否为二叉搜索树
void \_InOrder(Node\* root)
{
if (root == nullptr)
{
return;
\_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
\_InOrder(root->_right);
}
但中序遍历只能代表是二叉搜索树，不能代表是AVL树，为此还需要验证二叉树的平衡性，查平衡因子有一种监守自盗的感觉，因为平衡因子我们刚修改完，所以我们去查高度俩判断！
网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。
一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
oot->_left);
cout << root->_kv.first << “:” << root->_kv.second << endl;
_InOrder(root->_right);
}
但中序遍历只能代表是二叉搜索树，不能代表是AVL树，为此还需要验证二叉树的平衡性，查平衡因子有一种监守自盗的感觉，因为平衡因子我们刚修改完，所以我们去查高度俩判断！
[外链图片转存中...(img-e9LNrmE4-1715305269984)]
[外链图片转存中...(img-B7RRCS0M-1715305269985)]
**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。** **[需要这份系统化资料的朋友，可以戳这里获取]()** **一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**