平衡二叉树(AVL树)
3、旋转
在进行插入和删除之前需要先了解AVL树的旋转操作。旋转操作主要包括LL(左左)旋转、LR(左右)旋转、RR(右右)旋转、RL(右左)旋转,LL旋转与RR旋转对称,LR旋转与RL旋转对称。旋转操作是在插入结点或删除结点导致原AVL树不平衡时进行的。我的理解是当二叉树失衡的原因出现在“最低失衡根结点左子树的左子树”(所谓“最低失衡根结点”,则是从新增结点开始向根部回溯,所遇到的第一个失衡的根节点)时,则使用LL旋转来调整;当失衡出现在“最低失衡根节点左子树的右子树”,则使用LR旋转调整;RR旋转,RL旋转同理。具体的定义和操作可以看skywang12345的的文章:AVL树(二)之 C++的实现(我的这篇文章就是基于此文章,为了加深印象,在这里把实现再写一遍,加一些自己的理解)。
3.1 LL旋转
如上图所示,找到“最低失衡根结点”,上图是结点5,二叉树失衡的原因是因为结点1的存在,而结点1位于结点5“左子树的左子树”,所以要使用LL旋转来调节,只需一次旋转即可达到平衡。具体的方法是:LL旋转的对象是“最低失衡根结点”,也就是结点5,找到5的左孩子3,将3的右孩子4变成5的左孩子,最后将5变成3的右孩子,调整后的AVL树如下所示:
具体代码:
3.2 RR旋转
RR旋转与LL旋转对称。
如上图所示,“最低失衡根结点”是结点2,二叉树的失衡是结点6导致的,而结点6位于结点2“右子树的右子树”,所以要使用RR旋转来调节,只需一次旋转即可达到平衡。方法与LL旋转类似:RR旋转的对象是“最低失衡根结点”,这里是结点2,找到2的右孩子4,将4的左孩子3变成2的右孩子,最后将2变成4的右孩子,旋转后的结果如下图所示:
RR旋转代码如下:
3.3 LR旋转
LL旋转和RR旋转只需一次旋转即可达到平衡,而LR旋转和RL旋转需两次旋转才能达到平衡。
如上图所示,“最低失衡根结点”为结点5,二叉树失衡是因为结点3的存在,结点3位于结点5“左子树的右子树”,所以使用LR旋转来调节。方法:(1)先对最低失衡根结点的左孩子(结点2)进行RR旋转;(2)再对最低失衡根结点(结点5)进行LL旋转。下图演示了调整过程。
LR代码如下:
3.4 RL旋转
RL旋转与LR旋转对称,先LL旋转,在RR旋转。
分析过程与LR相似。旋转步骤:(1)先对最低失衡结点右孩子(结点5)LL旋转;(2)在对最低失衡结点(结点2)RR旋转。旋转过程如下:
RL实现代码:
4、插入结点与删除结点
https://www.cnblogs.com/sench/p/7786718.html
相关文章
- 【算法】【二叉树模块】判断二叉树是否是平衡二叉树
- 二叉树中第二小的节点
- 从上到下打印二叉树1
- 平衡搜索二叉树BST底层的增删改查原理,左旋右旋的目的
- 判断二叉树是否为满二叉树
- python学习之二叉树的实现详解
- [leetcode]面试题55 - I. 二叉树的深度
- 剑指 Offer 68 - II. 二叉树的最近公共祖先
- 层序创建二叉树
- 浅析索引为什么可以加快查询速度:计算机存储原理、索引是什么、索引数据结构、平衡二叉树/B树/B+树、二分查找法、索引的弊端、聚集索引、索引失效的例子
- 数据结构 | 链式二叉树【递归的终极奥义】
- LeetCode搜索二叉树的练习
- 94、【树与二叉树】leetcode ——110. 平衡二叉树(C++版本)
- 【剑指offer】4.重建二叉树
- 【历史上的今天】1 月 8 日:谷歌推出 Google Pay;Quibi 的重生;平衡二叉树的发明者出生
- [LeetCode] 894. All Possible Full Binary Trees 所有可能的满二叉树
- [CareerCup] 4.1 Balanced Binary Tree 平衡二叉树
- 二叉树的前序遍历,中序遍历,后序遍历学习 (原)
- leetcode算法110.平衡二叉树