Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

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

Substituting red-black trees for simple binary search trees improves data balance and can result in faster searches, particularly for large and well-ordered data.


advertisement
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.



Joydip Kanjilal has over 10 years of industry experience with C, C++, Java, C#, VB, VC++, ASP.Net, XML, Design Patterns, UML, etc. He currently works as a senior project leader in a reputable multinational company in Hyderabad, India, and has contributed articles on .NET and related technologies to www.aspalliance.com.
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap