（精）平衡二叉排序树.ppt

平衡二叉排序树 平衡二叉树 平衡二叉排序树——AV树 不平衡二叉排序树的调整——LL型 最低层失衡结点为A，在结点A的左子树的左子树上插入新结点S后，导致失衡，由A和B的平衡因子可知，BL、BR和AR深度相同，为恢复平衡并保持二叉排序树的特性，可将A改为B的右子，B原来的右子BR改为A的左子，这相当于以B为轴，对A做了一次顺时针旋转。 不平衡二叉排序树的调整——LL型 不平衡二叉排序树的调整——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做了一次顺时针旋转。 不平衡二叉排序树的调整——LR型 不平衡二叉排序树的调整——RR型 最低层失衡结点为A，在结点A的右子树的右子树上插入新结点S后，导致失衡，由A和B的平衡因子可知，BL、BR和AL深度相同，为恢复平衡并保持二叉排序树的特性，可将A改为B的左子，B原来的左子BL改为A的右子，这相当于以B为轴，对A做了一次逆时针旋转。 不平衡二叉排序树的调整——RR型 不平衡二叉排序树的调整——RL型 最低层失衡结点为A，在结点A的右子树的左子树上插入新结点S后，导致失衡，假设在CR下插入S，由A、B、C的平衡因子可知，CL与CR深度相同，AL与BR深度相同，且AL、BR的深度比CL、CR的深度大1；为恢复平衡并保持二叉排序树的特性，可将B改为C的右子，而C原来的右子CR改为B的左子，然后将A改为C的左子，C原来的左子CL改为A的右子；这相当于以B为轴，对A做了一次顺时针旋转。 不平衡二叉排序树的调整——RL型 思考：此树是否为平衡二叉树，在此二叉树中插入结点7后，该树是否为平衡二叉树，若不平衡，如何调整 一棵5阶的B-树，其深度为4 历届题目： m阶B-树是一棵( ) 【北京邮电大学 2000 二、2 （20/8分）】 A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 下面关于m阶B树说法正确的是( ) 【南京理工大学 1999 一、5 （2分）】 ①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。 A． ①②③ B. ②③ C. ②③④ D. ③ 高度为4的3阶b-树中，最多有__________个关键字。【合肥工业大学 2000 三、9 （2分）】 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。 【中国科技大学 1998 一、5 （3分）】【南京理工大学 2001 二、4 （3分）】  * * D G E D A B C F E G B A 起因：提高查找速度，避免最坏情况出现。如右图情况的出现。 C F 平衡因子（平衡度）：结点的平衡度是结点的左子树的高度－右子树的高度。 平衡二叉树：每个结点的平衡因子都为 ＋1、－1、0 的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。 定义： 一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树： 1、左子树与右子树的高度之差的绝对值小于等于1； 2、左子树和右子树也是平衡二叉排序树。 平衡二叉排序树的平均查找长度为O（log2n）。 平衡因子：结点的左子树深度与右子树深度之差：-1，0，1。 40 30 25 50 20 60 58 40 30 25 60 70 80 50 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 是平衡树不是丰满树 14 5 3 9 28 63 53 60 50 17 18 30 +1 +2 -1 -1 0 0 0 0 0 +1 不是平衡树 -1 以插入为例： 在左图所示的平衡树中插入数据场为 2 的结点。 插入之后仍应保持平衡分类二叉树的性质不变。 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 平衡树 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 2 +1