On Wed, 8 Feb 2006, Gustavo Rios wrote:
> 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?
>From a complexity theory point of view, you are talking nonsense,
since O(3n) equals O(n). I doubt there exists a balanced tree
algorithm that does not need some extra data per node. Of course you
can build an ordinary tree and balance it without extra data per node,
but that's gonna cost you extra time.
At least r-b trees guarantee O(log n) worst case for all operations.
The other algorithms are pretty good as well, though I cannot remember
the exact complexity characteristics.
Oh, if there is an upper bound on the number of entries, a hash table
is also good for dictionaries. But they wast space as well.
-Otto
