Working with Red-Black Trees in C# : Page 3

Working with Red-Black Trees
Here's an example showing how you can use the RedBlackTree class. The main() method shown below creates a new RedBlackTree instance and populates it with 1,000,000 nodes containing random integer values between 1 and 1,000,000. Finally, it inserts a node with the value 1,000,001 (forcing that node to appear at the end of the tree), and then searches for it, printing the elapsed time.

   public static void Main(String[] args)
   {
      RedBlackTree redBlackTree = new RedBlackTree();
      Random random = new Random();            
      for (int i = 0; i < 1000000; i++)
      {
         redBlackTree.Insert(random.Next(1, 1000000));
         random.Next();
      }
      redBlackTree.Insert(1000001);
      DateTime startTime = DateTime.Now;
      int p = (int)redBlackTree.Search(1000001);
      DateTime endTime = DateTime.Now;
      TimeSpan TimeElapsed = 
         (TimeSpan)(endTime - startTime);
      Console.WriteLine("The number " + p + " has been found in " + 
         TimeElapsed.Milliseconds.ToString()+" milliseconds.");
      Console.Read();
      Console.Read();
   }
   

When I run the preceding application on my system, the search requires just three milliseconds. Your system's timing may vary. To explore how much faster searching a red-black tree is compared to searching a binary search tree, I built both tree types in a similar manner, populated them with identical node values, and ran a comparison test. Here's the test code:

   public static void Main(String[] args)
   {
      RedBlackTree redBlackTree = new RedBlackTree();
   
      BinaryTree.BinarySearchTree binarySearchTree = new 
         BinaryTree.BinarySearchTree();
               
               
      for (int i = 0; i < 900000; i++)
      {
         redBlackTree.Insert(i);
      }
   
      for (int p = 0; p < 900000; p++)
      {
         binarySearchTree.Insert(p, p.ToString());
      }
   
      DateTime startTime = DateTime.Now;
      redBlackTree.Search(99449);
      DateTime endTime = DateTime.Now;
      TimeSpan TimeElapsed = (TimeSpan)(endTime - startTime);
      Console.WriteLine("Red-Black Tree Search Time: " + 
         TimeElapsed.Milliseconds.ToString() + " milliseconds."); 
   
       startTime = DateTime.Now;
       binarySearchTree.Search(binarySearchTree.Root, "99449");
       endTime = DateTime.Now;
       TimeElapsed = (TimeSpan)(endTime - startTime);
       Console.WriteLine("Binary Tree Search Time: " + 
          TimeElapsed.Milliseconds.ToString()+" milliseconds.");
       Console.Read();
   }
   

On my system the search using the red-black tree took scarcely any time compared to the same search using a binary search tree. The large difference is because, as discussed earlier, BST performance degrades quickly when you populate the tree with ordered or near-ordered values. In contrast, the red-black tree maintains branch balance even for ordered data, which is the root cause of the difference in search performance.

At this point, you've seen how red-black trees provide more efficient binary search operations for some types of data by maintaining more balance among the branches of the search tree than is usually possible with a typical binary search tree implementation. While adding nodes to red-black trees does take a little longer, that time is usually more than offset by improved search performance as the data volume in the tree grows. If you want more information on building red-black trees and other data structures in C#, I suggest you read this MSDN article.

Previous Page