What is a Red-Black Tree?

Red-Black Trees expand upon regular Binary Search Trees, and have special properties that keep the tree balanced using black and red nodes.

The Four Red-Black Tree Properties:

  1. Each node is either red or black
  2. The root node is always black
  3. Red nodes cannot have red children
  4. All paths from the root to a null child have the same number of black nodes

Picture of a Red-Black Tree:

Learn More:

Wikipedia GeeksforGeeks