Home > 编程技术 > AVL/RBTREE 实际比较

AVL/RBTREE 实际比较

网上对 AVL被批的很惨,认为性能不如 rbtree,这里给 AVL 树平反昭雪。最近优化了一下我之前的 AVL 树,总体跑的和 linux 的 rbtree 一样快了:

他们都比 std::map 快很多(即便使用动态内存分配,为每个新插入节点临时分配个新内存)。

项目代码在:skywind3000/avlmini
其他 AVL/RBTREE 评测也有类似的结论,见:STL AVL Map

谣言1:RBTREE的平均统计性能比 AVL 好

统计下来一千万个节点插入 AVL 共旋转 7053316 次(先左后右算两次),RBTREE共旋转 5887217 次,RBTREE看起来少是吧?应该很快?但是别忘了 RBTREE 再平衡的操作除了旋转外还有再着色,每次再平衡噼里啪啦的改一片颜色,父亲节点,叔叔,祖父,兄弟节点都要访问一圈,这些都是代价,再者平均树高比 AVL 高也成为各项操作的成本。

谣言2:RBTREE 一般情况只比 AVL 高一两层,这个代价忽略不计

纯粹谣言,随便随机一下,一百万个节点的 RBTREE 树高27,和一千万个节点的 AVL树相同,而一千万个节点的 RBTREE 树高 33,比 AVL 多了 6 层,这还不是最坏情况,最坏情况 AVL 只有 1.440 * log(n + 2) – 0.328, 而 RBTREE 是 2 * log(n + 1),也就是说同样100万个节点,AVL最坏情况是 28 层,rbtree 最坏可以到 39 层。

谣言3:AVL树删除节点是需要回溯到根节点

我以前也是这么写 AVL 树的,后来发现根据 AVL 的定义,可以做出两个推论,再平衡向上回溯时:

插入更新时:如当前节点的高度没有改变,则上面所有父节点的高度和平衡也不会改变。
删除更新时:如当前节点的高度没有改变且平衡值在 [-1, 1] 区间,则所有父节点的高度和平衡都不会改变。

根据这两个推论,AVL的插入和删除大部分时候只需要向上回溯一两个节点即可,范围十分紧凑。

谣言4:虽然二者插入一万个节点总时间类似,但是rbtree树更平均,avl有时很快,有时慢很多,rbtree 只需要旋转两次重新染色就行了,比 avl 平均

完全说反了,avl是公认的比rbtree平均的数据结构,插入时间更为平均,rbtree才是不均衡,有时候直接插入就返回了(上面是黑色节点),有时候插入要染色几个节点但不旋转,有时候还要两次旋转再染色然后递归到父节点。该说法最大的问题是以为 rbtree 插入节点最坏情况是两次旋转加染色,可是忘记了一条,需要向父节点递归,比如:当前节点需要旋转两次重染色,然后递归到父节点再旋转两次重染色,再递归到父节点的父节点,直到满足 rbtree 的5个条件。这种说法直接把递归给搞忘记了,翻翻看 linux 的 rbtree 代码看看,再平衡时那一堆的 while 循环是在干嘛?不就是向父节点递归么?avl和rbtree 插入和删除的最坏情况都需要递归到根节点,都可能需要一路旋转上去,否则你设想下,假设你一直再树的最左边插入1000个新节点,每次都想再局部转两次染染色,而不去调整整棵树,不动根节点,可能么?只是说整个过程avl更加平均而已。

比较结论

AVL / RBTREE 真的差不多,AVL被早期各种乱七八糟的实现和数学上的“统计”给害了,别盯着 linux 用了 rbtree 就觉得 rbtree 一定好过 avl了,solaris 里面大范围的使用 avltree ,完全没有 rbtree 的痕迹那。

补充测试

更新:有人比较疑惑 std::map 那么容易被超越么?无图无真相,给一下我测试的编译器和标准库版本吧,否则疑惑我在和 vc6 的 STL 做比较呢。

主要开发环境:mingw gcc 5.2.0

linux rbtree with 10000000 nodes:
insert time: 4451ms, height=32
search time: 2037ms error=0
delete time: 548ms
total: 7036ms

avlmini with 10000000 nodes:
insert time: 4563ms, height=27
search time: 2018ms error=0
delete time: 598ms
total: 7179ms

std::map with 10000000 nodes:
insert time: 4281ms
search time: 4124ms error=0
delete time: 767ms
total: 9172ms

linux rbtree with 1000000 nodes:
insert time: 355ms, height=26
search time: 171ms error=0
delete time: 46ms
total: 572ms

avlmini with 1000000 nodes:
insert time: 438ms, height=24
search time: 141ms error=0
delete time: 47ms
total: 626ms

std::map with 1000000 nodes:
insert time: 345ms
search time: 360ms error=0
delete time: 62ms
total: 767ms
又测试了一下 vs2017,结论类似:

linux rbtree with 10000000 nodes:
insert time: 4201ms, height=32
search time: 3411ms error=0
delete time: 567ms
total: 8179ms

avlmini with 10000000 nodes:
insert time: 4250ms, height=27
search time: 3233ms error=0
delete time: 658ms
total: 8141ms

std::map with 10000000 nodes:
insert time: 4658ms
search time: 4275ms error=0
delete time: 815ms
total: 9748ms

linux rbtree with 1000000 nodes:
insert time: 330ms, height=26
search time: 316ms error=0
delete time: 62ms
total: 708ms

avlmini with 1000000 nodes:
insert time: 409ms, height=24
search time: 266ms error=0
delete time: 53ms
total: 728ms

std::map with 1000000 nodes:
insert time: 426ms
search time: 375ms error=0
delete time: 78ms
total: 879ms

注意,avlmini 和 linux rbtree 都是使用结构体内嵌的形式,这样和 std::map 这种需要 overhead 的容器比较起来 std::map 太吃亏了,所以我测试时,每次插入 avlmini 和 linux rbtree 之前都会模拟 std::map 为每对新的 (key, value) 分配一个结构体(包含node信息和 key, value),再插入,这样加入了内存分配的开销,才和 std::map 进行比较。

参考:别人做的更多树和哈希表的评测 rcarbone/kudb

Categories: 编程技术 Tags:
  1. No comments yet.
  1. No trackbacks yet.