Chinaunix

标题: 请帮忙测试一下这个 AVL 树的实现 [打印本页]

作者: herberteuler 时间: 2006-01-20 10:27
标题: 请帮忙测试一下这个 AVL 树的实现
大家好，最近我完成了一个 AVL 树的实现。这个实现是非递归的，包含了添加和删除这两个功能。事实上，对 AVL 树的其他操作都不困难，因此需要特别实现的操作也就只有这两个了。我对这个实现的正确性和速度都作了测试，效果非常理想。我对 100,000,000 条随机数据的测试并没有显示出这个实现有错误。另一方面，它的速度非常快，超过了已有的同类实现。我主要与 GNU libavl 和 C++ STL 中的红黑树作了比较。下面是对 100,000,000 条随机数据作操作时 GNU libavl 的执行时间：

[xgp@server64 algorithm]$ time ./g <etest

real 11m53.265s
user 11m38.372s
sys    0m14.329s

另一段用 C++ STL 完成的程序在同一组数据上的执行时间是：

[xgp@server64 algorithm]$ time ./t <etest

real 12m5.207s
user 11m52.441s
sys    0m12.544s

不过把 C++ 程序的执行结果放在这里并不公平，因为红黑树的限制比 AVL 树小，如果用 C 实现红黑树，速度会比用 C 实现的 AVL 树更快。我的目的是考察一下 C++ 程序的执行速度。

我的程序的执行时间是：

[xgp@server64 algorithm]$ time ./a <etest

real 8m50.150s
user 8m39.265s
sys    0m10.516s

快得这么多是因为 GNU libavl 使用了 qsort 和 bsearch 的机制使其更加通用，而我的程序则不是通用的。将调用的机制修改为与 GNU libavl 相同以后，我发现我的程序仍然比 GNU libavl 要快。下面是修改后的程序的执行时间：

[xgp@server64 algorithm]$ time ./a <etest

real 10m31.667s
user 10m17.473s
sys    0m13.992s

所有这些都使我相信我的实现可以工作得非常好。但由于使用随机数据测试并不保险，我的想法也可能不全面，我希望这个实现能够经过更加严格的测试。现在我把源代码放在这里，请有兴趣的朋友帮忙检验它的正确性和健壮性，谢谢。

注：从 #include <stdio.h> 开始的代码就不属于 AVL 树的实现了，所以比较乱，不过没关系，因为我的本意就是使用的时候将代码复制后修改，而不是使它成为通用的库。

avl_tree.zip

3.53 KB, 下载次数: 1128

AVL 树的实现

作者: albcamus 时间: 2006-01-20 10:37
算法不够好，帮不上忙。 win_hate、yuxh几位老大快来阿！

P.S. AVL树的Rotation原理何在，数学依据何在，看书的时候想破脑袋也没想明白。。

作者: emacsnw 时间: 2006-01-20 11:19

原帖由 albcamus 于 2006-1-19 18:37 发表
算法不够好，帮不上忙。 win_hate、yuxh几位老大快来阿！

P.S. AVL树的Rotation原理何在，数学依据何在，看书的时候想破脑袋也没想明白。。

看看下面这个连接有没有什么帮助。
http://www.cse.ohio-state.edu/~g ... Ch10.html#QQ1-42-70

作者: converse 时间: 2006-01-20 11:38

原帖由 emacsnw 于 2006-1-20 11:19 发表

看看下面这个连接有没有什么帮助。
http://www.cse.ohio-state.edu/~g ... Ch10.html#QQ1-42-70

好东西,收下了~~

作者: win_hate 时间: 2006-01-21 15:36

原帖由 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 编辑 ]

作者: emacsnw 时间: 2006-01-21 16:26

原帖由 win_hate 于 2006-1-20 23:36 发表

我解释一下，看会不会越说越糊涂......

平衡二叉（排序）树的旋转有两个特点，其一是旋转后仍然是二叉排序树；其二是旋转后变成平衡的。其中令人迷惑的主要是第一点。

对于一组元素，不妨设为 ...

精彩之至！

作者: albcamus 时间: 2006-01-21 21:40

原帖由 win_hate 于 2006-1-21 15:36 发表

我解释一下，看会不会越说越糊涂......

平衡二叉（排序）树的旋转有两个特点，其一是旋转后仍然是二叉排序树；其二是旋转后变成平衡的。其中令人迷惑的主要是第一点。

对于一组元素，不妨设为 ...

這個……偶一時看不懂，晚上回去再仔細看. 先謝謝老大

作者: shelleycao 时间: 2006-07-14 15:18
请问如何打印avl树的图形啊？字符格式那种。可以看清树的结构。多谢。
我用一个队列，进行按层次访问，可是最后缩进总是弄不出来。能不能给个代码。
谢谢。

[ 本帖最后由 shelleycao 于 2006-7-14 15:21 编辑 ]

作者: dogygb 时间: 2008-10-13 20:36
标题: 回复 #5 win_hate 的帖子
写的太好了，拜读了谢谢

作者: crspo 时间: 2008-10-14 22:32

原帖由 win_hate 于 2006-1-21 15:36 发表

我解释一下，看会不会越说越糊涂......

平衡二叉（排序）树的旋转有两个特点，其一是旋转后仍然是二叉排序树；其二是旋转后变成平衡的。其中令人迷惑的主要是第一点。

对于一组元素，不妨设 ...

解释的很精辟，谢谢

作者: maxxfire 时间: 2008-10-15 03:24

原帖由 win_hate 于 2006-1-21 15:36 发表

我解释一下，看会不会越说越糊涂......

平衡二叉（排序）树的旋转有两个特点，其一是旋转后仍然是二叉排序树；其二是旋转后变成平衡的。其中令人迷惑的主要是第一点。

对于一组元素，不妨设 ...

不错不错，相当的有创意。。

作者: windlyboy 时间: 2009-01-13 17:35
标题: 支持
学习了，谢谢！

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)