β

Red Black Tree in C#

C++博客-首页原创精华区 32 阅读
Several weeks ago, I tried hard to search an implement of balance binary tree in C#,  what i needed was something like std::set<key, comparator> in C++: the data should be sorted, can be inserted and deleted at low cost and provides iterator which can move forward and backward. It looks like this can be easily achieved by List<T> with List<T>.Sort and List<T>.BinarySearch, the problem is that the performance of List<T> is not acceptable when the data collection size is big in my case.

I failed to find anything that can be used directly, it is hard to believe, a lot of implement of red-black tree in Java or C++ can be easily got from internet (although none of them meets my requirement), but none in C#.

So I had to implement one, it was translated from a C++ implement and modified to provide an immutable node.

Source code
http://www.cppblog.com/Files/aqazero/RBTree.zip
Use at your own risk!
Example:
1         RBTree<int> rbt = new RBTree<int>(Comparer<int>.Default);
2         rbt.Add(3);
3         rbt.Add(1);
4         rbt.Add(10);
5         rbt.Add(6);
6         rbt.Add(7);
7         rbt.Remove(10);
8         RBNode<int> node6 = rbt.GetNode(6);
9         rbt.Remove(node6);
10
11         RBNode<int> node = rbt.GetNode(3);
12         node = node.Prev;
13         while (null != node)
14         {
15             System.Diagnostics.Trace.WriteLine(node.Value);
16             node = node.Next;
17         }

Output:
1
3
7


brent 2017-04-29 05:02 发表评论
作者:C++博客-首页原创精华区
专注于C++技术
原文地址:Red Black Tree in C#, 感谢原作者分享。

发表评论