Color augments ordinary search order
A red-black tree adds color metadata and invariants to binary-search ordering to prevent extreme imbalance. A standard presentation makes the root and external NIL leaves black, forbids a red node with a red child, and requires equal numbers of black nodes on every path from a given node to descendant NIL leaves. Use one consistent counting convention for black height. Colors do not encode key magnitude: red keys are not necessarily smaller than black ones. Lookup follows the usual left-smaller, right-larger rule. The additional invariants limit structure while preserving the same ordered-container semantics supplied by a binary search tree.
Black height limits the longest path
The prohibition on consecutive red nodes prevents arbitrarily many red nodes between black ones. A longest path can therefore be at most roughly twice the black-height contribution. Supporting a given black height requires enough nodes, leading to logarithmic total height. Under standard conventions, height is at most twice log base two of n plus one. This is not the AVL rule limiting every local child-height difference to one. Red-black trees need not be perfect trees with all leaves at identical depth. The relaxed balance rules are enough to connect the structure to worst-case logarithmic search and update bounds without imposing every stronger local shape constraint.
Trace insertion10,20,30
For a standard insertion-repair example, begin with black root10, insert red20 to its right, then red30 to the right of20. The red parent-child pair violates an invariant. With a black NIL uncle, this right-right case can be repaired by rotating left at10 and making20 black and10 red. The resulting tree has black root20 and red children10 and30. Every root-to-NIL path has equal black count and no consecutive red nodes. This example combines recoloring with a rotation. Neither the rotation name alone nor a correct inorder traversal establishes that every color invariant has also been repaired.
Recoloring can propagate upward
When an inserted node has a red parent and red uncle, a common repair recolors parent and uncle black and grandparent red. Making the grandparent red can create another conflict with a higher red parent, requiring continued inspection toward the root. Finally re-establish the root condition. Parent, grandparent, and uncle describe relationships relative to the position currently being repaired, not permanently fixed variables from the first insertion site. Failing to update those relationships after rotations or upward propagation can modify the wrong nodes. Track keys, colors, and links together and verify that the inorder key sequence remains unchanged through the repair.
Deletion and implementation variants need their own rules
Removing a black node can reduce the black count on one path, requiring repairs distinct from insertion. Sibling and child colors determine appropriate recoloring and rotations. A successful short insertion trace does not validate deletion. Variants such as left-leaning red-black trees impose additional direction rules on red links. Their compact implementation code cannot be mixed arbitrarily into every symmetric red-black representation without checking assumptions. Align NIL representation, parent links, duplicate-key policy, and the chosen invariant set. The general data-structure name does not mean every published insertion and deletion fragment shares an interchangeable internal representation or repair strategy.
Verify ordering and color invariants together
Check sorted inorder traversal, a black root, absence of red-red parent-child pairs, and equal black count along descendant paths. Compare mixed insertions and removals with a reference set, including sorted input, reverse input, duplicate handling, and root changes. Distinguish logarithmic structural bounds from concrete comparison, allocation, and cache costs. The three-key tree illustrates repair rather than reports measurements of a language’s standard container. Choose an implementation whose supported operations and guarantees match the task. Verification should connect color rules to the claimed height bound while independently checking that ordinary search-order and API behavior remain correct throughout updates.