平衡二叉排序树.pptx
平衡二叉排序树
平衡二叉树DGEDABCFEGBA起因:提高查找速度,避免最坏情况出现。如右图情况的出现。CF平衡因子(平衡度):结点的平衡度是结点的左子树的高度-右子树的高度。平衡二叉树:每个结点的平衡因子都为+1、-1、0的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。
平衡二叉排序树——AV树定义:一棵平衡二叉排序树或者是空树,或者是具有下列性质的二叉排序树:左子树与右子树的高度之差的绝对值小于等于1;左子树和右子树也是平衡二叉排序树。平衡二叉排序树的平均查找长度为O(log2n)。平衡因子:结点的左子树深度与右子树深度之差:-1,0,1。
4030255020605840302560708050
141253928635360501718730+1+1-1-1-100000000是平衡树不是丰满树145392863536050171830+1+2-1-100000+1不是平衡树-1
以插入为例:在左图所示的平衡树中插入数据场为2的结点。插入之后仍应保持平衡分类二叉树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度为0危机结点如何用最简单、最有效的办法保持平衡分类二叉树的性质不变?
141253928635360501718730+1+1-1-1-1000000002+1+1+2危机结点如何用最简单、最有效的办法保持平衡分类二叉树的性质不变?解决方案:不涉及到危机结点的父亲结点,即以危机结点为根的子树的高度应保持不变(图为3)。新结点插入后,找到第一个平衡度不为0的结点(如左图结点9)即可。新插入的结点和第一个平衡度不为0的结点(也可能是危机结点)之间的结点,其平衡度皆为0。在调整中,仅调整那些在平衡度变化的路径上的结点(如:359),其它结点不予调整。仍应保持二叉排序树的性质不变。
141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度为0危机结点关键:将导致出现危机结点的情况全部分析清除,就可以使得平衡分类二叉树的性质保持不变!!14932528635360501718730+1+1-1-1-100000001200
不平衡二叉排序树的调整——LL型最低层失衡结点为A,在结点A的左子树的左子树上插入新结点S后,导致失衡,由A和B的平衡因子可知,BL、BR和AR深度相同,为恢复平衡并保持二叉排序树的特性,可将A改为B的右子,B原来的右子BR改为A的左子,这相当于以B为轴,对A做了一次顺时针旋转。ABBLSBRARBABLSBRAR
不平衡二叉排序树的调整——LL型4030256020AB15AB253020401560A-lchild=B-rchildB-rchild=A
不平衡二叉排序树的调整——LR型最低层失衡结点为A,在结点A的左子树的右子树上插入新结点S后,导致失衡,假设在CL下插入S,由A、B、C的平衡因子可知,CL与CR深度相同,BL与AR深度相同,且BL、AR的深度比CL、CR的深度大1;为恢复平衡并保持二叉排序树的特性,可将B改为C的左子,而C原来的左子CL改为B的右子,然后将A改为C的右子,C原来的右子CR改为A的左子;这相当于以B为轴,对A做了一次顺时针旋转。ABBLSCRARCLCCBBLSCRARCLA
不平衡二叉排序树的调整——LR型806040905020957085301045605040804520908570301095ABCCABA-lchild=c-rchildB-rchild=c-lchildc-rchild=Ac-lchild=B
不平衡二叉排序树的调整——RR型最低层失衡结点为A,在结点A的右子树的右子树上插入新结点S后,导致失衡,由A和B的平衡因子可知,BL、BR和AL深度相同,为恢复平衡并保持二叉排序树的特性,可将A改为B的左子,B原来的左子BL改为A的右子,这相当于以B为轴,对A做了一次逆时针旋转。ASBBLBRARBAALSBLBR
不平衡二叉排序树的调整——RR型3025204060AB703025204060AB70A-rchild=B-lchildB-lchild=A
不平衡二叉排序树的调整——RL型最低层失衡结点为A,在结点A的右子树的左子树上插入新结点S后,导致失衡,假设在CR下插入S,由A、B、C的平衡因子可知,CL与CR深度相同,AL与BR深度相同,且AL、BR的深度比CL、CR的深度大1;为恢复平衡并保持二叉排序树的特性,可将B改为C的右子,而C原来的右子CR改为B的左子,然