Red-Black Trees in Computer Science

What is a Red-Black Tree?

A red-black tree is a self-balancing binary search tree. Each node stores an extra bit representing "color" (red or black), used to ensure the tree remains approximately balanced during insertions and deletions.

The 5 Core Properties

• Every node is either red or black.
• The root node is always black.
• Every leaf (NIL) is black.
• If a node is red, then both its children are black (no two adjacent red nodes).
• Every path from a node to its descendant NIL nodes contains the same number of black nodes.

Visual Example

Learn More

For more detailed information, you can visit the Wikipedia page on Red-Black Trees.