Red Black Tree

Red-Black trees are a recently popular implementation of a BalancedTree. Wikipedia has a nice article on RedBlackTrees (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, RedBlackTrees are in practice fast to update.

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

CategoryDataStructure