Red-Black Tree


Red-Black tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black.

Key Properties:

  1. Each node is either red or black
  2. The root is black.
  3. No red nodes can have red children
  4. Every path from root to a null child has the same number of black nodes(black height of the tree)
  5. Null children are black

An example of valid Red-Black tree:

There is one link to more information about Red-Black tree:

Learn more about Red-Black Trees