Home Products Download Order Contacts


Subject: Re: Tree traversal algorithm

>>I have a tree structure I want to traverse in in-order (left leaf, node,
>>right leaf) sequence. This is pretty easy if you have a binary tree and
>>child pointers you can follow. Unfortunately I have a tree with n childs
>>and only parent pointers.
> Wow. That must be the single most unhelpful way of storing a tree,
> ever. That almost makes bogo-sort look like a good idea in comparison

Hmm. Do you have a better suggestion? We could still fix this I guess.
The trees are stored in a standard relational database. We investigated
several different methods of storing them, but this was the best
compromise we could come up with. From an SQL point of view it would be
far nicer to store trees as nested sets, where each node has a left and
right index number indicating how many children it has.

However we couldn't figure out a way of compressing that. Compression is
very important in our case, since we store a gazillion trees in the
database, which often differ only in some of their leaf nodes or leaf
sub-trees. The parent pointer structure we have now makes it trivially
easy to share parent trees - with the cost of making queries very
hard/inefficient, hence my post.

I was all in favor of going with the set tree model and easy queries at
the expense of huge tables - but the decision was made the other way

> Forget about efficiency. That's the least of your worries here.
> That said, it's pretty straight forward: sort your N parent-child
> pairs by parent. This will give you all child nodes of each parent
> nicely arranged next to each other. Keep that sorted table, and store
> the start and length of that sequence with each node. Done.

I'll try that, thanks.




View All Messages in comp.graphics.algorithms

Tree traversal algorithm =>Re: Tree traversal algorithm =>


Copyright © 2006 WatermarkFactory.com. All Rights Reserved.