15-451 MINI #3: due midnight Oct 5.
1.
(a) Draw the result of inserting the letters Z,Y,X,W,V,U into an
initially-empty B-tree with t=2 (i.e., a 2-3-4 tree). (For instance, if we
stopped after the first three inserts, your tree would just be a
single node with letters X,Y,Z in it.) Feel free to do an ascii
drawing like the kind in the lecture notes.
(b) Continue with the example in (a) by showing the result after
inserting T,S,R
2.
(a) Draw a treap containing the following (key priority) pairs:
(a 4), (b 6), (c 1), (d 3).
(b) It turns out that so long as the keys and priorities are all
distinct, there is only one treap consistent with any set of (key,
priority) pairs. Prove this by induction.