Red-Black Trees

Data Structure and Algorithms


A Red-Black Tree is a self-balancing binary search tree that maintains balance during insertion and deletion operations.

Red-Black Tree Properties:

  1. The root is black.
  2. Every leaf (Leaf is a NULL child of a node) is black in Red-Black tree.
  3. The children of a red node are black. Hence possible parent of red node is a black node.
  4. All the leaves have the same black depth.
  5. Every simple path from root to descendant leaf node contains same number of black nodes.

Visual Representation:

Red-Black Tree Visualization

Other Reading:

For more information about Red-Black Trees, please visit GeeksforGeeks' Red-Black Tree tutorial page.