[techtalk] DESIGN: N-ary trees

[jenn at simegen.com]

James A. Sutherland wrote:

> On Wed, 21 Mar 2001 jenn at simegen.com wrote:

>> *I* couldn't figure out a way to do that within an N-ary tree (other
>> than also changing the 'where in the tree am I' stuff). I
>> was wondering if anyone else could.
> 
> 
> If you just have a load of pointers in groups of four, each either
> pointing to another block of pointers or some node items (leaves on the
> tree), you shouldn't need a "where am I?" field, surely? In which case,
> relocating becomes trivial: just change two pointers. If you need pointers
> to the parent node, it's a little bit more difficult, but not too hard...

How do you know which branch to put a new pointer on if you don't know 
where the pointer is?

I'm thinking of a tree like:

                      |
  x1<x2   y1>y2       |    x1>x2   y1>y2
                      |
----------------------------------------------
                      |
  x1<x2   y1<y2       |    x1>x2   y1<y2
                      |


And so I need to know what x2 and y2 are for any given node, so I know
where the new leaf fits in. Otherwise searching the tree will be a real
bitch.




Jenn V.
-- 
     "Do you ever wonder if there's a whole section of geek culture
             you miss out on by being a geek?" - Dancer.

jenn at simegen.com     Jenn Vesperman     http://www.simegen.com/~jenn/