Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 1 / d

Use the conventional bottom-up red-black tree insertion: insert a red node by the binary search tree rule, repair a red parent with recolouring or tree rotations, and make the root black. Write $B$ and $R$ for black and red. The first three insertions give root $34_B$, with $21_R$ on the left and $55_R$ on the right.

Inserting $40$ as the left child of $55$ gives a red parent and a red uncle. Recolour $21,55$ black and retain a black root $34$. Inserting $45$ then gives the inner configuration $55_B$–$40_R$–$45_R$. A left tree rotation at $40$, followed by a right tree rotation at $55$, produces a subtree rooted at $45_B$ with $40_R$ and $55_R$ beneath it. Finally insert $37_R$ to the left of $40_R$. Its uncle $55_R$ is red, so recolour $40,55$ black and $45$ red. No further repair is required because $45$ has black parent $34$.

The final root is $34_B$; its left child is $21_B$ and its right child is $45_R$. Under $45_R$ are $40_B$ on the left and $55_B$ on the right; $40_B$ has left child $37_R$. All omitted children are black null sentinels. Each root-to-null graph path has two real black nodes, and no red node has a red child.