I am working on a program with a tree in it and because I will be
regularly be retrieving entire branches I was going to use the preorder
traversal representation for storage rather than the adjacency matrix so
as to cut down on queries.
I am guessing this is the representation referenced in the documentation
when someone said they could load a tree with a single query and I was
just wondering if anyone could speak to the appropriateness of torque. I
don't want to spend the time learning it if it is not going to be useful.
If anyone is unfamiliar with a preorder traversal you just walk around the
tree tracking counting when you first and last pass a node, like: (I
explained it in e-mail a couple months ago, so I have some nice ascii)
(1) W [10] (#) - Number placed Node ID | Entry # | Exit #
v / \ ^ entering a node ==========================
v / \ ^ [#] - Number placed W | 1 | 10
v />>>>>\ ^ leaving a node --------+---------+-------
v / ^ v \ ^ > - Movement right X | 2 | 7
(2) X [7] v \ ^ v - Movement down --------+---------+-------
v | ^ (8) R [9] ^ - Movement up Y | 3 | 6
(3) Y [6] >>>>>>^ --------+---------+-------
v | ^ Z | 4 | 5
(4) Z [5] --------+---------+-------
>>>>>>^ R | 8 | 9
--------+---------+-------
As opposed to the more traditional adjacency matrix which would look
like:
Node Id | Node Contents Parent | Child W
======================= ============== / \
W | ... W | X / \
--------+-------------- -------+------ X R
X | ... W | R |
--------+-------------- -------+------ Y
Y | ... X | Y |
--------+-------------- -------+------ Z
Z | ... Y | Z
--------+-------------- -------+------
The advantage is you can get all the nodes in a branch with a single query
(entry_id > node.entry_id and exit_id < node.exit_id) and reconstruct it
pretty painlessly (if exit_id - entry_id = 1 then is a leaf). Also, you
can get the path back to the root with a single query which is handy
sometimes.
The downside is that adding or moving a node requires changing the id's of
all the nodes to the right. How to do that sort of operation is what I am
uncertain about in torque. Also, the querries to get branches and stuff
are not normal sort of mapping. Anyone have any useful info?
Will
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
