In a binary search tree, created by inserting $n$ elements in a randomly-chosen order without rebalancing, suppose that element $x$ is the $i$th largest of the elements to be inserted. What is the probability that $x$ is a leaf node of the tree, as a function of $n$ and $i$?
What is the smallest possible number of internal nodes in a valid WAVL tree whose root has rank 4? Draw a valid WAVL tree with this many internal nodes and with rank 4 at the root; in your drawing, label each node with the key it holds and with its rank.
Suppose that we have a collection of $n$ items $x_i$, so that their sorted order by weight is the same as the sorted order by access frequency: the most frequently accessed item is $x_i$, the next most frequently accessed is $x_2$, and so on up to $x_n$. We have seen that, if these items are given weights $w_i$, so that the total weight is $W$, then the amortized time to search for $x_i$ in a splay tree will be $O(\log(W/w_i))$.
Show how to choose a system of weights so that $\log(W/w_i)=O(\log i)$.
Show how to construct a static search tree such that the distance from the root for the $i$th item is $O(\log i)$.