kwong

In my previous post, I discussed how to merge and split a two level tree. Before moving on to discuss its applications, let us take a look at the output of the sample program I gave before. 

        static void Main(string[] args)
        {
            TreeNode n1 = new TreeNode("t1");
            TreeNode n2 = new TreeNode("t2");
            TreeNode n3 = new TreeNode("t3");
 
            TreeNode n4 = new TreeNode("t4");
            TreeNode n5 = new TreeNode("t5");
            TreeNode n6 = new TreeNode("t6");
 
            TreeNode t1 = n1.Add(n2).Add(n3);
            Console.WriteLine(t1);
 
            TreeNode t2 = n4.Add(n5).Add(n6);
            Console.WriteLine(t2);
 
            TreeNode t3 = t1.Add(t2);
            Console.WriteLine(t3);
 
            TreeNode t4 = t3.Remove(n4);
            Console.WriteLine(t4);
 
            TreeNode t5 = t4.Remove(n1);
            Console.WriteLine(t5);
 
            Console.ReadKey();
        }

Here is the output from the main routine:

(t1);t2;t3;
(t4);t5;t6;
(t1);t2;t3;t4;t5;t6;
(t1);t2;t3;t5;t6;
(t2);t3;t5;t6;

As you can see, tree t1 is formed by adding nodes t2 and t3 and the resulting tree is a two-level tree with t1 being the root. Similarly, t4 is formed by adding nodes t5 and t6. We then combined this two tree we just created, note how node t4 changed to a leaf in order to satisfy the two level property. In the next two output lines, we removed nodes from the two level tree. Note the last line: when we removed the root node, a leaf node (t2) is chosen as the new root of the tree.

Two level tree is extremely useful in capturing relationships in real world applications. For instance, if a is related to b and c, and d is related to e and f. Now we have two sets of distinct relationships (both are two level trees):

(a);b;c
(d);e;f

Now suppose that we also know c is related to e, what would the new relationship be? We know that a, b, c, d, e, f are then all related. But how do we capture this kind of relationships programmatically? As it turned out, we can use two level trees. In the example we just discussed, the relationship between e and c are captured via combining the two trees. And thus we get the following two level tree:

(a);b;c;d;e;f

Since related items are not necessarily limited to just tree roots (e.g. c and e are both leafs), we needed to be able to refer to a tree by either its root or its nodes and this is why in my previous post I mentioned that it would be a lot easier if we allowed referencing a tree by either the root node or its leafs.

One benefit of using a two level tree to capture relationships is that finding out the related items is a constant time operation since all of the related items are in a two level tree and no further tree traversal is required. In a large data set, this algorithm becomes very effective since no recursion is required.

Be Sociable, Share!