AVL vs RED-BLACK tree

mjus · #1 (**permalink**) 2007-10-15

Regarding AVL & RB tree, I wonder who is better in terms of insert, find, delete, and overall (the named three actions). please provide your insight, thinking...
thank you !!!

cat · #2 (**permalink**) 2007-10-15

google到了这条:

The Old Joel on Software Forum - AVL Trees vs. Red-Black Trees?

里面这段说得不错，不过具体效率很重要的话还是测一下的好，实现得很烂的RB-tree可能就会比实现得很好的AVL tree快一点。

引用:

It's been a long time since any data structure lectures, but my understanding is that in an AVL tree the difference between the shortest and longest path to from the root to any leaf is at most one. In a red-black tree the difference can be a factor of 2.

Both of these give O(log n) for look up, but balancing an AVL tree can require O(log n) rotations, whilst a red black tree will take at most two rotations to bring it into balance (though it may have to examine O(log n) nodes to decide where the rotations are necessary). The rotations themselves are O(1) operations since you are just moving pointers around.

You might also want to look up 2-3-4 trees, or more generally B trees for more balanced tree data structures.

Rob Walker
Tuesday, December 17, 2002

mjus · #3 (**permalink**) 2007-10-16

To cat
实现得很烂的RB-tree可能就会比实现得很好的AVL tree快一点 ???
did you make a typo ?

cat · #4 (**permalink**) 2007-10-18

一直听说AVL调整比较复杂貌似会比RB-Tree慢一点吧。没测过说不准。这种同一个O下的性能优势可能因为某个的实现上的失误泡汤的吧。

mjus · #5 (**permalink**) 2007-10-20

please see & check the page below
Daniel K. O. - std::map and std:

et based on AVL, not RB trees.

it is based on the sgi style, STL compatible AVLmap. As I tested it.
it does surpass sgi::RBmap. really cool. but it seems not what the
books say (usually rb is better than avl -- most books say so ...).

主题工具
显示可打印版本邮寄本页给好友
显示模式
平板模式切换到混合模式切换到树形模式

相似的主题
主题	主题作者	版面	回复	最后发表
请问sicp 2.63题	tomato	算法	3	2006-05-03 11:57 PM
[请问]Expression tree和一般的tree有什么区别阿？	Karla	技术杂烩	2	2003-12-09 11:27 AM
functional的pattern match vs. OO的visitor vs. if/switch	ajoo	技术杂烩	49	2003-09-22 04:51 PM
与树实现无关的树iterator	ajoo	技术杂烩	74	2003-06-27 01:20 PM
从directory reader到tree iterator	papercrane	技术杂烩	2	2003-04-15 03:16 PM