ML Wiki

Red-Black trees

In Binary Search Trees the worst case running time depends on the height of a tree. How we can make sure the tree doesn't turn into a linked list - and is kept balanced?

Idea

• the height is maintained at [math]O(\log n)[/math]
• therefore all operations are in [math]O(\log n)[/math]

Red-Black invariants

• each node is red or black
• root is black
• not 2 reds in a row
  • red node => only black children
• every path from the root to NULL-nodes passed the same amount of black nodes

Operations

All the operations expect insert and delete are performed as usual in Binary Search Trees

See also

• Binary Search Trees

Sources

• Algorithms Design and Analysis Part 1 (coursera)