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

By submitting your information, you agree that devx.com may send you DevX offers via email, phone and text message, as well as email offers about other products and services that DevX believes may be of interest to you. DevX will process your information in accordance with the Quinstreet Privacy Policy.


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

WEBINAR:

On-Demand

Application Security Testing: An Integral Part of DevOps


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
×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.
Thanks for your registration, follow us on our social networks to keep up-to-date