On Wed, 8 Feb 2006, Gustavo Rios wrote:
> 2006/2/8, Otto Moerbeek <[EMAIL PROTECTED]>:
> >
> >
> > On Wed, 8 Feb 2006, Gustavo Rios wrote:
> >
> > > i saw openbsd uses red-black trees inside. I could not figure it out a
> > > motivation for not using AVL, SPL or even something based on
> > > http://user.it.uu.se/~arnea/abs/simp.html.
> > >
> > > I could not figure what would it be the best/average/worst cost, i.e.,
> > > O(f(n)) for those method above.
> > >
> > > Thanks a lot for your time and cooperation.
> >
> > Why would red-black trees not be a good choice?
>
> I just wanted to know which would it be the best choice, and why?
> For instance, i don't know the best/average/worst case for the method
> supplied.
> I don't have a simple source of reference where i could see these
> metrics, prefereable on the internet.
I don't think you searched very good. Wikipedia has entries on all of
the well known balanced tree alghorithms.
-Otto
>
> > For dictionaries, red-black trees are considered pretty much the best
> > algorithm. See for example Sedgewick "Algorithms in C", third ed,
> > especially the conclusions in paragraph 13.6.
> >
> > -Otto
