AlgoPlus//structures / red-black
Read the theory

Red-Black Tree

A BST that stays balanced through node colours, recolouring, and rotations.

Operation
—
Inserting
—
Insert sequence
Legend
Red node
Black node
Being fixed
AI Tutor Workspace
—
In a nutshell
A red-black tree is a binary search tree that stays balanced using one cheap trick: every node is painted red or black, and a few colour rules force the tree to stay roughly even. The key rules are that no red node may sit directly above another red node, and every path from the root down to an empty spot must cross the same number of black nodes. A new node arrives red; if that breaks the no-red-red rule, the tree recolours nearby nodes or, when that is not enough, rotates them — quick local fixes that keep the height O(log n).
Ready
Press play to begin the cinematic walkthrough.
Colours are a cheap balance signal. A new node is red; if that breaks the no-red-red rule, recolour when the uncle is red, rotate when it's black — local fixes that keep every path's black count equal.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for Red-Black Tree.
Code Simulator
▼
1
def bst(root, val):
2
    # insert / search / traverse
3
    if root is None:
4
        return Node(val)  # Inserted/Found
5
    if val < root.val:
6
        root.left = bst(root.left, val)
7
    else:
8
        root.right = bst(root.right, val)
9
    # traversal order
10
    visit(root.val)  # Visit
Why Python? · Readable first, fast second

Dynamically typed and interpreted — every comparison and swap is dispatched by the interpreter at run time, so tight loops run roughly 10–100× slower than compiled C/C++. Unbeatable for learning the idea with the least code; not what you reach for when the inner loop is the bottleneck.