Let rbts(bh) be the number of red-black trees with black height bh. Give a recursive formula for rbts(bh) in terms of rbts(bh – 1). How many red-black trees have heights 1, 2, and 3? Hint: Look at the hint for Exercise •• R17.18 .

Data from exercise R17.18

Show that a red-black tree with black height bh has at least 2^bh –1 nodes. Look at the root. A black child has black height bh – 1. A red child must have two black children of black height bh – 1.