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