Red-Black Tree

Red-black tree

• Invented by Rudolf Bayer in 1972

• A node is either red or black

• The root and leaves (NIL) are black

• If a node is red, then its children are black

• All path from a node to its NIL descendants contains the same number of black nodes.

• Nodes require one storage bit to keep track of color

• The longest path (root do farthest NIL) is no more than twice the length of the shortest path (root to nearest NIL).

  • Shortest path: all black nodes
  • Longest path: alternating red and black

• Operations are O(log n) time complexity

  • Search
  • Insert (require rotation)
  • Remove (require rotation)

• Space complexity are O(n)

References

• INE 5408 - Estruturas de Dados - Aula 6.5. Árvores de Busca Rubro-Negras (Red-Black Trees)