Do you agree that binary trees and algorithms that keep trees reasonably balanced
Our answer is yes!
It's interesting enough, however, that you won't easily find these algorithms
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
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
Consider an example - a simple scheduler,
ScheduleBookmark.cs, with operations:
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.
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
and a whole project (VS2008) is
a@href@title, b, blockquote@cite, em, i, strike, strong, sub, super, u