平衡二叉排序树.ppt

平衡二叉排序树平衡二叉树DGEDABCFEGBA起因：提高查找速度，避免最坏情况出现。如右图情况的出现。CF平衡因子（平衡度）：结点的平衡度是结点的左子树的高度－右子树的高度。平衡二叉树：每个结点的平衡因子都为＋1、－1、0的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。平衡二叉排序树——AV树定义：一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树：左子树与右子树的高度之差的绝对值小于等于1；左子树和右子树也是平衡二叉排序树。平衡二叉排序树的平均查找长度为O（log2n）。平衡因子：结点的左子树深度与右子树深度之差：-1，0，1。4030255020605840302560708050141253928635360501718730+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后，导致失衡，由