Red-black · insertion

Use rotations and link-color changes to preserve ordered search with logarithmic height. Null leaves are implicitly black.

Remember: Repair red links; preserve equal black height.

Example: Insert 10 then 20: rotate the red right link left and keep the root black.

Time: O(log n) / insert. Auxiliary space: O(log n).

Formula: Black root; no red-red edge; equal black height to every null leaf

Left-leaning red-black (LLRB) insertion. Colors represent incoming links; the root is black and null leaves are implicitly black. Intermediate repairs may temporarily violate invariants. Duplicates are ignored. Build: O(n log n); tree storage: O(n). Deletion is not included.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.