rove that the height of a red-black tree is at most 2n, and that this bound cannot be substantially lowered.