Intuition The one core ideaA Red-Black tree is just a Binary Search Tree where every node also wears a colour (red or black), and a handful of colouring rules quietly force the tree to stay short — no path down to the bottom is ever more than twice as long as any other. Before you can understand why those colour rules work, you must first be fluent in every little symbol the parent note throws at you: nodes, children, leaves, height, black-height, and the pointer-surgery move called a rotation.
This page is the workshop where we build every tool the parent topic assumes you already own. We never use a symbol before we draw it.
Definition Node, edge, root, leaf, child, parentA node is a box that holds one number (a "key"). An edge is a line joining two boxes. A tree is boxes joined by edges so that starting from the top box you can reach every other box, and there are no loops.
The top box (no box above it) is the root .
A box directly below another, joined by one edge, is its child ; the box above is its parent .
A box with no children is a leaf .
Look at the figure. The plum box on top is the root . Follow any edge downward — the lower box is a child of the upper box. The two orange boxes at the very bottom have nothing beneath them: those are leaves .
Intuition Why we even draw trees this wayReal programs store thousands of numbers. If we lay them out as this branching shape and keep them sorted (next section), we can find any number by walking down just a few boxes instead of scanning them all. The whole point of the Trees chapter is: shape controls speed.
The parent note says things like "3 < 10 < 3 < 5 Binary Search Tree rule. Let's earn it.
Definition Binary Search Tree (BST) property"Binary " = every node has at most two children, called left and right .
The BST rule: for every node holding key k
all keys in its left subtree are < k all keys in its right subtree are > k
Intuition What the rule looks like as a motionTo find a number, stand at the root and ask one yes/no question: "is my target smaller than this box?" If yes, step left ; if larger, step right . Each step throws away half the remaining boxes. That is the whole reason a BST is fast — if it stays bushy and short.
The parent's "3 < 10 < 10 3 5
Common mistake "The BST rule is only about direct children."Why it feels right: you only ever compare with the one box in front of you.
Why it's wrong: the rule says the whole left subtree (every descendant on the left) must be smaller — not just the immediate left child. That is what keeps the search correct all the way down.
h height h edges on the longest path from the root down to a leaf. A single lonely node has height 0
Look at the two trees in the figure. Both hold the same five numbers 1 , 2 , 3 , 4 , 5
The left tree is a "stick" — every box has one child, so the longest path uses 4 = 4
The right tree is "bushy" — the longest path uses only 2 = 2
Intuition Why height is the enemySearching walks down one path, so the work is proportional to the height. The stick forces us to walk past almost every box — that is the O ( n ) log 2 n Everything Red-Black trees do is a scheme to keep h log 2 n n
Now the new ingredient. A Red-Black tree paints each node.
Definition Colour of a nodeEach node carries one extra bit: it is red or black . This is just a label — it does not change the BST ordering at all. Its only job is to record a promise about balance.
NIL leaf sentinel
Where an ordinary tree drawing shows "nothing" (a missing child), a Red-Black tree pretends there is still a tiny black box there, called ==NIL==. Every real data node's empty slots point to this sentinel.
NIL boxes are real black leaves for counting purposes
Intuition What black-heightbh ( x ) x down any path from x NIL at the bottom, and count only the black boxes you pass (not counting x black-height bh ( x )
The whole magic of property 5 is that this count is the same no matter which downward path you take. In the figure, every path from the root to a NIL passes exactly the same number of black boxes — that is the balance promise made visible.
Definition Subtree rooted atx x x plus everything reachable below it . That whole clump is the ==subtree rooted at x
Intuition Why the topic keeps saying "subtree"Every Red-Black rule ("all keys in the left subtree are smaller", "the subtree at x 2 bh ( x ) − 1 clump , not a single box. Recognising a subtree as a self-contained tree is what lets the parent's height proof use induction — assume the rule for the smaller subtrees, then stitch them together.
The parent's biggest assumed tool. See also Tree Rotations .
Definition Left rotation atx rotation rearranges three nodes to change the height without breaking the BST order . A left rotation at x pulls x y up , and pushes x down-left .
Follow the figure left-to-right:
Before: x y y b What we do: y x y left child; the orphaned subtree b x new right child.Why order survives: the sorted line reads a < x < b < y < c before and after . We only re-hung branches, never re-sorted keys.
Intuition Why rotation is "cheap" —O ( 1 ) a , b , c Big-O Analysis ). We never walk into those subtrees. That constant cost is exactly why Red-Black trees (and AVL Tree s) can afford to rotate during every insert.
A left rotation moves the pivot counter-clockwise — the right child swings up and over to the left. A right rotation is the mirror image.
Binary Search Tree order rule
Read it top-down: raw nodes give us both the BST order rule and the notion of height ; colours plus NIL give black-height ; rotation and subtree are the repair tools. All arrows converge on the Red-Black tree.
Cover the right side and answer aloud. If any stalls, re-read that section above.
What is the root of a tree? The single top node that has no parent.
State the BST ordering rule in one line. Every left-subtree key is smaller than the node; every right-subtree key is larger.
What does the height h Edges on the longest root-to-leaf path; search cost grows with it, so we want it near log 2 n
What does log 2 ( n + 1 ) Roughly how many boxes deep a perfectly bushy tree of n 2 n + 1
What is a NIL sentinel and what colour is it? A pretend empty leaf standing in for every missing child; it is always black and counts toward black-height.
Define black-height bh ( x ) The number of black nodes on any downward path from x NIL — the same for every such path.
What does a left rotation at x x y It lifts y x y y x
Why is a rotation O ( 1 ) It only re-points a constant number of edges, never touching the interiors of the subtrees.
Why must the BST order be preserved by a rotation? Otherwise later searches would walk the wrong way and fail to find keys.
Ready? Head back to the parent topic and the properties will read like plain English. Related deeper reading: 2-3-4 Tree (the model Red-Black trees imitate) and std::map / TreeMap internals (where they ship in real libraries).
