Red-Black Trees

Overview

A Red-Black Tree is a self-balancing binary search tree where each node contains an extra bit for tracking the color of the node, either red or black. It ensures balanced trees for efficient insert, delete, and search operations.

Key Properties

• Each node is either red or black.
• The root node is always black.
• No two red nodes can be adjacent (no red parent with red child).
• Every path from a node to its descendant NULL nodes must have the same number of black nodes.

Example

For more detailed information, check out Wikipedia: Red–Black Trees .