Other cool balanced trees: rank-balanced trees [1], which have O(1) amortized insertion, deletion, and rebalancing, and ravl trees [2], which do not rebalance o

Other cool balanced trees: rank-balanced trees [1], which have O(1) amortized insertion, deletion, and rebalancing, and ravl trees [2], which do not rebalance on deletion in hopes that insertions will happen soon and seem to rotate fewer times than both red-black trees and rank-balanced trees in experiments. [1]: http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf (2009) [2]: http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf (2010)