Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!brutus.cs.uiuc.edu!psuvax1!psuvm!brl102
From: BRL102@psuvm.psu.edu (Ben Liblit)
Newsgroups: comp.ai
Subject: Re: m-way tree building
Message-ID: <90043.162734BRL102@PSUVM.BITNET>
Date: 12 Feb 90 21:27:34 GMT
References: <8053@cbnewsh.ATT.COM> <D?88P-@rpi.edu>
Organization: Penn State University
Lines: 36

Some free advice from someone who knows more about linked lists than ai.

In article <D?88P-@rpi.edu>, fargo@pawl.rpi.edu (Irwin M. Fargo) says:
>
>You can also create n-way trees in languages like C and Pascal by using
>linked lists.

This is true.  However, the implementation of this that first comes to mind is
absolutely nightmarish to work with.  One's first thought is to associate with
each node a linked list of pointers to children.  Something like this:

    A
    |------|
    B      C
    |-|-|
    D E F

When you actually sit down to program, though, this really gets hairy.  A much
nicer way of handling general trees is to have each node point to its first
chile and its next sibling.  Thus:

    A
    |
    B--------C
    |
    D--E--F

Admittedly, this doesn't resemble the original relationships as the first
technique, amd there *are* some applications for which it is not appropriate.
However, I strongly recommend that anyone out there who is thinking of
implementing an m-tree in a language like Pascal or C take the time to evaluate
this approach.  It may be the better of the two in the long run.

                      Ben Liblit
                      BRL102 @ psuvm.bitnet -- BRL102 @ psuvm.psu.edu
                      "Fais que tes reves soient plus longs que la nuit."