[techtalk] DESIGN: N-ary trees

jenn at simegen.com jenn at simegen.com
Fri Mar 23 13:49:02 EST 2001

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

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/

More information about the Techtalk mailing list