Solved

# hierarchical tree

Posted on 2005-04-19
Medium Priority
462 Views
Hi experts,
I have to build a hierarchical tree and am uncertain wich method is the best. I have 2 methods to choose from:

1: Flat Table Model - with a parent Id, rank and indent level

2: Modified Preorder Tree Traversal -- with a left and right number

Does anyone know what the advantages / disadvantages are of these methods?

0
Question by:HumanContent

LVL 19

Expert Comment

ID: 13814984
Personally I'd go for the first method which in my humble opinion is more clear than the other.

I would  have to say both methods have their strong points and therefor it depends on personal preference which method is 'best'.

You could get several different answers to this questions and all of them would be accurate.

Regards,
Max.
0

LVL 9

Expert Comment

ID: 13815382
I second that emotion. Here's some of my own code that seems to work pretty well:

http://www.experts-exchange.com/Web/Web_Languages/ASP/Q_21338262.html
0

LVL 8

Accepted Solution

anthonywjones66 earned 2000 total points
ID: 13816918
How many nodes you expect to be holding?
How often will nodes be create, destroyed or moved around in the structure?
Will the structure always be accessed from the root or will nodes at lower levers be accessed?

I couldn't see any advantages the the Preorder Tree has over the flat model.   So I thought I would ask what would the set of operations one would want to be able to make on a tree structure.  We would want to be able to acheive these operations without too much complexity balanced with good performance.
One of the problems with trees and DBs is that they often result in cursors or recursive code initiiating queries over and over again so we would want a structure that help us to aviod that.

Defintions.

flat model:-

ID, ParentID, Name, Indentation, Rank  (where rank is a contiguous sequence number through the whole tree)

The pre-ordered model is:-

ID, ParentID, Name, LeftID, RightID (see link in question for diagram)

These are the operations I can think of that we might need and how difficult they might be to achieve.  The list may not be exhaustive and others may better ideas.

Operations on a tree:-

1) Read the tree in sequence given a node in that tree (be that a the root node or a descendant somewhere)

Both methods have a sequential number on which a sort can be achieved.    Both can limit return sets to only children of the current node being queried

2) Limit reading to direct children only  of as specified node.

For both models this is very easy using the ParentID field.

3) Traverse siblings only, forward or backward

At times you might want to the next sibling of the node (or previous sibling) ignoring any children.  This is very similar to the above since siblings will have the same parentID and previous or following sibilings can be identifed by their sequence number.

4) Traverse from child back through ancestors to the final root.

A common operation is discovering a node's ancestors in appropriate sequence (to build a path string for example).  The flat model has trouble with this.  I don't think it can be done with resorting to a cursor (although perhaps there is a better way).  The preordered model can do this since the left hand or right hand sequence id of the original node will always be beween the left hand and right hand sequence ids of it's ancestors also RightID - LeftID  can be used as a sort value to get the ancestors in appropriate order.

5) Delete and Insert nodes.

Both models struggle with this since both have sequence numbers covering the whole range of nodes.  Hence on average half the node records will need to be updated when nodes are randomly added and removed.

6) Testing IsChildOf or IsDescendantOf/IsAncestorOf.

Due to having a ParentID testing for IsChildOf is easy for both.  For IsDescendantOf/IsAncestorOf in the flat model the rank of the next node that has the same or lower indentation level (in effect finding the equivalent to Preorder's RightID) a descendant will be between this and the current nodes rank.   For the Preorder model it is very easy since any node's sequence ids will be within any of those of it's ancestors.

7) Number of Children or Descendants.

For the both models number of children can be acheived with COUNT(*) and the parentID.  Finding number of descendants in the flat model is a little trickier using the same method above to find the effective 'RightID' and then subtracting the current nodes rank.  For the Preordered model number of descendants is simply (Right - Left -1) / 2.

It would seem then that the preordered approach has the more elegant and effecient solutions to the above set of problems.  I also note that IsDescendantOf and Number of Descendants require some special case handling when the context node is on the right-most extremity of the tree.

Anthony.
0

Author Comment

ID: 13893106
Great anthony, thanks for the answer, this was excactly what i was looking for. Think i'll go for the pre-ordered model, because of the possibility of Traverse from child back through ancestors to the final root.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

I recently decide that I needed a way to make my pages scream on the net.   While searching around how I can accomplish this I stumbled across a great article that stated "minimize the server requests." I got to thinking, hey, I use more than one…
This demonstration started out as a follow up to some recently posted questions on the subject of logging in: http://www.experts-exchange.com/Programming/Languages/Scripting/JavaScript/Q_28634665.html and http://www.experts-exchange.com/Programming/…
Are you ready to place your question in front of subject-matter experts for more timely responses? With the release of Priority Question, Premium Members, Team Accounts and Qualified Experts can now identify the emergent level of their issue, signal…
Please read the paragraph below before following the instructions in the video — there are important caveats in the paragraph that I did not mention in the video. If your PaperPort 12 or PaperPort 14 is failing to start, or crashing, or hanging, …
###### Suggested Courses
Course of the Month13 days, 18 hours left to enroll