- 论坛徽章:
- 0
|
原帖由 albcamus 于 2006-1-20 10:37 发表
P.S. AVL树的Rotation原理何在， 数学依据何在， 看书的时候想破脑袋也没想明白。。
我解释一下，看会不会越说越糊涂...... 
平衡二叉（排序）树的旋转有两个特点，其一是旋转后仍然是二叉排序树；其二是旋转后变成平衡的。其中令人迷惑的主要是第一点。
对于一组元素，不妨设为 1,2...n，可以组织到一棵二叉排序树中，这样的二叉排序树有很多，但它们有一个共同的特点：若以中序访问该树，得到的序列是 1,2... n.
在不同二叉排序树的背后，如果说包含了某种数学规律，那必定是所谓的``结合律''。归根到底，二叉排序树的组织不过是在一串数中加入括号，控制结合方式罢了。
例1：
设有两棵二叉排序树 A，B，其中 A 的节点均小于 B 的节点，则 A，B 可合并成一棵二叉排序树 AB. 考虑结合的方式，设 A=A'x (也即 x 为中序访问 A的最后一个节点),则
AB=A'xB = A'(xB) = (A')x(B)
（这里的符号有点混淆，但你可以选取其中一种解释，这些解释对应了不同的二叉排序树。）
A'(xB) 表示把 B 作为 x 的右子树，
(A')x(B) 表示把 x 作为整棵树的根，A',B 分别为左右子树。
建议动手画一画，这种实际经验非常重要，光看文字是得不到的。
关键点：
1） 中序遍历得到增序，
2) 同一组元素的不同二叉排序树本质上对应了这组元素增序的不同结合方式。若给定元素组为 1，2，...n，则可截之成为若干段，每段形成一棵二叉排序树，并依次合并成一棵大树。若给定了一棵二叉排序树，可把一些分枝剪下，并重新组织(园丁的技能)。
例2: (小写为节点，大写为子树)
比如 AxByC 无论如何结合，先访问 A，再访问 x, B，y, C
现在我们再来考虑平衡二叉树，插入一个节点后，若引发节点失衡，则从插入点上溯，直到第一个失衡点 y，其平衡因子绝对值为 2。若为－2，则插人在y的右子树，称 R型；反之称 L型。这里仅讨论 L 型。
用 F 表示树(根节点)的平衡因子，h 表示树的高度。设从 y 起的子树为 T=(AxB)yZ
[LL 型] 其中新节点已经插入在 A 中。设 h(A)=l, 容易推导出：
h(A)=l, h(B)=l-1, h(Z) = l-1, h(AxB)=max{h(A),h(B)}+1=l+1, h(T)=l+2,
F(T)=2, F(AxB)=1, F(A),F(B),F(Z) in [-1,1]
把 T 割成五个部分：A,x,B,y,Z，由于结合律成立，我们可以轻易得到另一种组织方式：
Ax(ByZ)
此时h(A)=l, h(ByZ) = max{h(B),h(Z)}+1 = l
F(Ax(ByZ)) = h(A)-h(ByZ) = 0, F(ByZ) = h(B)-h(Z)=0, F(A), F(B), F(Z) in [-1,1]。
此时 h(Ax(ByZ))= max{h(A),h(ByZ)}+1 = l+1
此时 T 已经平衡，而 T 在新节点插入前，高度为 l+1, 插入后为 l+2，重组后为 l+1, 因此 T 的高度没有最终没有发生变化。所以对整棵数的其它部分没有影响。
建议画个图对比看一看。有结合律后，不用画图也可以得到结果，这是一个优点，但只有画过图，理解得才深刻。
[LR 型]: 即新节点插入在 B 中，设 h(B)=l, 容易推出：
h(A)=l-1, h(B)=l, h(Z)=l-1, h(AxB)=l+1, h(T)=l+2
F(T)=2, F(AxB)=-1, F(A), F(Z) F(B) in [-1,1]
容易发现象 LL 型那样割开五份不好使了，因为 AxByZ 中， h(A)=h(Z)，(AxB)yZ 与 Ax(ByZ) 是对称的，Ax(ByZ) 成 RR 型了。这时要把 B 割开为 CbD, b 为 B 的根节点。
设新节点插入在 C 中，则 h(C)=l-1, h(D)=l-2 （C,D 高度不等，否则 B 的高度在插入前后不变，不会使 y 失衡）。
T=(AxCbD)yZ = (AxC)b(DyZ)
子树的根节点从 y 变成了 b.
h(AxC)=l, h(DyZ)=l, h((AxC)b(DyZ))=l+1
F(AxC)=0, F(DyZ)=-1, F((AxC)b(DyZ))=0
因为插入前 T高度为 l+1, 插入后高度为 l+2，重组后高度为 l+1, T 的高度最终没有变化，对整棵树的其他部分没有影响。
[ 本帖最后由 win_hate 于 2006-1-21 15:49 编辑 ] |
评分
-
查看全部评分
|
免费注册
发表于 2006-01-20 10:27
