Red-Black Tree Operations
Traverse
100%
Ctrl + scroll to zoom
Red-Black Tree
See red-black tree coloring and rotations keep the tree balanced on every operation.
Time O(log n) · Space O(n)
Implementation
from __future__ import annotations
from enum import Enum
class Color(Enum):
RED = 1
BLACK = 0
class RbNode:
"""A node in the Red-Black tree with color tracking."""
__slots__ = ("val", "left", "right", "parent", "color")
def __init__(self, val=None, color: Color = Color.BLACK):
self.val = val
# Self-references are placeholders; overwritten for real nodes
self.left: RbNode = self
self.right: RbNode = self
self.parent: RbNode = self
self.color: Color = color
def __str__(self):
return str(self.val)
def __repr__(self):
return str(self.val)
class RedBlackTree:
"""
Self-balancing Red-Black tree implementation.
Maintains the Red-Black invariants through color flips and rotations.
Uses a NIL sentinel node for leaves to simplify boundary conditions.
Provides operations for adding, searching, deleting nodes,
finding successors, and traversing the tree.
"""
def __init__(self):
"""Initialize an empty Red-Black tree."""
# NIL Sentinel Pattern:
# Instead of using None for empty children/parent, we use a single
# shared sentinel node. This simplifies the code because:
# - No None checks needed: all pointers are valid RbNode objects
# - Can safely access .color, .parent on any node (NIL is black)
# - Leaf semantics: RB theory treats leaves as black NIL nodes
# The sentinel has val=None and points to itself for all references.
# Real nodes must never use None as their value.
self.NIL = RbNode(val=None, color=Color.BLACK)
self.NIL.left = self.NIL.right = self.NIL.parent = self.NIL
self.root: RbNode = self.NIL # Empty tree
# -------------------------------------------------------------------------
# Basic Helpers
# -------------------------------------------------------------------------
def __contains__(self, val):
"""Allow 'val in tree' syntax."""
return self.search(val) is not None
# -------------------------------------------------------------------------
# Rotations
# -------------------------------------------------------------------------
# Rotations preserve BST ordering while rebalancing the tree.
#
# Left Rotation: Right Rotation:
# x y y x
# / \ => / \ / \ => / \
# A y x C x C A y
# / \ / \ / \ / \
# B C A B A B B C
# -------------------------------------------------------------------------
def _rotate_left(self, x: RbNode) -> None:
"""Perform left rotation on node x."""
y = x.right
# Turn y's left subtree into x's right subtree
x.right = y.left
if y.left is not self.NIL:
y.left.parent = x
# Link x's parent to y
y.parent = x.parent
if x.parent is self.NIL:
self.root = y
elif x is x.parent.left:
x.parent.left = y
else:
x.parent.right = y
# Put x on y's left
y.left = x
x.parent = y
def _rotate_right(self, y: RbNode) -> None:
"""Perform right rotation on node y."""
x = y.left
# Turn x's right subtree into y's left subtree
y.left = x.right
if x.right is not self.NIL:
x.right.parent = y
# Link y's parent to x
x.parent = y.parent
if y.parent is self.NIL:
self.root = x
elif y is y.parent.right:
y.parent.right = x
else:
y.parent.left = x
# Put y on x's right
x.right = y
y.parent = x
# -------------------------------------------------------------------------
# Insert
# -------------------------------------------------------------------------
def add(self, val) -> None:
"""Add a value to the tree. Raises KeyError if duplicate."""
# Create new red node with NIL children/parent
node = RbNode(val=val, color=Color.RED)
node.left = node.right = node.parent = self.NIL
# Standard BST insertion
y = self.NIL # Trailing pointer (will be parent)
x = self.root
while x is not self.NIL:
y = x
if val < x.val:
x = x.left
elif val > x.val:
x = x.right
else:
raise KeyError("Node with this value already in tree.")
# Insert node as child of y
node.parent = y
if y is self.NIL:
self.root = node # Tree was empty
elif node.val < y.val:
y.left = node
else:
y.right = node
# Fix Red-Black properties
self._insert_fixup(node)
def _insert_fixup(self, z: RbNode) -> None:
"""Restore Red-Black properties after insertion."""
# Loop until parent is black (no violation) or z is root
while z.parent.color == Color.RED:
if z.parent is z.parent.parent.right:
y = z.parent.parent.left # Uncle
if y.color == Color.RED:
# Case 1: Uncle is red - recolor and move up
y.color = Color.BLACK
z.parent.color = Color.BLACK
z.parent.parent.color = Color.RED
z = z.parent.parent
else:
# Uncle is black
if z is z.parent.left:
# Case 2: z is left child - rotate to make it right child
z = z.parent
self._rotate_right(z)
# Case 3: z is right child - rotate and recolor
z.parent.color = Color.BLACK
z.parent.parent.color = Color.RED
self._rotate_left(z.parent.parent)
else:
# Mirror of above (parent is left child)
y = z.parent.parent.right # Uncle
if y.color == Color.RED:
# Case 1: Uncle is red - recolor and move up
y.color = Color.BLACK
z.parent.color = Color.BLACK
z.parent.parent.color = Color.RED
z = z.parent.parent
else:
# Uncle is black
if z is z.parent.right:
# Case 2: z is right child - rotate to make it left child
z = z.parent
self._rotate_left(z)
# Case 3: z is left child - rotate and recolor
z.parent.color = Color.BLACK
z.parent.parent.color = Color.RED
self._rotate_right(z.parent.parent)
if z is self.root:
break
# Ensure root is always black
self.root.color = Color.BLACK
# -------------------------------------------------------------------------
# Search / Min / Max / Successor / Predecessor
# -------------------------------------------------------------------------
def search(self, val) -> RbNode | None:
"""Search for a value. Returns the node if found, None otherwise."""
node = self.root
while node is not self.NIL: # Stop at NIL sentinel (not None)
if val == node.val:
return node
node = node.left if val < node.val else node.right
return None # Not found - return None to external callers
def find_successor(self, node: RbNode) -> RbNode | None:
"""
Find the in-order successor of a node.
If node has right subtree: successor is leftmost in right subtree.
Otherwise: successor is first ancestor where node is in left subtree.
"""
if node.right is not self.NIL:
# Find leftmost node in right subtree
leftmost = node.right
while leftmost.left is not self.NIL:
leftmost = leftmost.left
return leftmost
# Walk up until we find an ancestor from the left
y = node.parent
while y is not self.NIL and node is y.right:
node = y
y = y.parent
return None if y is self.NIL else y
# -------------------------------------------------------------------------
# Delete
# -------------------------------------------------------------------------
def delete(self, val) -> None:
"""Delete a value from the tree. No-op if value not found."""
# Find node to delete
z = self.root
while z is not self.NIL and z.val != val:
z = z.left if val < z.val else z.right
if z is self.NIL:
return # Not found
y = z # Node to be removed or moved
y_original_color = y.color
if z.left is self.NIL:
# Case 1: No left child - replace with right
x = z.right
self._transplant(z, z.right)
elif z.right is self.NIL:
# Case 2: No right child - replace with left
x = z.left
self._transplant(z, z.left)
else:
# Case 3: Two children - replace with successor
# Find successor (minimum in right subtree)
y = z.right
while y.left is not self.NIL:
y = y.left
y_original_color = y.color
x = y.right # Successor's right child (may be NIL)
if y.parent is z:
# Successor is direct child of z
x.parent = y # Maintain parent even if x is NIL
else:
# Successor is deeper - move it up
self._transplant(y, y.right)
y.right = z.right
y.right.parent = y
# Replace z with successor y
self._transplant(z, y)
y.left = z.left
y.left.parent = y
y.color = z.color
# Fix Red-Black properties if black node was removed
if y_original_color == Color.BLACK:
self._delete_fixup(x)
def _transplant(self, u: RbNode, v: RbNode) -> None:
"""Replace subtree rooted at u with subtree rooted at v."""
if u.parent is self.NIL:
self.root = v
elif u is u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent
def _delete_fixup(self, x: RbNode) -> None:
"""Restore Red-Black properties after deletion."""
# Loop until x is red or root (extra black absorbed)
while x is not self.root and x.color == Color.BLACK:
if x is x.parent.left:
w = x.parent.right # Sibling
if w.color == Color.RED:
# Case 1: Sibling is red - rotate to make sibling black
w.color = Color.BLACK
x.parent.color = Color.RED
self._rotate_left(x.parent)
w = x.parent.right # New sibling
if w.left.color == Color.BLACK and w.right.color == Color.BLACK:
# Case 2: Sibling and both nephews are black - recolor
w.color = Color.RED
x = x.parent # Move extra black up
else:
if w.right.color == Color.BLACK:
# Case 3: Sibling's right child is black - rotate sibling
w.left.color = Color.BLACK
w.color = Color.RED
self._rotate_right(w)
w = x.parent.right
# Case 4: Sibling's right child is red - rotate parent
w.color = x.parent.color
x.parent.color = Color.BLACK
w.right.color = Color.BLACK
self._rotate_left(x.parent)
x = self.root # Done
else:
# Mirror of above (x is right child)
w = x.parent.left # Sibling
if w.color == Color.RED:
# Case 1: Sibling is red
w.color = Color.BLACK
x.parent.color = Color.RED
self._rotate_right(x.parent)
w = x.parent.left
if w.right.color == Color.BLACK and w.left.color == Color.BLACK:
# Case 2: Sibling and both nephews are black
w.color = Color.RED
x = x.parent
else:
if w.left.color == Color.BLACK:
# Case 3: Sibling's left child is black
w.right.color = Color.BLACK
w.color = Color.RED
self._rotate_left(w)
w = x.parent.left
# Case 4: Sibling's left child is red
w.color = x.parent.color
x.parent.color = Color.BLACK
w.left.color = Color.BLACK
self._rotate_right(x.parent)
x = self.root
# Remove extra black by coloring x black
x.color = Color.BLACK
# -------------------------------------------------------------------------
# Traversal Methods
# -------------------------------------------------------------------------
class TraverseOrder(Enum):
"""Enumeration of tree traversal orders."""
preorder = 1
inorder = 2
postorder = 3
def traverse(self, order: TraverseOrder) -> list:
"""Traverse the tree in the specified order. Returns list of values."""
result = []
def _preorder(node: RbNode):
if node is self.NIL:
return
result.append(node.val)
_preorder(node.left)
_preorder(node.right)
def _inorder(node: RbNode):
if node is self.NIL:
return
_inorder(node.left)
result.append(node.val)
_inorder(node.right)
def _postorder(node: RbNode):
if node is self.NIL:
return
_postorder(node.left)
_postorder(node.right)
result.append(node.val)
traversals = {
RedBlackTree.TraverseOrder.preorder: _preorder,
RedBlackTree.TraverseOrder.inorder: _inorder,
RedBlackTree.TraverseOrder.postorder: _postorder,
}
if order not in traversals:
raise TypeError("Invalid traverse order passed.")
traversals[order](self.root)
return result
def inorder_traversal(self) -> list:
"""Return values in sorted (in-order) sequence."""
return self.traverse(RedBlackTree.TraverseOrder.inorder)
def levels_traversal(self) -> dict[int, list]:
"""Return values grouped by level (breadth-first). Level 0 is root."""
if self.root is self.NIL:
return {}
levels = {}
queue = [(self.root, 0)]
for node, level in queue:
if level not in levels:
levels[level] = []
levels[level].append(node.val)
if node.left is not self.NIL:
queue.append((node.left, level + 1))
if node.right is not self.NIL:
queue.append((node.right, level + 1))
return levels
# -------------------------------------------------------------------------
# Depth Helpers
# -------------------------------------------------------------------------
def min_depth(self) -> int:
"""Return minimum depth (shortest path from root to a leaf). -1 if empty."""
if self.root is self.NIL:
return -1
min_lvl = -1
def _dfs(node: RbNode, depth: int):
nonlocal min_lvl
if node is self.NIL:
return
# Found a leaf (both children are NIL)
if node.left is self.NIL and node.right is self.NIL:
if min_lvl == -1 or depth < min_lvl:
min_lvl = depth
_dfs(node.left, depth + 1)
_dfs(node.right, depth + 1)
_dfs(self.root, 0)
return min_lvl
def max_depth(self) -> int:
"""Return maximum depth (longest path from root to a leaf). -1 if empty."""
if self.root is self.NIL:
return -1
max_lvl = 0
def _dfs(node: RbNode, depth: int):
nonlocal max_lvl
if node is self.NIL:
return
if depth > max_lvl:
max_lvl = depth
_dfs(node.left, depth + 1)
_dfs(node.right, depth + 1)
_dfs(self.root, 0)
return max_lvl
# Example usage:
if __name__ == "__main__":
tree = RedBlackTree()
# Insert values
for val in [10, 20, 30, 40, 50, 25]:
tree.add(val)
# Traverse in different orders
print("Inorder: ", tree.traverse(RedBlackTree.TraverseOrder.inorder)) # [10, 20, 25, 30, 40, 50]
print("Preorder: ", tree.traverse(RedBlackTree.TraverseOrder.preorder))
print("Postorder:", tree.traverse(RedBlackTree.TraverseOrder.postorder))
print("By levels:", tree.levels_traversal())
# Search
print("Search 25:", tree.search(25)) # RbNode with val=25
print("25 in tree:", 25 in tree) # True
# Delete
tree.delete(40)
tree.delete(30)
print("After deletions:", tree.inorder_traversal())
About Red-Black Tree
How Red-Black Tree Works
A red-black tree is a self-balancing binary search tree where each node carries a color bit (red or black). A set of color-based rules ensures the tree remains approximately balanced, guaranteeing O(log n) time for search, insert, and delete. It is used extensively in language standard libraries.
Nodes are colored red or black following rules: the root is black, red nodes cannot have red children, and all paths from a node to its leaf descendants contain the same number of black nodes. After insertions and deletions, fix violations with recoloring and rotations.
Complexity
- Time
- O(log n)
- Space
- O(n)
When to Use Red-Black Tree
- Standard library implementations (Java TreeMap, C++ std::map)
- Linux kernel's Completely Fair Scheduler
- Balanced tree operations where slightly relaxed balance is acceptable