brent's hut

Red Black Tree in C#

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

posted on 2017-04-29 05:02 brent 阅读(396) 评论(0)  编辑 收藏 引用 所属分类: C#


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理