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

【证毕】9.3.3 L树从前面的讨论可知，由同一个关键字集合所生成的众多二叉排序树中，最佳二叉排序树具有最佳的查找性能，但这种“最佳性”却是静态的，也就是说，随着结点的不断插入与删除，这种“最佳性”可能会遭到破坏，从而导致二叉排序树的查找性能下降。例9.8 如图9-10所示的最佳二叉排序树，经过插入关键字12和14之后，就会出现这种情况，这时它已不再是最佳二叉排序树了 参见图9-12 。这里我们仍讨论被查找所有关键字在概率相等的情况下，如何动态地使一棵二叉排序树保持平衡，从而有较高的查找效率的问题。一、L树的定义1962年，阿德尔森一维尔斯基 G.M.Adel'son-Vel'skii 和兰迪斯 E.M.Landis 提出了一种动态保持二叉排序树的平衡、使其具有较高性能的方法。并把这种二叉排序树用他们的名字缩记为L树。下面给出几个概念：二叉树的高度是二叉树中树叶的最大层数，也就是从根到叶的最大路径长度。空的二叉树高度定义为 -1。L树是所有结点的左子树和右子树高度之差的绝对值不超过1的二叉排序树。例9.9 图9-13 a 是一棵L树，而图9-13 b 却不是。结点的平衡因子 balance factor 定义为结点的右子树高度减去左子树高度。

显然，L树中结点的平衡因子只能取值为 -1, 0, +1。为了表示起来方便，在图示中分别表示为 -,·, +。因为以下的讨论与结点的平衡因子有密切的关系，为了能明显地反映出结点的平衡因子的情况，在图示中我们把平衡因子写在表示结点的圆圈之内，而把结点的关键字写在圆圈之外，图9-14给出了这种表示形式。在用lchild-rchild表示法存储L树时，每个结点不仅要存贮key, …, lchild, rchild, 而且要存储平衡因子bf。结点的形式为由于L树是一种特殊的二叉排序树，有关二叉排序树的查找、插入和删除运算前面已经讲过。这里主要对插入和删除结点时，为保持L树的动态平衡而做的调整 旋转动作 进行讨论。二、L树的平衡旋转为保持L树的平衡，在插入新结点时，必须对树的结构作必要调整。若插入一个新结点作树叶，相应子树的根结点变化大致有三类：? 结点原来是平衡的，现在成为左重或右重的了，此时这个结点的前驱结点的状态也要发生变化。? 结点原来是某一边重的，而现在成为平衡的了，此时前驱结点不改变状态，因为这个子树的高度没变。? 结点原来就是左重或右重的，而新结点又插入到重的一边，此时这个结点不再满足L树条件，我们把这样的结点称作“危急结点”。

此时必须调整树的结构，使之平衡化。平衡旋转有两类：单旋转 single rotation 和双旋转 double rotation 。而每一类又含有对称的两种，所以共有四种，分别称为LL型 见图9-15 、RR型 见图9-16 和LR型 见图9-17 、RL型 见图9-18 。其中前两种属于单旋转，而后两种属于双旋转。在图9-15 ～ 图9-18中，图中大的长方框α，β，γ，δ表示子树，旁边注明了子树的高度。⑴ LL型的单旋转如果是由于在结点A的左子女B的左子树中插入新结点，使A的平衡因子由 -1变成-2，则需要进行LL型的平衡旋转：视结点B、A在同一圆弧上，以它们的圆心为轴心做顺时针旋转 右转 ，即B的右子树作为A的左子树，A作为B的右子女。 图9-15是LL型平衡旋转的情况，图9-15 a 是新结点插入前L树的形状，图9-15 b 是新结点插入后L树的形状，图9-15 c 是进行LL型的平衡旋转后L树的形状。⑵ RR型的单旋转这种旋转和LL型单旋转是对称的。如果是由于在结点A的右子女B的右子树中插入新结点，使A的平衡因子由+1变成+2，则需要进行RR型的平衡旋转：视结点B、A在同一圆弧上，以它们的圆心为轴心做逆时针旋转 左转 ，即B的左子树作为A的右子树，A作为B的左子女。

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