Practice Problem Set 6
Given four numbers \(w \lt x \lt y \lt z\), there are 14 possible binary search trees. If we choose one of these trees at random, with all trees equally likely, what it the probability that the root of the tree will have only one child?
If we choose a binary search tree on \(n\) items by starting with an empty tree and then inserting one item at a time, using the basic insertion operation without rebalancing, with all \(n!\) insertion orders equally likely, give a formula for the probability that the root of the tree will have only one child. What is the value of your formula for \(n=4\)?
Consider the B+ trees described in the lecture notes, and assume that the parameter b used to define these trees is an even number with \(b\ge 4\). In this structure, each node at the bottom level of the tree holds \(b-1\) key-value pairs. If we try to add any more keys than that, it is split into two nodes, each containing exactly \(b/2\) key-value pairs, and causing more changes to propagate upward in the tree.
If we start with an empty tree (one bottom-level node with zero keys in it), and then insert \(n\) keys one at a time, different insertion sequences will lead to different numbers of split operations at the bottom level of the tree. What is the maximum possible number of bottom-level split operations that can happen, as a function of \(n\) and \(b\)?
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 we arrange \(n\) keys into a perfectly balanced binary tree, of height \(\log_2 n\), and do not change that tree. What is the competitive ratio of using this static tree for the dynamic optimality problem, as a function of \(n\)? Describe a sequence \(S\) of requests that will cause this tree to have this ratio.