Tree validation

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View

I'm getting serious headaches with the following problem:

I try to build a small HTML-based tree with the help of PHP. I started
off wirting a TreeClass and a nice TreeNodeClass, a recursive function
which builds the tree and everything seems to be fine.

Unless you feed some incorrect data, for example you add two or more
nodes to the Tree which contain a loop (The Information which tells
the TreeClass, which Node is which's parent is stored within the
nodes), like NodeB is a child of NodeA and NodeA is a child of NodeB
(endless looping).

The question is - how to validate such a tree? I played around with
crosschecking each node's Children with each other's children stored
in the tree, looking for equal children of the nodes, but it was not
that successful, as my algorithm was pretty ... ineffective ... -.-

The question is, is there a solution which lets me easily check the
tree for looping nodes, without crashing down the whole server, just
by knowing each nodes's children?



Re: Tree validation wrote:
Quoted text here. Click to load it

This should never happen.  If the parent node is not already in the
tree, reject the insert.

Quoted text here. Click to load it

Don't allow it to be bad in the first place.

Quoted text here. Click to load it

Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.

Re: Tree validation

While I am not a PHP programmer, you might want to look at the Nested
Sets model in the SQL world.  The technique of using (lft, rgt)
bracketing pairs is very general.

Re: Tree validation

On Mar 9, 2:34 pm, wrote:
Quoted text here. Click to load it

Walk the tree maintaining a list of the nodes you've visited, or put a
flag in each node. If you visit a node twice in the same context then
it's invalid.

(this is why programmer's prefer a complete structure such as a right-
threaded binary tree so it can be walked in a single pass - even
though the relational model you describe is the right one to use in a
relational DBMS)


Site Timeline