[数据结构]AVL 树的一个非递归实现

herberteuler

我发现我的工作总是遇到查找和插入，而且对效率的要求非常高。平衡的树是实现这样的目标的好方法。C++ 中的 STL 就是用平衡的树（红黑树）实现的。我不会 C++，又不想用第三方的库，所以我的选择就只有自己写一个了。不过我准备从 AVL 树开始。经过大量的尝试，得到了下面的程序。遗憾的是，我还没有写出在 AVL 树中删除一个结点的函数，因为用我现在的方法来分析那比较复杂。不过我仍在尝试，也许不久我就可以发一个 AVL 树的完整实现了。

我的实现是非递归的，这使得它的效率非常高。下面是对大规模数据（100,000,000 条）作插入操作的时间比较：

1. # modified version -- same outline as in GNU avl
   
2. [xgp@server64 algorithm]$ time ./a <etest
   
3. 
   
4. real    10m31.667s
   
5. user    10m17.473s
   
6. sys     0m13.992s
   
7. # linked with GNU avl
   
8. [xgp@server64 algorithm]$ time ./g <etest
   
9. 
   
10. real    11m53.265s
    
11. user    11m38.372s
    
12. sys     0m14.329s
    
13. # orignal version
    
14. [xgp@server64 algorithm]$ time ./a <etest
    
15. 
    
16. real    8m50.150s
    
17. user    8m39.265s
    
18. sys     0m10.516s
    
19. # same function program implemented with C++ STL
    
20. [xgp@server64 algorithm]$ time ./t <etest
    
21. 
    
22. real    12m5.207s
    
23. user    11m52.441s
    
24. sys     0m12.544s
    
25. [xgp@server64 algorithm]$
    

复制代码

第三个结果是我最初的版本（也就是这里贴的这个），它虽然不通用，但却是速度最快的一个。第二个是来自 GNU 的 AVL 树实现。第一个是我将我的实现修改为调用方法和 GNU 的 AVL 实现类似的方法以后程序的执行时间。最后一个是 C++ 中 STL 实现的执行时间；它其实使用了红黑树。

我会把我的思路写成文档。这会和删除的函数一些贴在这里。（释放树的结构我也没写，不过好在它们并不难。）

ideawu

支持。
我们的数据结构课程没有讲AVL树，我正想学呢。

herberteuler

本来我想等程序经过严格的测试以后再将它放到这里，无奈我在好几个地方贴了程序，愿意帮我测试的人一个都没有，所以我只好将_我认为没有问题的_程序放在这里了。这次的程序已经实现了删除操作；同以前一样，它的速度也是我知道的程序中最快的。

同时放在这里的还有我为 Windows 编译的可执行程序。运行后，输入 i 回车，再输入一个整数回车就可以向树中插入这个整数；输入 d 回车再输入一个整数回车就可以从树中删除这个整数。插入重复的整数和删除不存在的整数都没有效果。完成一次插入或删除以后，可以看到树的结构。

过段时间我会把实现的思路贴上来。

arxor

可以找个oj来测试,
比如http://acm.pku.edu.cn/JudgeOnline/
1002,2418没有用到删除
1823可以也用avl做,用到删除

herberteuler

我只是做了一下 1002。不过现在我好像连不上那个网址了，请帮我测试一下吧。
实在是不好意思。 :p

mingfal

没有太高的要求的话其实有个叫treap的东西编起来要简单的多。

arxor

Post by mingfal
没有太高的要求的话其实有个叫treap的东西编起来要简单的多。

nod, 随机函数好的话效率不错
还有skiplist也不错, 期望都是O(logn).

nuptlhj

我测试过了, 插入算法效率挺高的, 删除算法需要改进, 删除过程中会出错

mikeandmore

考虑效率的话，你可以试试SBT(Size Balanced Tree)。
于AVLTree不同的是AVL是根据树高的差来判断是否rotate，而SBT是根据树的size。。。

mikeandmore

http://www.mydatabus.com/public/sqybi/z/useSBT.pdf