Build a tree from a list of paths



Hi,

I am looking for advice on an algorithm. I have one that's O(n^2), and
I'm hoping that someone here knows of or can think up a faster one.

I am storing hierarchical data in an SQL database, in a format such as
the following (I have heard it called materialied paths, materialized
trees, and enumerated paths):

+----+-------------+
| id | path |
+----+-------------+
| 1 | 1 |
| 2 | 1.2 |
| 3 | 1.3 |
| 4 | 1.3.4 |
+----+-------------+

This corresponds to the tree:

-1
\_2
|_3
\_4

In my program, I wish to be able to access the data using a tree of
objects, where each node includes an array of its children. The
challange is to build such a tree efficiently.

I have an algorithm, but I believe it is O(n^2). So if somebody could
point me to a better algorithm, I would be very much obliged. It is
preferable if the rows do not have to be sorted by path when they come
from the database.

The existing algorithm is this, where $lines is the database results
(all the rows that will end up as part of the tree) and $l is the row
to start from:

function buildTree( $lines, $l ) {
$children = array();
$lpath = preg_quote($l->path);
foreach( $lines as $key => $m ) {
if ( preg_match( "/^{$lpath}\.\d+$/", $m->path ) ) {
// $m->path begins with $l->path; this is a child.
$children[] = buildTree( &$lines, $m );
}
}
$t = new Node($l, $children);
return $t;
}


Thanks much!
--
David McCabe

.