A Red-Black Tree is a self-balancing binary search tree where each node has a color — either red or black. These colors enforce rules that keep the tree roughly balanced, ensuring that the longest path from root to a leaf is no more than twice the shortest path. This guarantees reliable O(log n) worst-case performance for lookups, insertions, and deletions.
When a node is inserted or deleted, the tree may temporarily violate its color rules. To restore balance, the tree uses a combination of recoloring and rotations. It maintains balance through four key properties: the root is always black, all leaves (null nodes) are black, red nodes cannot have red children, and every path from a node to its descendant leaves contains the same number of black nodes.
When a new node is inserted into a red-black tree, it is colored red to avoid altering the black-height of existing paths. However, if its parent is also red, the red-property is violated (two consecutive red nodes). The tree repairs this violation using recoloring and rotations by inspecting the color of the node's uncle (the parent's sibling).
If the uncle is red, a simple recoloring pushes the violation up the tree without rotations. If the uncle is black, at most 2 rotations resolve the conflict. Deletion follows similar principles: if a black node is removed, a black-height deficit is resolved using recoloring and at most 3 rotations.
(5 credits)
See what happens with your input
Get a short, step-by-step explanation of this visualization. Turn on AI Summary, then start a fresh run with your input.
Metric / Operation | Complexity | Description |
|---|---|---|
| Search | O(log n) | Guaranteed maximum height of 2 log₂ (n + 1) provides predictable logarithmic lookups. |
| Insertion | O(log n) | Standard BST insertion followed by recoloring and at most 2 tree rotations. |
| Deletion | O(log n) | Removes the node followed by black-height rebalancing with at most 3 rotations. |
| Space Complexity | O(n) | Requires one color bit per node in addition to standard BST pointers. |
AVL trees maintain strict height balance, which requires frequent rotations during mutations — up to O(log n) rotations for a single deletion. Red-Black trees tolerate slightly more imbalance (height up to 2 log n) but guarantee at most 3 rotations on deletion. For general-purpose workloads with mixed reads and writes, the lower rebalancing cost of Red-Black trees provides superior overall throughput.
A red leaf can be removed without changing the black-height on any path. Removing a black node creates a double-black situation; a red replacement is recolored black, otherwise a double-black is resolved via recoloring and rotations. It is the color of the physically removed successor that determines whether fixup is needed.
to join the discussion
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0