Don't get me wrong, i am very confident with openbsd. Although i am very confident using the openbsd native support for my needs, all of them have some thing i dislike.
First: i would really enjoy worst case O(log2 n), none of the method i know so far make such garantee. Another problem is about memory usage: They all requires 3 pointer (left/right node and the element pointer) plus space for thing like left/right subtree weight, color, etc. I could see a paradise for the following scenario: worst case search/delete/insert in O(log2 N) and space requirement O(3N). Is that possible? Any suggestions? Thanks once more. 2006/2/8, Claudio Jeker <[EMAIL PROTECTED]>: > On Wed, Feb 08, 2006 at 06:47:15PM -0200, 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. > > > > http://en.wikipedia.org/wiki/Red-black_tree is a good starting point. > RB trees have a equal properties to AVL trees and are available in > tree(3). > > -- > :wq Claudio
