Ken Tilton  <ken@theoryyalgebra.com> wrote:
+---------------
| Your mission, should you blah blah blah, is to take a list of field 
| outputs (again, a list whose last element is data, the rest a path)
| and collapse them into the implied tree(s):
| 
| #+test
| (time (tree-ify '((x one a 1)(x two a 2)(x three 42)
|                   (y two b 3)(x one b 4))))
| ;; 39 cons cells
| ;; -> ((Y (TWO (B 3))) (X (THREE 42) (TWO (A 2)) (ONE (B 4) (A 1))))
+---------------

Not sure I can contribute any code more useful than the other branch
of this thread [some cute stuff in there], but one thought comes to
mind from the problem statement: If you consider each element of an
input "list of field outputs" to be a "character" [yes, I know it isn't],
then this task smells an awful lot like inserting into a "trie", and
some study of trie algorithms might prove useful.

Oh, and there was some discussion that might be related to this
back in August '02, in the thread "Q: modularity problem with CLOS".
Tim Bradshaw's "generic trees" & INTERN-SEQUENCE-IN-GT come to mind in
particular, see <news:ey3wuqn41r3.fsf@cley.com>, et seq in which Rahul
Jain says that GTs are really tries, or maybe "discrimination nets".
["Ternary search trees" were also mentioned.]

That's all I've got. Sorry it's not more...


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607