Practice Problem Set 6 Solutions
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?
Solution: There are five trees with \(w\) as root; the remaining three keys form one subtree below \(w\) in one of five ways. Symmetrically, there are five subtrees with \(z\) as root, and one subtree below \(z\). When \(x\) or \(y\) are root, there are children both to the left and the right (with two trees for each root). So the answer is \(\tfrac{10}{14}\).
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\)?
Solution: The root has one child if and only if the first element to be inserted is either the minimum or maximum. Each element is equally likely to be first, so the probability that this happens is \(\tfrac{2}{n}\). For \(n=4\) this is \(\tfrac{1}{2}\), significantly smaller than the probability when all trees are equally likely.
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\)?
Solution: The number of bottom-level split operations is one less than the number of bottom-level nodes. Each node has at least \(b/2\) keys, and this number is maximized when we have as many \(b/2\)-key nodes as possible. This can happen when we insert the keys in sorted order, in which case all but the last bottom-level node will have exactly \(b/2\) keys. The number of nodes is \[\left\lceil\frac{n}{b/2}\right\rceil,\] and the number of split operations is \[\left\lceil\frac{n}{b/2}\right\rceil-1.\]
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?
Solution:
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.
Solution:
Could this dot pattern have been generated by an unchanging (static) binary search tree? How or why not?
Solution: No. If it came from a static tree, the root would occur in every row of the dot pattern, and the only key for which that happens is b. But in a tree with b as root, it would not be possible for a single step to access both a and c, as happens in the second-from-bottom row of dots.
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.
Solution: \(\log_2 n\). You can cause the tree to have this ratio by repeatedly searching for the same key, at the leaf of the given tree. The same search sequence would have cost one per search for a different tree with the repeatedly-searched key at its root.