COMPUTER SCIENCE TRIPOS Part IA – 2018 – Paper 1
Algorithms (RKH-DJW)
A 2-3 tree is analogous to a 2-3-4 tree but has only 2-nodes and 3-nodes.
(a) Show in detail the steps to build a 2-3 tree from the sequence {7,3,9,8,11,10}.
Highlight any procedural differences to building a 2-3-4 tree. [7 marks]
(b) A red-black tree can be based on a 2-3 tree. An example red violation for such
a structure is sketched below, with red nodes represented using unfilled circles.
Sketch examples of the remaining red-violation cases, providing example values
within the nodes. For each case, sketch its resolution, assuming each case occurs
as a sub-tree of a larger tree. [5 marks]
(c) Consider restricting the 2-3 variant of a red-black tree so that red nodes may
only lie on the left of a parent.
(i) Discuss the effect this has on the search and insert performance. How does
it impact the implementation? [5 marks]
(ii) How does it affect the worst-case costs of finding the minimum and
maximum values in the tree? [3 marks]