If y has other fields, copy them, too. Lines 7-8 give x a new parent. Lines 14-16 if the removed node is deleted, copy. In fact, random search trees on average have height, but we are worried about worst case height. Red-Black trees are binary search trees where each node is assigned a color, where the coloring scheme helps us maintain the height as .
Every node is colored either red or black.
If a node is red then both its children are black. Every single path from a node to a decendant leaf contains the same number of black nodes. For one of its children might be red. Because now all nodes may not have the same black height. A red-black tree with n internal nodes has height at most .