二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(11)

图9-16是RR型平衡旋转的情况，图9-16 a 是新结点插入前L树的形状，图9-16 b 是新结点插入后L树的形状，图9-16 c 是进行RR型的平衡旋转后L树的形状。⑶ LR型的双旋转如果是由于在结点A的左子女B的右子树 其根为X 中插入新结点，使A的平衡因子由-1变成-2，则需要进行LR型的平衡旋转。这实际上是两次单旋转的复合，先做一次RR型的单旋转、再做一次LL型的单旋转：首先视结点X、B在同一圆弧上，以它们的圆心为轴心做逆时针旋转 左转 ，即X的左子树作为B的右子树，B作为X的左子女；然后视结点X、A在同一圆弧上，以它们的圆心为轴心做顺时针旋转 右转 ，即X的右子树作为A的左子树，A作为X的右子女。图9-17是LR型平衡旋转的情况，图9-17 a 是新结点插入前L树的形状，图9-17 b 是新结点插入后L树的形状，图9-17 c 是进行LR型的平衡旋转后L树的形状。⑷ RL型的双旋转这种旋转和LR型双旋转也是对称的。如果是由于在结点A的右子女B的左子树 其根为X 中插入新结点，使A的平衡因子由 +1变成 +2，则需要进行RL型的平衡旋转。这也是两次单旋转的复合，先做一次LL型的单旋转、再做一次RR型的单旋转：首先视结点X、B在同一圆弧上，以它们的圆心为轴心做顺时针旋转 右转 ，即X的右子树作为B的左子树，B作为X的右子女；然后视结点X、A在同一圆弧上，以它们的圆心为轴心做逆时针旋转 左转 ，即X的左子树作为A的右子树，A作为X的左子女。

图9-18是RL型平衡旋转的情况，图9-18 a 是新结点插入前L树的形状，图9-18 b 是新结点插入后L树的形状，图9-18 c 是进行RL型的平衡旋转后L树的形状。三、L树的插入与删除往L树中插入一个新结点 *q的基本方法是：⑴ 按前面讲述的二叉排序树的插入方法插入新结点，并用指针s指向根到新插入结点的路径上最后一个平衡因子不为0的结点；若此路径上不存在这样的结点，则指针s指向根。⑵ 修改平衡因子：用新结点 *q的关键字与从结点 *s到 *q的双亲结点的有向路径上的各结点逐个进行比较，如果新结点 *q的关键字小于路径上结点的关键字，则路径上结点的平衡因子减1；否则路径上结点的平衡因子加1。⑶ 若结点 *s的平衡因子绝对值为2，则 *s为“危急结点”，说明二叉排序树失去平衡，这时再根据结点 *s与它在这条路径上子女的平衡因子符号值来确定平衡旋转的类型：若同号则做单旋转；若反号则做双旋转。从空树开始，不断地用上述方法插入结点就可以建立起L树。例9.10 设输入的关键字序列为 25, 10, 5, 30, 35, 15, 2, 12, 20 ,18 ，图9-19给出了从空树开始按关键字在此序列的自左至右的顺序依次插入各结点并进行调整的过程。

为了图示清晰起见，我们把结点的关键字写在表示结点的圆圈之内，而把结点的平衡因子写在圆圈之外，并直接标注平衡因子的值。在L树上进行删除操作时，同样有需要平衡旋转来做调整的问题。其基本方法为：⒈ 按前面讲述的二叉排序树的删除方法?、?' 删除指定结点 *p：若为情形 ?，则删除后让p仍指向原来子树 即原来以被删结点为根的子树 变化后的根位置；若为情形 ?'，则删除后让p仍指向原来它的中序前驱 *r为根的子树变化后的根位置。如果这时p为空，则它的双亲结点的相应指针置为NULL即可。⒉ 修改平衡因子及平衡旋转：将以现在*p指向结点为根的子树的高度减1，并沿 *p到根的路径反向追踪由删除引起的 子 树的高度的变化对路径上各结点 *p的影响， 即让p沿着这条反向路径逐层地指向更高辈分的祖先结点，并分以下情况进行平衡化处理：情况 ⑴：当前结点 *p的平衡因子为0。如果它的左子树或右子树被缩短，则它的平衡因子改为 +1或 -1。图9-20 1 所示的是 *p的左子树被缩短、平衡因子改为 +1的情形。情况 ⑵：结点 *p的平衡因子不为0，且其较高的子树被缩短，则 *p的平衡因子改为 0。图9-20 2 所示的是 *p的左子树的高度被缩短、平衡因子改为0的情形。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-11.html