On 24 Mar 2002 15:00:38 -0500, Warp wrote:
> Ron Parker <ron### [at] povrayorg> wrote:
>> A binary tree can always be put in a 1-d array.  It's simple: Given a
>> cell with index n, the left child of that cell is at index n*2 and
>> the right child of that cell is at index n*2+1.  The parent of that
>> cell is, obviously, at index int(n/2).  A few macros to implement that
>> scheme and there you go.
> 
>   Yes, but would it be as fast as a regular binary tree (ie one where
> items are allocated dynamically and which contains pointers to children)?
> For example adding a new item or removing an item can be slow.

It wouldn't be any slower than a regular binary tree, but it would have a
limit on the maximum depth, it would take up more storage than absolutely
necessary, and it couldn't be balanced.  Subject to those contraints, though,
it wouldn't need to move any data around to insert or delete a node.  

Unfortunately, the combination of "can't be balanced" and "maximum depth" 
leads to it being only theoretically useful, since it's very sensitive to 
the order you add elements.

-- 
#local R=rgb 99;#local P=R-R;#local F=pigment{gradient x}box{0,1pigment{gradient
y pigment_map{[.5F pigment_map{[.3R][.3F color_map{[.15red 99][.15P]}rotate z*45
translate x]}]#local H=pigment{gradient y color_map{[.5P][.5R]}scale 1/3}[.5F
pigment_map{[.3R][.3H][.7H][.7R]}]}}}camera{location.5-3*z}//only my opinions

Post a reply to this message