= Red-black tree insertion
In the usual bottom-up algorithm, insert a red node by the <binary search tree> rule. If its parent is black, no repair is needed. If its parent and uncle are red, recolour both black and recolour the grandparent red, then continue upward. If the uncle is black, an inner configuration first rotates the parent to become an outer configuration; rotating the grandparent and exchanging its colour with the parent's resolves the red-red conflict. Apply the left/right mirror cases as needed and finish with a black root. The <tree rotations> preserve key order, and the colour changes preserve equal <black height>. Different valid insertion conventions can produce different valid <red-black trees>, so a worked trace must identify its convention.
Back to article page
