AVL树的实现代码
2009-10-29 11:58:55 来源:WEB开发网另外,关于AVL树,chinaunix的win_hate有一段herberteuler 精彩的讲述:
大家好,最近我完成了一个 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 树的实现了,所以比较乱,不过没关系,因为我的本意就是使用的时候将代码复制后修改,而不是使它成为通用的库。
更多精彩
赞助商链接