Red-black tree

Keys still divide left and right subtrees, while colors encode balancing information. Typical rules treat null links as black, equalize black counts along descendant paths, and restrict consecutive red relationships, preventing unbounded differences in path length.

Colors are structural metadata rather than properties of the application’s keys or decorative drawing choices. Updates must restore the prescribed invariants. A temporary intermediate shape during repair differs from the valid tree exposed after an operation completes.

References: [1]

The textbook’s left-leaning red-black representation encodes a 2–3-tree three-node as two binary nodes joined by a left red link. Collapsing such links reveals the balanced multi-key structure, while ordinary BST lookup still follows key order.

Rotations change link orientation and color flips reorganize local groupings. Left leaning is an additional convention of this representation, not a claim that every red-black variant uses identical repair code. Implementations must be compared through their stated invariants.

References: [1]

The constraints keep height logarithmic, supporting logarithmic worst-case search and prescribed updates. Ordered input therefore does not by itself stretch the tree into the chain possible in an unbalanced BST.

The structure also supports ordered operations such as extrema, boundaries, and range counts. Their required metadata and key-comparison rules still need maintenance; red-black balancing does not repair an inconsistent comparator or unauthorized key mutations.

References: [1]