I test this implementation with 10000000 entry inserted by random() ;) average seek time with random search of 10000 is from 2 to 3 seconds
On Fri, 20 May 2011 04:04:07 +0200 Ariane van der Steldt <ari...@stack.nl> wrote: > 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 > -- M.Punov --------------------- AITNET - Sofia/Bulgaria - Software & Network Solutions (+359) 888 73 73 58;(+359) 2 402 4000
