Red Black Tree

A red-black tree is a self-balancing BST where each node is colored red or black and a small set of color invariants keep the tree height ≤ 2 log(n+1). Used in C++ std::map/std::set, Java TreeMap, the Linux kernel scheduler (CFS), and the Linux epoll ready-list.

Complexity

How it works

Invariants: (1) root is black; (2) red nodes have black children; (3) every root-to-leaf path has the same number of black nodes. After a normal BST insert (new node colored red), restore the invariants with rotations and recoloring — at most O(log n) work.

Python implementation

# Red-black trees are intricate; this is a working but compact insert.
# In production use sortedcontainers.SortedList or sortedcontainers.SortedDict.
RED, BLACK = True, False


class Node:
    __slots__ = ("key", "color", "left", "right", "parent")
    def __init__(self, key, color=RED):
        self.key, self.color = key, color
        self.left = self.right = self.parent = None


class RBTree:
    def __init__(self):
        self.NIL = Node(None, BLACK)
        self.root = self.NIL

    def _rotate_left(self, x):
        y = x.right
        x.right = y.left
        if y.left is not self.NIL: y.left.parent = x
        y.parent = x.parent
        if x.parent is None: self.root = y
        elif x is x.parent.left: x.parent.left = y
        else: x.parent.right = y
        y.left = x; x.parent = y

    def _rotate_right(self, x):
        y = x.left
        x.left = y.right
        if y.right is not self.NIL: y.right.parent = x
        y.parent = x.parent
        if x.parent is None: self.root = y
        elif x is x.parent.right: x.parent.right = y
        else: x.parent.left = y
        y.right = x; x.parent = y

    def insert(self, key):
        z = Node(key); z.left = z.right = self.NIL
        y, x = None, self.root
        while x is not self.NIL:
            y = x
            x = x.left if z.key < x.key else x.right
        z.parent = y
        if y is None: self.root = z
        elif z.key < y.key: y.left = z
        else: y.right = z
        self._insert_fixup(z)

    def _insert_fixup(self, z):
        while z.parent and z.parent.color == RED:
            gp = z.parent.parent
            if z.parent is gp.left:
                y = gp.right
                if y.color == RED:
                    z.parent.color = y.color = BLACK
                    gp.color = RED; z = gp
                else:
                    if z is z.parent.right:
                        z = z.parent; self._rotate_left(z)
                    z.parent.color = BLACK; gp.color = RED
                    self._rotate_right(gp)
            else:
                y = gp.left
                if y.color == RED:
                    z.parent.color = y.color = BLACK
                    gp.color = RED; z = gp
                else:
                    if z is z.parent.left:
                        z = z.parent; self._rotate_right(z)
                    z.parent.color = BLACK; gp.color = RED
                    self._rotate_left(gp)
        self.root.color = BLACK


t = RBTree()
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
    t.insert(k)
print(t.root.key)

Trade-offs

• Worst-case O(log n) on every operation — the safe default for in-memory ordered maps.
• More rotation cases than AVL but fewer rebalances on insert/delete in practice.
• Backing structure for C++ std::map, Java TreeMap, Linux CFS scheduler.
• Implementation is famously fiddly; use a library.

← Back to Algorithms