Re: Split Trees (my design, similar to binary treaps)

[Hans Reiser <reiser@namesys.com>]

Kevin Bealer wrote:

>As Alexander said, data can be in the node or
>elsewhere in
>either a skip list or skip tree.  Skip List nodes are
>variable
>sized; skip tree nodes are uniform, three pointers +
>data.
>(Unless the data is variable sized).
>
>Skip Lists look like:
>
>XX-----X-----X
>X--X--X--X--X--X--X--X
>
>
>--- "Alexander G. M. Smith" <agmsmith@rogers.com>
>wrote:
>  
>
>>Hans Reiser wrote on Fri, 23 May 2003 02:48:05
>>+0400:
>>    
>>
>>>Do nodes contain both pointers and data?
>>>      
>>>
>>Yes, that's a common way of doing skip lists.  Or
>>the node could contain
>>the level pointers and a data pointer.  The nodes
>>are also awkwardly
>>variable sized due to the random number of levels. 
>>That leads to
>>allocation fragmentation unless extra steps are
>>taken.
>>
>>I don't know how the split trees approach does it.
>>
>>- Alex
>>    
>>
>
>
>__________________________________
>Do you Yahoo!?
>The New Yahoo! Search - Faster. Easier. Bingo.
>http://search.yahoo.com
>
>
>  
>
So the fanout of a skip tree is 3?  (Just got back from Italy.....)

-- 
Hans