CODEWITHSUNDEEP
javac#.netcollectionstree
Denis Yarkovoy
Denis Yarkovoy

Reputation: 1307

Comparing tree nodes

Suppose we have a simple tree of nodes:

Node 1                        0
 |-Node 1.1                   1
 |  |-Node 1.1.1              2
 |     |-Node 1.1.1.1         3
 |     |-Node 1.1.1.2         4
 |-Node 1.2                   5
    |-Node 1.2.1              6

... etc.

I need to be able to compare any 2 nodes by their flat position in the tree. The easiest way is to walk the tree and assign each node an index (as shown above in the rightmost column), then compare the indices. However, there are 2 disadvantages:

  1. For large trees, calculation of indices may be time consuming and impractical in case we need to compare only 2 nodes of the tree that contains millions of nodes.
  2. Once the tree is modified (nodes inserted/removed), indices need to be re-calculated.

Hence, my question: is there a better approach that would allow me to compare tree nodes by their position without the need to compute indices for each node?

Upvotes: 0

Views: 909

Answers (1)

Thomas
Thomas

Reputation: 88707

One approach might be to use a "materialized path" and compare those paths (i.e. the path might be "1.1.1.2" etc.). Depending on whether you know how many nodes per level you'd expect you could use fixed size part parts, e.g. "001.001.001.002" and then a simple string compare should do the trick.

That way when inserting/deleting a node you'd only have to update the materialized paths for the new node and the affected subtree. When changing node order you'd do the same for all nodes/subtrees whose order has been changed.

Another approach would be to use "nested sets", have a look here for a short tutorial on both: https://communities.bmc.com/docs/DOC-9902

Basically your problem seems to be related to how to map a tree to a database table, i.e. convert a tree structure into a flat list and back.

Upvotes: 1

Related Questions