## 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

## Sources