[techtalk] DESIGN: N-ary trees

James A. Sutherland jas88 at cam.ac.uk
Thu Mar 22 19:29:18 EST 2001


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

> Laurel Fan wrote:
>
> > Excerpts from linuxchix: 21-Mar-101 [techtalk] DESIGN: N-ary
> > treesjenn at simegen.com (687*) by
> >
> >> Has anyone come up with a useful design of an N-ary tree (I'm
> >> thinking of a 4-ary tree) where you can lift a whole branch of
> >> the tree and move it elsewhere?
> >
> >
> > What do you mean by move it elsewhere?  Are you specifically thinking
> > of something quadtrees can't do? :)
>
> I suspect so.
>
> Dancer wants to lift a whole branch of an N-ary tree and move it
> elsewhere in the tree. (basically, to move the data from one
> section to another, without deconstructing the current branch
> and making a new one - just move the pointer that points to
> the branch.)
>
> *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...


James.





More information about the Techtalk mailing list