【C++】AVL树的了解和简单实现
目录
AVL树的概念
- AVL数是一棵具有二叉搜索树性质，并且左右子树的高度差不超过1的树
- AVL树还可以是一棵空树
AVL树的发明者：G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家
AVL树介绍
- AVL树遵循二叉搜索树的规则：左边小于根节点，右边大于根节点
- 本次AVL树的实现借助平衡因子的概念
平衡因子
- 每个节点都有一个平衡因子，该平衡因子等于右子树的高度减去左子树的高度
- 可以说任何节点的平衡因子可能是0/1/-1
- 平衡因子并不是AVL树的必须品，但它可以作为一个观察风向标，使我们更加方便观察和控制AVL树的平衡
注意： 如果平衡因子大于等于2，说明该树已经不平衡不再是一棵AVL树，需要调节平衡！
AVL树是高度平衡的二叉搜索树这个高度为什么设置为1，而不是0呢，因为存在某些特殊情况，高度无法达到0
AVL树整体结点数量和分布和完全二叉树类似，⾼度可以控制在logN，那么增删查改的效率也可 以控制在O(logN)，相比二叉搜索树有了本质的提升。
AVL树的插入
- 按照二叉搜索树的规则插入
- 根据新增的节点更新平衡因子
平衡因子的更新
更新规则：
- 平衡因⼦=右子树⾼度-左子树⾼度
- 只有⼦树高度变化才会影响当前结点平衡因⼦
- 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在 parent的左子树，parent平衡因⼦--
- parent所在子树的⾼度是否变化决定了是否会继续往上更新
更新停止条件：
【1】平衡因子为0
更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0，说明更新前parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束
【2】平衡因子为1/-1
更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响arent的⽗亲结点的平衡因⼦，所以要继续向上更新
- 更新到中间结点，3为根的⼦树⾼度不变，不会影响上⼀层，更新结束
- 最坏更新到根停⽌
【3】平衡因子为2/-2
更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束
选择的处理
旋转的原则
- 保持搜索树的规则
- 让旋转的树从不平衡变平衡，其次降低旋转树的⾼度
- 旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋
右单旋
具体的三种情况：
所有情况的概念图：
触发右单旋的条件：parent->_bf == -2 && cur->_bf == -1
右单旋的具体操作：5<b子树的数据<10，进行旋转时，我们将b子树作为10的左子树，然后10作为5的右子树，同样我们也需要更改他们的_parent节点，最后5节点和10节点的平衡因子为0
对于父亲指针的处理 ：
当我们完成上述的连接之后我们需要考虑subL的父亲节点是什么
- 1. 原本的parent是_root，那么新的subL将成为_root节点，其_parent->nullptr
- 2. 原本的parent是其他节点，那么subL的父亲节点需要判断原本的parent在他的_parent的左子树还是右子树，指向subL
左单旋
具体的三种情况：
其他情况处理与右单旋相似
左右双旋
具体情况例子：
以上如果我们只通过一个单旋操作是无法实现条件平衡的
- 先对subL进行一个左单旋，再对parent进行一个右单旋
- 根据图像观察我们可以发现，最后的步骤可以简化为将subLR的左子树给subL的右，bf++；subLR的右子树给parent的左，bf--； 我们只需要记录subLR的bf即可，如果subLR的bf为0，那么所有参与节点的bf最后都为0；如果subLR的bf为1，那么subL->_bf=-1；如果subLR的bf为-1，那么parent->_bf=1；
右左双旋
- 先对subR进行一个右单旋，再对parent进行一个左单旋
- 根据图像观察我们可以发现，最后的步骤可以简化为将subRL的右子树给subR的左，bf--；subRL的左子树给parent的右，bf++； 我们只需要记录subRL的bf即可，如果subRL的bf为0，那么所有参与节点的bf最后都为0；如果subRL的bf为1，那么parent->_bf=-1；如果subRL的bf为-1，那么subR->_bf=1；
代码示例：
C++_Test_AVLTree_2024_10_29 · 阳区欠/CPlusPlus学习仓库 - 码云 - 开源中国
原文地址：https://blog.csdn.net/2301_81577798/article/details/143335489
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！