binary treaps

binary treaps

[Kevin Bealer]

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

Re: binary treaps

[Hans Reiser]

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