开发学院软件开发数据结构 AVL树的实现代码 阅读

AVL树的实现代码

 2009-10-29 11:58:55 来源:WEB开发网   
核心提示:另外,关于AVL树,chinaunix的win_hate有一段herberteuler 精彩的讲述:大家好,最近我完成了一个 AVL 树的实现,AVL树的实现代码(2),这个实现是非递归的,包含了添加和删除这两个功能,不过没关系,因为我的本意就是使用的时候将代码复制后修改,事实上,对 AVL 树的其他操作都不困难

另外,关于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 树的实现了,所以比较乱,不过没关系,因为我的本意就是使用的时候将代码复制后修改,而不是使它成为通用的库。

上一页  1 2 

Tags:AVL 实现 代码

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接