 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.