4 ms·

For simplicity in implementation but guaranteed upper bounds I highly recommend AA-trees. WikiPedia: http://en.wikipedia.org/wiki/AA_tree http://en.wikipedia.

• shadytrees 16y ago
  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)