Red-Black trees are a recently popular implementation of a BalancedTree. Wikipedia has a nice article on RedBlackTree''''''s (http://en.wikipedia.org/wiki/Red-Black_tree).  It explains how each of the rotation algorithms serves to restore the tree's invariants.

Takes O(log n) time overall for lookups, insertions, and deletions, and for insertion and deletion takes only O(1) rotations.  Since rotations mean writing to memory, and writing to memory is expensive, RedBlackTree''''''s are in practice fast to update.

''If I remember correctly RedBlackTree''''''s are isomorphic to TwoThreeTree''''''s expanded into one or two nodes. -- GunnarZarncke''

----
CategoryDataStructure