数据结构（陈仲民）第八章二叉排序树等.pptVIP

张乃孝 算法与数据结构——C语言描述 二叉排序树结点的删除 删除二叉排序树的某个指定结点后，仍然要是二叉排序树。 分3种情况讨论： 若*p是叶子结点，由于删除叶子结点不破坏整棵树的结构，因此，只需要修改其双亲结点的指针。 3. 若*p的左右子树均不空，则从下图可知,在删除 *p 之前，中序遍历该二叉树得到的序列为 {…L *p R …} 删除*p之后，为保持其它元素之间的相对位置不 变，可以有两种做法： 构造最佳二叉排序树的过程： 构造包含一个内部结点的最佳二叉排序树， T(0,1), T(1,2),…,T(n-1,n) 构造包含二个内部结点的最佳二叉排序树， T(0,2), T(1,3),…,T(n-2,n) ……, 直到最后构造T(0,n) 。 上面的几种情况在经过平衡旋转处理后，以*b 或*c为根的新子树为平衡二叉排序树，而且它的深度和插入之前以*a为根的子树相同。因此，当平衡的二叉排序树因插入结点而失去平衡时，仅需对最小不平衡子树进行旋转处理即可。 补充：AVL树的删除方法** 二叉排序树的删除+调整平衡 找最小不平衡子树 一棵m阶的B树，或为空树，或是满足下列特性： （1）树中每个结点至多有m棵子树； （2） 除根之外的所有分支结点至少有?m/2?棵子树； （3）若根结点不是叶子结点，则至少有两棵子树； （4） 所有叶子结点都在同一层上，实际上这些结点不存在（不属于索引树）。 （5） 有j个子女的非叶结点中恰好有j-1个关键码， 且 按递增顺 序排列，结点中包含的信息为 (p0, k1, p1, k2, …, kj-1, pj-1) 可如下实现“分裂”： 假设一个6阶B树的*p结点经过插入含有信息为： *p ： 6, p0, (10,p1), (20,p2) (30, p3), (40, p4), (50, p5), (60, p6) 将这个结点分裂为*p和*q两个结点，分别含有信息为： *p ： 2, p0, (10,p1), (20,p2) *q：3, p3, (40, p4), (50, p5), (60, p6), 把(30, q),插入到原来*p的父结点中。 假设(5 , p) 在原来*p的父结点中（保持不变） 调整方法： 设父结 点 中的信息为： （p0, k1,p1,k2,p2,…,kxpx), 由pi指向被删除关键码的结点，其的信息为： （p ? 0, k ?1,p ?1,k ? 2,p ?2,…,k ? y p ? y), 左（右）兄弟结点中的信息为： （p ? 0, k ?1 ,p ? 1 ,k ? 2 ,p ?2 ,…,k ?z p ? z)。z= ?m/2? 则应将k ? ?(z+y)/2+1? （或k ? ?(z-y)/2? ）上移到父结点中，并将左（或右）兄第中大于（或小于） k ? ?(z+y)/2+1? （或k ? ?(z-y)/2? ）及父结点中的ki移 到被删除关键码的结点中。 最小不平衡子树: 指离插入结点最近，且以平衡因子绝对值大于1的结点为根的子树。 27 10 51 18 41 25 0 0 1 1 -1 -2 最小 不平衡子树 插入结点 8.6.1 调整平衡的模式 设最小不平衡子树的根为A，调整的规律可归纳 为下列四种： 1. LL型调整； 2. RR型调整； 3. LR型调整； 4. RL型调整； LL型调整操作示意图 (αBβ)A(γ)= (α)B(βAγ) 调整规则是∶将A的左子女B提升为新二叉树的根；原来的根A连同其右子树γ向右下旋转成为B的右子树；B的原右子树β作为A的左子树。 27 10 0 1 B A 27 10 0 1 B A 05 2 27 10 0 0 B A 05 0 51 27 0 1 B A 10 0 ? 05 18 0 0 03 0 1 1 2 ? ? 51 27 0 B A 10 0 ? 05 18 0 03 0 1 0 ? ? 图 LL型调整操作示例 RR型调整操作示意图 (α)A(βBγ)= (αAβ)B(γ) 调整规则：将A的右子女B提升为新二叉树的根；原来的根A连同其左子树向左下旋转成为B的左子树；B的原左子树作为A的右子树。