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.