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

.

Relevant Pages

  • LOS Optimization Using Binary Tree Structures (with demo)
    ... fast way to calculate LOS using a binary tree (properly called a binary ... describe the visibility-dependency between tiles - as in describing ... Using octants ... The cool thing about using a relational-based LOS algorithm is that you ...
    (rec.games.roguelike.development)
  • Re: How come Ada isnt more popular?
    ... beneficial for the memory-management aspect of such an algorithm. ... When the GC hits it just traverses the tree ... E.g a chess playing program (any ... Furthermore generational garbage collection AFAIK has ...
    (comp.lang.ada)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... If your target, on the other hand, is continuous, the algorithm will build regression trees that have regression formulae in nodes and leaves. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... if my target is discrete, the algorithm will ... build a classification tree. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Comparing 2 Infinite Trees
    ... An infinite tree is described by including "self references" in place ... self reference makes the tree infinite. ... believe that I have an algorithm that can show equality in m * n time. ...
    (sci.math)