On Fri, May 20, 2011 at 4:04 AM, Ariane van der Steldt <ari...@stack.nl> wrote: > > 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 >
i know about the difference of lookup and insert/remove speed, but is there a significant difference in practice (in openbsd use cases)? > 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. so maybe it makes sense to have a non macro implementation in libkern and use it in uvm or whenever needed? > -- > Ariane
