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?
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
