20.1 Preliminary approaches

20.1-1

Modify the data structures in this section to support duplicate keys.

To modify these structure to allow for multiple elements, instead of just storing a bit in each of the entries, we can store the head of a linked list representing how many elements of that value that are contained in the structure, with a $\text{NIL}$ value to represent having no elements of that value.

20.1-2

Modify the data structures in this section to support keys that have associated satellite data.

All operations will remain the same, except instead of the leaves of the tree being an array of integers, they will be an array of nodes, each of which stores $x.key$ in addition to whatever additional satellite data you wish.

20.1-3

Observe that, using the structures in this section, the way we find the successor and predecessor of a value $x$ does not depend on whether $x$ is in the set at the time. Show how to find the successor of $x$ in a binary search tree when $x$ is not stored in the tree.

To find the successor of a given key $k$ from a binary tree, call the procedure $\text{SUCC}(x, T.root)$. Note that this will return $\text{NIL}$ if there is no entry in the tree with a larger key.

20.1-4

Suppose that instead of superimposing a tree of degree $\sqrt u$, we were to superimpose a tree of degree $u^{1 / k}$, where $k > 1$ is a constant. What would be the height of such a tree, and how long would each of the operations take?

The new tree would have height $k$. $\text{INSERT}$ would take $O(k)$, $\text{MINIMUM}$, $\text{MAXIMUM}$, $\text{SUCCESSOR}$, $\text{PREDECESSOR}$, and $\text{DELETE}$ would take $O(ku^{1 / k})$.