Re: binary treaps

[Hans Reiser <reiser@namesys.com>]

Kevin Bealer wrote:

>On the namesys homepage, there is a statement that
>skip lists
>would be very good for directory contents but the node
>size
>varies.
>
>I wrote a balanced tree algorithm that works about
>like a skip
>list but does not have variable node size.  I started
>with the 'skip
>list' algorithm and developed a tree algorithm based
>on it.
>
>After developing this, I found an algorithm which is
>similar, called a 'treap', although they use an
>insert-then-rotate, and
>my version does the insert in one downward pass.
>
>I don't know enough about reiserfs's internals but I
>can send the
>tree algorithm description and code if anyone wants to
>see it.
>
>Kevin Bealer
>
>
>
>__________________________________
>Do you Yahoo!?
>The New Yahoo! Search - Faster. Easier. Bingo.
>http://search.yahoo.com
>
>
>  
>
Josh (jmacd) said that he did that also, but perhaps I did not listen 
carefully enough because I did not understand how it could be done.  If 
you randomly choose whether to insert into a given node or its children, 
how do you avoid randomly exceeding a fixed node size without 
balancing?   I must be misunderstanding one of the premises of the 
algorithm, or some such.

Yes, I would be interested in reading the algorithm description.

-- 
Hans