On Thu, May 19, 2011 at 07:33:22PM +0200, Mike Belopuhov wrote:
> On Thu, May 19, 2011 at 7:25 PM, Michael Pounov <mi...@aitbg.com> wrote:
> > Not see differences in results with performance from RB tree vs AVL,
Which tree size did you use to test that? Which insert order (yes, this
is relevant: with the right ordering you can hit the worst or best case
of a tree algorithm). Did you test lookup time or update time or both
(combined or split)?
> > but right solution for problems when we have choice between algorithms.
> >
>
> if you don't see any difference then what's the point in having them
> both available?
AVL trees have a difference of max 1 between the longest and shortest
path to a leaf, whereas RB-trees have at max the longest path be double
the length of the shortest path.
I.e. work case lookups require traversal of
ln(size)/ln(2) elements for AVL trees,
2 * ln(size)/ln(2) elements for RB trees.
However, RB trees are slightly more efficient with insertion/removal.
The better balancing of AVL trees can make a big difference in lookup
time compared to RB trees, for trees containing millions of items.
> how are you supposed to choose between them?
Basically it's a trade off. Is lookup more important, or insert/remove?
And ofcourse, if you still don't know, just take what strikes your
fancy. :D
But I'm mostly interested because I tend to use trees left, right and
center and those macros lead to code bloat. If I can use a tree without
macros, I'm happy.
--
Ariane
