COMPUTER SCIENCE TRIPOS Part IA – 2015 – Paper 1
Algorithms (FMS)
Reminders: A red-black tree has leaf nodes (black) and may have non-leaf nodes (red
or black). The height of a red-black tree is the number of edges on the longest path
from the root to any leaf.
Mathematical hint: Pk
j=1 2
−j = 1 − 2
−k
(a) Indicate whether each of the following trees is or is not a valid red-black tree.
Justify your answers with reference to the defining invariants of red-black trees.
You may, but do not have to, redraw the trees if it helps you clarify a point.
[8 marks]
t1 t2 t3
(b) Let r(h), b(h), l(h) respectively represent the number of red non-leaf nodes, the
number of black non-leaf nodes, and the number of leaf nodes in a red-black tree
as a function of the height h of the tree. Under each of the conditions stated
below, and assuming that the tree has as few red nodes as possible, derive
mathematical expressions for r(h), b(h), l(h), preferably in closed form. Clearly
justify your answers, with drawings if appropriate. Expressions that are valid
only for even (or odd) values of h can still earn full marks if properly derived
and explained.
(i) Derive the r(h), b(h), l(h) expressions assuming that the red-black tree has
the largest possible number of nodes for a given height h. [6 marks]
(ii) Derive the r(h), b(h), l(h) expressions assuming that the red-black tree has
the smallest possible number of nodes for a given height h. [6 marks]