Let a splay tree for the three keys a, b, c start with b as the root node, a as its left child, and c as its right child.
If we perform a sequence of four splay operations on this tree, on the nodes a, c, b, a, what trees do we get after each splay?
Draw the point set that represents the sequence of nodes accessed in these four operations. Your points should be a subset of a 3x4 grid where the three horizontal positions represent the three keys and the four vertical positions represent the four splay operations (ordered bottom to top), as in the lecture notes.
Could this dot pattern have been generated by an unchanging (static) binary search tree? How or why not?
Suppose that we wish to answer range median queries: that is, given a range [bottom,top] we wish to find the median of the keys within the range (the one in the middle position, rounding down if there are an even number of keys in the range). Describe how to do this using a constant number of ranking and unranking queries.
Suppose that our data is a set of (key,vote) pairs, and we wish to answer range majority queries: given a range [bottom,top] we wish to return a vote that is associated with more than half of the keys within the range, if such a vote exists. If a majority vote does not exist, the result of query is allowed to be arbitrary. Describe a value that can be associated with each (key,vote) pair, and an associative operation on these values, making this into a decomposable range searching problem that can be solved in logarithmic time per query. (Hint: the values can be sketches.)
Find three sorted lists of numbers \(S_0\), \(S_1\), and \(S_2\), with eight numbers in each list and with all 24 numbers different, such that when fractional cascading is applied to these numbers, none of the elements of \(S_2\) is included in \(T_0\).