AVL树的实现代码

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