Trees

• Download source code - 12.3 KB

Introduction

When version 2.0 of .NET was released, there was a lot of fuss about the fact that it had Generics included with it, along with some other stuff, and to be honest, this was mostly greeted with a shrug and a so what on my part. Largely, this is due to being a professional Windows programmer in the nineties when MFC was all the rage and people mostly forgot everything they ever knew about templates because they weren't supported by the Microsoft compilers.

Then .NET came out and I started doing a lot of C# programming, and it didn't have templates in it either, and to be honest, I never really missed them in either C# or in the MFC days as most of the business logic I was required to write didn't really need them anyway. Sure if they had been available I might have used them in some projects, if only so I could put them on my C.V. and make out I was the true expert in everything under the sun that seem to be the requirement to get a job these days.

These days however, some ideas for future projects could benefit from a template or a generic implementation. Not that these projects couldn't be done using the C# object model; the implementations would, coming from a templates background, be more logically cleaner if developed generically. So I figured that I'd better poke these Generics just to see what they can do and if in the implementation they match up to what I wanted out of them. Also, I wanted to see how they compare in a head to head with the object model, so as some future projects are going to be relying on a data structure that is similar to the tree data structure, I thought the ideal starting place would be to implement a simple tree using the object model and then convert it to the generic model to see what the gains if any where.

Tree Basics

A tree is a data structure that stores the data in nodes that branch out depending on the value contained within the data held in the node.

So if we assume that each of the blue circles is a node and the numbers in them represent the data, we can see that the node that we are starting with contains the lower value 5 and the node to the left of our starting node contains the value 4, while the node to the right contains the higher value 6, and this is how trees work. The node on the left of the node we are currently at will contain a smaller value than the current node, and the node on the right will contain a higher value. Of course, if you want to get more involved with tree data structures, you can start getting into balancing and organising the tree so that the left and right sides from the root nodes are equal, which makes searching quicker, but for our purposes, left lower, right higher will do.

The implementation we are going to be using is a C# translation of the BasicTree code in Namir Clement Shammas' book Advanced C++ Progrogramming, published in 1992. This, as the name suggests, is about the most basic implementation of a tree you can get, and there are much more complex trees available on this site, both using the object and the Generics models of implementation.

The Object Model Implementation

To start with, we define the data that we are going to use:

public class SimpleTreeData : IComparer
{
   private string strData;

