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

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion