theEclipse
Programmer
I am trying to figure out the most efficient way to accomplish this:
In a SQL database a table exists that has a list of nodes. When SELECT'd out of the table an algorithm should be able to organize the nodes into a tree-like structure with the following rules:[ul][li]The root element is null[/li][li]All elements (including null) can have infinite child nodes, including none[/li][li]No implicit order or structure is defined to account for searching, ect. other than the parent-child relationship of the tree itself[/li][/ul]
As of now my solution defines a table something like this:
Table nodes(
varchar(32) ID
varchar DATA,
varchar(32) PARENT
)
and the recursive algorithm to build the tree is something like this:
At least I think that works....something like that anyway. Near as I can tell building this structure is O
where n=the deepest nest (the degree I suppose).
In searching on google, I found some information on trees where nodes have unlimited numbers of direct children. Their solution specified a next-sibling pointer, effectively making a linked list out of the siblings.
Any ideas as to how to improve this process? The database table is changeable.
Robert Carpenter
Remember....eternity is much longer than this ~80 years we will spend roaming this earth.
ô¿ô
In a SQL database a table exists that has a list of nodes. When SELECT'd out of the table an algorithm should be able to organize the nodes into a tree-like structure with the following rules:[ul][li]The root element is null[/li][li]All elements (including null) can have infinite child nodes, including none[/li][li]No implicit order or structure is defined to account for searching, ect. other than the parent-child relationship of the tree itself[/li][/ul]
As of now my solution defines a table something like this:
Table nodes(
varchar(32) ID
varchar DATA,
varchar(32) PARENT
)
and the recursive algorithm to build the tree is something like this:
Code:
sub build_tree (nodeList, parent_id):
j := 0;
children := new List;
while counter < size nodeList:
if list[j]->parent = parent_id:
k := size children;
children[k]:=list[counter]
children[k]->children := build_tree(nodeList, children[k]->id)
endif
increment counter
endwhile
return children
endsubAt least I think that works....something like that anyway. Near as I can tell building this structure is O
where n=the deepest nest (the degree I suppose).In searching on google, I found some information on trees where nodes have unlimited numbers of direct children. Their solution specified a next-sibling pointer, effectively making a linked list out of the siblings.
Any ideas as to how to improve this process? The database table is changeable.
Robert Carpenter
Remember....eternity is much longer than this ~80 years we will spend roaming this earth.
ô¿ô