   public string Data
   {

   public SimpleTreeData( string data )
   {
     Data = data;
   }

   public int Compare( object simpleTreeDataOne, object simpleTreeDataTwo )
   {
      if( ( SimpleTreeData )simpleTreeDataOne < 
          ( SimpleTreeData )simpleTreeDataTwo )
            return -1;

      if( ( SimpleTreeData )simpleTreeDataOne > 
          ( SimpleTreeData )simpleTreeDataTwo )
            return 1;

      return 0; // equal
   }

   public static bool operator ==( SimpleTreeData simpleTreeDataOne, 
                                   SimpleTreeData simpleTreeDataTwo )
   {

   public static bool operator !=( SimpleTreeData simpleTreeDataOne, 
                                   SimpleTreeData simpleTreeDataTwo )
   {

   public static bool operator >( SimpleTreeData simpleTreeDataOne, 
                                  SimpleTreeData simpleTreeDataTwo )
   {

   public static bool operator >=( SimpleTreeData simpleTreeDataOne, 
                                   SimpleTreeData simpleTreeDataTwo )
   {

   public static bool operator <( SimpleTreeData simpleTreeDataOne, 
                                     SimpleTreeData simpleTreeDataTwo )
   {

   public static bool operator <=( SimpleTreeData simpleTreeDataOne, 
                                      SimpleTreeData simpleTreeDataTwo )
   {

   public override int GetHashCode()
   {

   public override bool Equals(object obj)
   {
}

We start the SimpleTreeData class by declaring it as implementing the IComparer interface. This means that we have to implement the Compare function which compares two objects returning 1 if the first object to be compared is greater than the second object, 0 if both objects are equal, and -1 if the second object is greater than the first. Although the only data in the class is a string and we could implement this a lot more easily by just using the string compare function in the SimpleTreeData class Compare function, both the object model and the generic versions are implemented as if they are a much more complex class and therefore have a full compliment of overloaded operators.

Nodes

The way a tree tracks and stores its data, so as I said before, if we consider each blue circle in the picture above as a node, then this is the declaration for the node class:

public class SimpleTreeNode
{
   private SimpleTreeNode parentNode;
   private SimpleTreeNode leftNode;
   private SimpleTreeNode rightNode;
   private object data;

If we look again at the picture above and imagine that we are looking from the first node that contains the number 5, then the data for the number five would be held in the private object data, leftNode would point to the node containing the value 4, and rightNode would point to the node containing the value 6. For this node, the parentNode would be null, but for both the nodes containing the values 4 and 6, the parentNode would point to the node containing the value 5.

The SimpleTree Class

The main characteristics of the SimpleTree class are:

public class SimpleTree
{
  /// <summary>
  /// The Starting node for the tree
  /// </summary>
  private SimpleTreeNode stnRootNode;

  /// <summary>
  /// The current Node For the Tree
  /// </summary>
  private SimpleTreeNode stnCurrentNode;

  /// <summary>
  /// The number of nodes the tree currently holds
  /// </summary>
  private int nNumberOfNodes;

  ...

  public SimpleTree()
  {

  public SimpleTree( SimpleTreeNode rootNode ) : this()
  {

  public bool Insert( IComparer data )
  {

  public SimpleTreeNode SearchBinaryTree( IComparer data )
  {

  public SimpleTreeNode SearchBinaryTree( IComparer data, int occurance )
  {

  public bool Remove( IComparer data )
  {

  public bool Remove( IComparer data, int occurance )
  {

  public SimpleTreeNode GetSuccessor( SimpleTreeNode node )
  {

  public SimpleTreeNode GetPredecessor( SimpleTreeNode node )
  {

  public void ClearNode( SimpleTreeNode root )
  {

  public SimpleTreeNode GetLowestNode()
  {

Here we have the SimpleTree class stripped to all that is important. We have a root node that is the start of the tree, or the node that would hold the five in the picture above, and the current node which is used when moving around the tree, and a number of nodes counter. In terms of functionality, we have the compulsory Insert and Remove functions, along with searching for a specific node, and the GetSuccessor and GetPredecessor functions for moving through the tree, and finally, the GetLowestNode function which is what you would do if you were going to use an enumerator to move through the list. Basically, it calls GetPredecessor until it gets to the lowest node of the tree, and then you call GetSuccessor to move through the nodes in the tree.

Comparisons

For our purposes, the IComparer interface is important in that we will be using the IComparer<T> interface when we get to the Generic implementation of the class. The IComparer interface defines only one function and that is the Compare function that we must implement. In the object model code, it looks like this:

public int Compare( object simpleTreeDataOne, object simpleTreeDataTwo )
{
  if( ( SimpleTreeData )simpleTreeDataOne < ( SimpleTreeData )simpleTreeDataTwo )
     return -1;

  if( ( SimpleTreeData )simpleTreeDataOne > ( SimpleTreeData )simpleTreeDataTwo )
     return 1;

  return 0; // equal
}

As you can see from the above code, the object model requires us to declare the items passed in as objects, even though as we know our class automatically inherits the Object class. Trying to put a proper class declaration here will result in a compiler error. This is because the interface definition for the Compare function explicitly declares that the parameters are to be objects, which means that in the test code, you could quite easily pass in a SimpleGenericTreeData class object to this function and there would be no compiler error as that also inherits from the class Object. Of course, as soon as we try to compile the code, the compiler would notify us that the SimpleGenericTreeData class could not be cast to a SimpleTreeData class.

As stated above, this function returns 1 if the first item is greater than the second, and -1 if the second item is greater than the first. This is purely arbitrary on my part as the function definition requires that the value returned if the first item is greater should be greater than 0, and less than 0 if the second item is greater.

Inserting a Node

The Insert function for the object model is:

public bool Insert( IComparer data )
{
  SimpleTreeNode stnNewData = new SimpleTreeNode( data );
  stnCurrentNode = stnRootNode;
  SimpleTreeNode stnTempData = null;

  NumberOfNodes++;

  // find the location for the insertion

  while( stnCurrentNode != null )
  {
    stnTempData = stnCurrentNode;
    if( ( ( IComparer )stnNewData.Data ).Compare( 
              stnNewData.Data, stnTempData.Data ) <= 0 )
      stnCurrentNode = stnCurrentNode.LeftNode;
    else
      stnCurrentNode = stnCurrentNode.RightNode;
  }

  stnNewData.ParentNode = stnTempData;

  if( stnTempData == null )
  {
    stnRootNode = stnNewData;
  }
  else
  {
     if( ( ( IComparer )stnNewData.Data ).Compare( 
              stnNewData.Data, stnTempData.Data ) <= 0 )
      stnTempData.LeftNode = stnNewData;
    else
      stnTempData.RightNode = stnNewData;

    return true;
  }

  return false;
}

To insert a node into the tree, we call the Insert function with a data object that inherits from IComparer. We then insert this data into a new node and then try to find where to put it. We do this by working through the tree from the root node, and if the data is greater than or equal to the data stored in the current node, we move to the left. If it is greater than the data in the current node, then we move to the right. Note straight away that a class that inherits from the SimpleTreeData class would have no problems here.

As we move through the tree, we maintain track of the current node with the stnTempData node which, once we have found a place for the node, is set to the new parent node. If we have gone nowhere at all and the stnTempData node is equal to null, then we set the new node to be the root node.

If we already have nodes in the tree, then we decide if we need to place it to the left or to the right of the current node.

Removing a Node

The Remove function for the object model is:

public bool Remove( IComparer data, int occurance )
{
  stnCurrentNode = stnRootNode;
  SimpleTreeNode stnTempNodeOne = null;
  SimpleTreeNode stnTempNodeTwo = null;

  if( occurance == 0 )
    occurance = 1;

  if( occurance > NumberOfNodes )
    return false;

  stnCurrentNode = SearchBinaryTree( data, occurance );

  if( stnCurrentNode != null )
  {
    if( stnCurrentNode.LeftNode == null || stnCurrentNode.RightNode == null )
      stnTempNodeOne = stnCurrentNode;
    else
      stnTempNodeOne = GetSuccessor( stnCurrentNode );
                                
    if( stnTempNodeOne.LeftNode != null )
      stnTempNodeTwo = stnTempNodeOne.LeftNode;
    else
      stnTempNodeTwo = stnTempNodeOne.RightNode;

    if( stnTempNodeTwo != null )
    {
      if( stnTempNodeTwo.ParentNode != null )
        stnTempNodeTwo.ParentNode = stnTempNodeOne.ParentNode;
    }

    if( stnTempNodeOne.ParentNode == null )
    {
      stnRootNode = stnTempNodeTwo;
      NumberOfNodes--;
    }
    else
    {
       if( stnTempNodeOne.ParentNode.LeftNode != null )
       {
         if( ( ( IComparer )stnTempNodeOne.Data ).Compare( stnTempNodeOne.Data, 
                 stnTempNodeOne.ParentNode.LeftNode.Data ) == 0 )
            stnTempNodeOne.ParentNode.LeftNode = stnTempNodeTwo;
         else
            stnTempNodeOne.ParentNode.RightNode = stnTempNodeTwo;
       }
       else
       {
         stnTempNodeOne.ParentNode.RightNode = stnTempNodeTwo;
       }

       NumberOfNodes--;
    }

    if( stnTempNodeOne != stnCurrentNode )
      stnCurrentNode.Data = stnTempNodeOne.Data;

    return true;
  }

  return false;
}

As with the Insert function, we pass in a class object that inherits from the IComparer interface and we pass in an integer to specify which occurrence of the data we are deleting. If 0 or no second parameter is included in the function call, then we set the value for the occurrence to one after setting up some temporary variables.

We find out where the data is in the tree by calling SearchBinaryTree which is dealt with next. And then if we manage to find the data in question, we test to see if there are any nodes branching off the current node. If there aren't, we set the first temporary node to the next node in the tree with a call to GetSuccessor.

Next, we set the value of the second temporary node to either the left or the right of the first temporary node.

Then if the second temporary node, which is the node after the node we wish to remove - the first temporary node, is valid and it has a valid parent, we shift the parent to be the parent of the first temporary node which is the node we are about to remove.

Finally, we test the parent node of the first temporary node, and if it is null, then the node to be removed is the root node, so we simply replace the current root node with the second temporary node. If it is not equal to null, we set the secondary temporary node to either the left or the right of the parent node of the node which we wish to remove, therefore replacing the node to be removed.

All we have to do then is copy the data and the function exits.

Searching for a Node

The search function really isn't all that complicated.

public SimpleTreeNode SearchBinaryTree( IComparer data, int occurance )
{
  int nCount = 0;
  stnCurrentNode = stnRootNode;

  if( occurance == 0 )
    occurance = 1;

  if( occurance > NumberOfNodes )
    return null;

  while( stnCurrentNode != null && nCount < occurance )
  {
    if( ( ( IComparer )data ).Compare( data, stnCurrentNode.Data ) > 0 )
    {
       stnCurrentNode = stnCurrentNode.RightNode;
    }
    else if( ( ( IComparer )data ).Compare( data, stnCurrentNode.Data ) < 0 )
    {
       stnCurrentNode = stnCurrentNode.LeftNode;
    }
    else // match found
    {
       nCount++;

       if( nCount < occurance )
         stnCurrentNode = stnCurrentNode.LeftNode;
    }
  }

  if( stnCurrentNode != null )
    return stnCurrentNode;

  return null;
}

Once you get past the setup variables and the checking for the number of occurrences, then it is a simple while loop that compares the data in the tree and moves to the left or the right of the current node depending on the result, until the matching node is found.

The GetSuccessor and GetPredecessor are straightforward, simply getting the getting the next higher or lower node from the current node without using any comparison of the data in the node.

The Generic Implementation

As with the object model, we declare our data:

public class SimpleGenericTreeData : IComparer< SimpleGenericTreeData >
{
  private string strData;

  public string Data
  {

  public SimpleGenericTreeData()
  {

  public SimpleGenericTreeData( string data )
  {

  public int Compare( SimpleGenericTreeData dataOne, SimpleGenericTreeData dataTwo )
  {
    if( dataOne < dataTwo )
      return -1;

    if( dataOne > dataTwo )
      return 1;

    return 0; /// equal
  }

  public static bool operator ==( SimpleGenericTreeData simpleTreeDataOne, 
                SimpleGenericTreeData simpleTreeDataTwo )
  {

  public static bool operator !=( SimpleGenericTreeData simpleTreeDataOne, 
                SimpleGenericTreeData simpleTreeDataTwo )
  {

  public static bool operator >( SimpleGenericTreeData simpleTreeDataOne, 
                SimpleGenericTreeData simpleTreeDataTwo )
  {

  public static bool operator >=( SimpleGenericTreeData simpleTreeDataOne, 
                SimpleGenericTreeData simpleTreeDataTwo )
  {

  public static bool operator <( SimpleGenericTreeData simpleTreeDataOne, 
                SimpleGenericTreeData simpleTreeDataTwo )
  {

  public static bool operator <=( SimpleGenericTreeData simpleTreeDataOne, 
                SimpleGenericTreeData simpleTreeDataTwo )
  {

  public override int GetHashCode()
  {

  public override bool Equals(object obj)
  {
}

As you can see, the generic tree data class inherits from the IComparer<T> interface which is just the generic version of the IComparer interface. The only difference being that in the declaration, the T in brackets must be the type that is being compared, which to be honest is more often than not going to be the class type that is using the interface. This means that the compiler then enforces that a compare function of the type of the class given is used. So in the example file, we have:

public class SimpleGenericTreeData : IComparer< SimpleGenericTreeData >

and with this header, we must declare a Compare function of the type:

public int Compare( SimpleGenericTreeData dataOne, SimpleGenericTreeData dataTwo )

which is quite straightforward and in keeping with the idea that a class that implements IComparer< T > must implement the class given as T. But the question is why have the T there at all. Surely it would make sense to just have it the way the object model does? Well, the answer to that is that if you want to compare more than one class in the class that implements IComparar< T >, you can. For example, declare a completely unrelated class. Note here that standard object rules apply so that in our example, any class that inherits from the SimpleGenericTreeData class will automatically be cast to its base class. Then add the unrelated class to the class declaration. E.g.:

public class SimpleGenericTreeData : IComparer< SimpleGenericTreeData >, 
             IComparer< UnrelatedGenericTest >

Of course, this means that you must declare the Compare function to handle the new data type:

public int Compare( UnrelatedGenericTest dataOne, UnrelatedGenericTest dataTwo )

With the data classes declared, their implementation is as you would expect, in that you create a new SimpleTreeData object with:

new SimpleTreeData( "First Data String" )

and as the SimpleGenericTreeData class is not specified with a template parameter, it is instantiated in exactly the same way.

new SimpleGenericTreeData( "First Data String" )

Nodes

The nodes class declaration is essentially the same as SimpleTreeNodes, except for the type T parameter:

public class SimpleGenericTreeNode< T > where T : IComparer< T >
{
  private SimpleGenericTreeNode< T > parentNode;
  private SimpleGenericTreeNode< T > leftNode;
  private SimpleGenericTreeNode< T > rightNode;
  private T data;

As you can see, the class is declared as SimpleGenericTreeNode< T > where T is the type parameter for the class, which works in exactly the same way as the type parameter for the IComparer< T > class we just looked at. This means that when we declare an object of the SimpleGenericTreeNode class, we must include the type parameter as well so whereas the object model declaration for a SimpleTreeNode is:

SimpleTreeNode stnNewData = new SimpleTreeNode( data );

the SimpleGenericTreeNode class is declared as:

SimpleGenericTreeNode< T > stnNewData = new SimpleGenericTreeNode< T >( data );

At first, this looks like you can just create a SimpleGenericTreeNode with any type as we have not specified a type here, but there are two things to take into consideration. The first is that the SimpleGenericTreeNode class is declared as:

public class SimpleGenericTreeNode< T > where T : IComparer< T >

The section after the declaration of the the class reads:

where T : IComparer< T >

This is called a constraint, and what it means to the compiler is that the type T can only be a type that implements the IComparer< T > interface. The second thing to consider is the positioning of the line:

SimpleGenericTreeNode< T > stnNewData = new SimpleGenericTreeNode< T >( data );

This line of code is taken from the Insert function of the SimpleGenericTree class, and it is here that we declare the type that the class uses.

The SimpleGenericTree Class

The class is declared as:

public class SimpleGenericTree< T > where T : IComparer< T >
{
  SimpleGenericTreeNode< T > stnRootNode;
  SimpleGenericTreeNode< T > stnCurrentNode;
  private int nNumberOfNodes;

  ...

  public SimpleGenericTree()
  {

  public SimpleGenericTree( SimpleGenericTreeNode< T > rootNode ) : this()
  {

  public bool Insert( T data ) 
  {

  public SimpleGenericTreeNode< T > SearchBinaryTree( T data, int occurance )
  {

  public bool Remove( T data, int occurance )
  {

  public SimpleGenericTreeNode< T > GetSuccessor( SimpleGenericTreeNode< T > node )
  {

  public SimpleGenericTreeNode< T > GetPredecessor( SimpleGenericTreeNode< T > node )
  {

  public void ClearNode( SimpleGenericTreeNode< T > root )
  {

  public SimpleGenericTreeNode< T > GetLowestNode()
  {

The generic implementation of the tree is functionally identical to the object implementation of the SimpleTree class. The main difference being that in the class declaration, the SimpleGenericTree class has the constraint that type T must implement the IComparer< T > interface.

All the functions are declared to take an object of type T; whether it is as a straight class object T or as a SimpleGenericTreeNode< T >, they are all the same type. This means that when we declare a SimpleTree, we don't have to provide any information about the type of data that we are storing, so we can instantiate the tree as:

SimpleTree tree = new SimpleTree();

We can't do this with the SimpleGenericTree class though as we have to specify the type and it has to be a type that implements the IComparer< T > interface, so it is instantiated as:

SimpleGenericTree< SimpleGenericTreeData > tree = 
                   new SimpleGenericTree<SimpleGenericTreeData >();

Declaring the tree as using the SimpleGenericTreeData class means that for our program, any attempt to pass in a class that is not of or derived from the SimpleGenericTreeData class will result in a compiler error.

Comparisons

The comparison function for the SimpleGenericData class is:

public int Compare( SimpleGenericTreeData dataOne, SimpleGenericTreeData dataTwo )
{
  if( dataOne < dataTwo )
    return -1;

  if( dataOne > dataTwo )
    return 1;

  return 0; /// equal
}

The only difference between the object model implementation and the generic implementation is that the generic implementation declares the class types in the function declaration so we don't need to cast the passed in parameters from objects to the required types.

Inserting a Node

As we have seen, the call to insert a node is identical for both classes; the object model is:

tree.Insert( new SimpleTreeData( "First Data String" ) );

and the generic version is:

tree.Insert( new SimpleGenericTreeData( "First Data String" ) );

The only real difference within the function is the casting when calling the Compare function; with the object model reading:

if( ( ( IComparer )stnNewData.Data ).Compare( stnNewData.Data, stnTempData.Data ) <= 0 )

and the generic model reading:

if( stnNewData.Data.Compare( stnNewData.Data, stnCurrentNode.Data ) <= 0 )

Removing a Node and Searching for a Node

The differences in the code for removing/searching a node are identical to those for inserting a node, with the only difference being the casting in the calls to the Compare function.

Conclusions

OK, for those expecting anything earth shattering, there isn't anything. Putting it simple, the strengths of using Generics come from the declarations and the strong type checking that forces you to think more closely about the types you are using right at the start of programming the class. Implementation wise, they offer nothing new apart from not having to cast objects to class types.

So the answer to the question "What can I do with Generics that I can't do without them?" is not a lot really. You could, in the given example, define a single class that implements the Compare functions for all your classes by implementing multiple IComparer< T >, IComparer< L > types, but we're stretching a bit and still not implementing anything that couldn't be done with the object model.

At the end of the day, if you choose to use the object model over the generic model, it is your choice, although Generics might look good on your CV and you can't escape the fact that Generics is just a cleaner and more organised way of doing things.

History

• 12 June 2007: First release.