Do you agree that binary trees and algorithms that keep trees reasonably balanced are important?

Our answer is yes!

It's interesting enough, however, that you won't easily find these algorithms publicly available.

Though red-black, AVL and other algorithms described in the wikipedia are defined in terms of tree manipulation, all implementations we have seen, deal with trees annotated with keys and values. These implementations really use tree balancing algorithms behind the schene, and expose a commonplace set or map containers to a client. Even C++ Standard Library suffers from this disease.

We think that binary trees are valuable independent concepts, and they worth to be implemented separately, at least because there are other algorithms, except sets and maps, using trees.

And well, we did it in C#! See RedBlackTree.cs.

Consider an example - a simple scheduler, ScheduleBookmark.cs, with operations:

• schedule an action;
• remove an action from the schedule;
• enumerate actions;
• find a date, an action is scheduled for;
• find an action (or at least closest one) for a specified date;
• postpone actions due to delays;

A balanced binary tree allows efficient implementation of such a scheduler. Tree node stores an action, and a time span between parent node and this node. This way:

Operation	Steps
schedule an action	find place + link node + rebalance tree
remove an action from the schedule	unlink node + rebalance tree
enumerate actions	navigate tree
find a date, an action is scheduled for	find node in tree
find an action for a specified date	cumulate time spans up to the tree root
postpone actions due to delays	fixup time spans from a node up to the tree root

Compare operation complexities between tree, array, list and map:

Operation	Tree	Array	List	Map
schedule an action	O(ln(N))	O(N)	O(N)	O(ln(N))
remove an action from the schedule	O(ln(N))	O(N)	O(1)	O(ln(N))
enumerate actions	O(ln(N))	O(1)	O(1)	O(ln(N))
find a date, an action is scheduled for	O(ln(N))	O(1)	O(1)	O(1)
find an action for a specified date	O(ln(N))	O(ln(N))	O(N)	O(ln(N))
postpone actions due to delays	O(ln(N))	O(N)	O(N)	O(N*ln(N))

Complexity of each operation for the tree is O(ln(N)). No arrays, lists, or maps achieve similar worst case guaranty.

Finally, the test program is Program.cs, and a whole project (VS2008) is Tree.zip