软测验点---平衡二叉树
在平衡二叉树
(Balanced binarytree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的,所以又称为AVL树。
一、平衡二叉树的基本介绍
定义:平衡二叉树或为空树,或为例如以下性质的二叉排序树:
(1)左右子树深度之差的绝对值不超过1;
(2)左右子树仍然为平衡二叉树.
平衡因子BF=左子树深度-右子树深度.
平衡二叉树每一个结点的平衡因子仅仅能是1。0,-1。
若其绝对值超过1。则该二叉排序树就是不平衡的。
查找、插入和删除在平均和最坏情况下都是O(log n)。添加和删除可能须要通过一次或多次树旋转来又一次平衡这个树。
如图所看到的为平衡树和非平衡树示意图:
(图一左为非平衡二叉树,图一右图为平衡二叉树)
二、平衡二叉树算法思想
若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系,使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后,原有其它全部不平衡子树无需调整,整个二叉排序树就又成为一棵平衡二叉树。
失去平衡的最小子树是指以离插入结点近期,且平衡因子绝对值大于1的结点作为根的子树。如果用A表示失去平衡的最小子树的根结点,则调整该子树的操作可归纳为下列四种情况。
(1)LL型平衡旋转法(右转)
因为在A的左孩子B的左子树上插入结点F,使A的平衡因子由1增至2而失去平衡。
故需进行一次顺时针旋转操作。即将A的左孩子B向右上旋转取代A作为根结点。A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。
图二(1)
图二(2)
(2)RR型平衡旋转法(左转)
因为在A的右孩子C的右子树上插入结点F,使A的平衡因子由-1减至-2而失去平衡。
故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转取代A作为根结点,A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。
图三(1)
图三(2)
(3)LR型平衡旋转法(先左后右)
因为在A的左孩子B的右子数上插入结点F,使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作(先逆时针,后顺时针)。
即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置。然后再把该D结点向右上旋转提升到A结点的位置。
即先使之成为LL型,再按LL型处理。
图四(1)
如图四中所看到的,即先将圆圈部分先调整为平衡树,然后将其以根结点接到A的左子树上,此时成为LL型,再按LL型处理成平衡型。
图四(2)
(4)RL型平衡旋转法(先右后左)
由的右孩子C的左子树上插入结点F,使A的平衡因子由-1减至-2而失去平衡。
故需进行两次旋转操作(先顺时针,后逆时针)。即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置,然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型,再按RR型处理。
图五(1)
如图五中所看到的,即先将圆圈部分先调整为平衡树,然后将其以根结点接到A的左子树上,此时成为RR型,再按RR型处理成平衡型。
图五(2)
(以上的四种节点包括了全部插入时导致不平衡的情况,图中所看到的不过平衡树插入后产生的最小不平衡子树)
平衡化靠的是旋转。參与旋转的是3个节点(当中一个可能是外部节点NULL),旋转就是把这3个节点转个位置。注意的是,左旋的时候p->right一定不为空,右旋的时候p->left一定不为空,这是显而易见的。
假设从空树開始建立,并时刻保持平衡。那么不平衡仅仅会发生在插入删除操作上,而不平衡的标志就是出现bf == 2或者bf == -2的节点。8
例:在平衡二叉树中插入一个结点后造成了不平衡。设最低的不平衡结点为A,而且A的左孩子的平衡因子为-1,右孩子的平衡因子为0。则使其平衡的调整方法为( )
A.LL型 B.LR型
C.RL型 D.RR型
解:由图四(1)显然答案选B
(个人角度理解,如果错误还请指教读者)
相关文章
- Java 第十一届 蓝桥杯 省模拟赛 第十层的二叉树
- Lintcode---二叉树的序列化和反序列化
- Lintcode---二叉树的最小深度
- Lintcode---把排序树组转换为高度最小的二叉树
- Lintcode---二叉树的路径和
- python数据结构之二叉树的统计与转换实例
- 二叉树 Java 实现 前序遍历 中序遍历 后序遍历 层级遍历 获取叶节点 宽度 ,高度,队列实现二叉树遍历 求二叉树的最大距离
- 二叉树的后序遍历(C++)
- 【剑指offer专题】3重建二叉树
- [LeetCode] 671. 二叉树中第二小的节点 ☆(递归 合并)
- 经典平衡二叉树(AVL树)
- 二叉树的非递归遍历--京东2015笔试回顾
- 二叉树(12)----查找两个节点最低祖先节点(或近期公共父节点等),递归和非递归
- 剑指 Offer 27. 二叉树的镜像