A Red-Black tree is a binary search tree where each node is either red or black

Here is a link to more information: Red-Black Trees: Geeks for Geeks

Here is an image:


  1. Nodes are either red (value = 0) or black(value = 1)
  2. Root and leaf/null nodes are always black
  3. If a node is red, both its children must be black
  4. The black height of all leaf/null nodes must be the same

Key Algorithms:

  1. Rotate
  2. Insert
  3. Remove