|
我发现我的工作总是遇到查找和插入,而且对效率的要求非常高。平衡的树是实现这样的目标的好方法。C++ 中的 STL 就是用平衡的树(红黑树)实现的。我不会 C++,又不想用第三方的库,所以我的选择就只有自己写一个了。不过我准备从 AVL 树开始。经过大量的尝试,得到了下面的程序。遗憾的是,我还没有写出在 AVL 树中删除一个结点的函数,因为用我现在的方法来分析那比较复杂。不过我仍在尝试,也许不久我就可以发一个 AVL 树的完整实现了。
我的实现是非递归的,这使得它的效率非常高。下面是对大规模数据(100,000,000 条)作插入操作的时间比较:
- # modified version -- same outline as in GNU avl
- [xgp@server64 algorithm]$ time ./a <etest
-
- real 10m31.667s
- user 10m17.473s
- sys 0m13.992s
- # linked with GNU avl
- [xgp@server64 algorithm]$ time ./g <etest
-
- real 11m53.265s
- user 11m38.372s
- sys 0m14.329s
- # orignal version
- [xgp@server64 algorithm]$ time ./a <etest
-
- real 8m50.150s
- user 8m39.265s
- sys 0m10.516s
- # same function program implemented with C++ STL
- [xgp@server64 algorithm]$ time ./t <etest
-
- real 12m5.207s
- user 11m52.441s
- sys 0m12.544s
- [xgp@server64 algorithm]$
复制代码
第三个结果是我最初的版本(也就是这里贴的这个),它虽然不通用,但却是速度最快的一个。第二个是来自 GNU 的 AVL 树实现。第一个是我将我的实现修改为调用方法和 GNU 的 AVL 实现类似的方法以后程序的执行时间。最后一个是 C++ 中 STL 实现的执行时间;它其实使用了红黑树。
我会把我的思路写成文档。这会和删除的函数一些贴在这里。(释放树的结构我也没写,不过好在它们并不难。) |
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有帐号?注册
x
|