Exercises A#
Note
You must complete these exercises by Wednesday of W6.
SequentialSearchST vs. BinarySearchST#
Which of the two implementations, SequentialSearchST or BinarySearchST, would you use for an application
that performs \(10^3\) put() and \(10^6\) get() operations in random order? Justify your choice.
Interpolation Search#
Exercise 3.1.24 of the book.
Assume the keys are doubles or integers. Write a version of binary search that assumes a uniform distribution of keys and will thus first look at the beginning of a dictionary for a word that begins with a letter close to the beginning of the alphabet.
More precisely, if the searched key is \(k_x\), the smallest key is \(k_{lo}\), and the largest key is \(k_{hi}\), interpolation search will first probe at the key at index fraction \(\lfloor (k_x-k_{lo})/(k_{hi}-k_{lo}) \cdot (\text{length}-1) \rfloor\) of the array instead of probing the middle (50th percentile) first.
Implement InterpolationSearchST and compare this on FrequencyCounter.
Software Caching in BinarySearchST#
Exercise 3.1.25 of the book.
It is very common to first test the presence of a key before adding or modifying the corresponding entry. That practice generates several consecutive searches for the same key.
The idea of caching is to store the last accessed key internally
and to use it opportunistically if it is still valid.
Modify BinarySearchST to incorporate this idea.
Validating a Binary Search Tree#
Exercise 3.2.31 of the book.
Write an isBST() method that takes a Node as an argument and returns true if the argument is the root of a valid BST, and false otherwise (i.e., verify that all properties of a BST are satisfied).
Do you think that testing (locally) for each node the property “the left child has a smaller key and the right child has a greater key” is sufficient? If not, give a counterexample.
What is the time complexity of your algorithm?
Valid BST Search Key Sequences#
Exercise 3.2.4 of the book.
Suppose a certain search tree has keys between 1 and 10 and we are looking for key 5. Which sequence(s) cannot match the sequence of the examined keys?
10, 9, 8, 7, 6, 5
4, 10, 8, 6, 5
1, 10, 2, 9, 3, 8, 4, 7, 6, 5
2, 7, 3, 8, 4, 5
1, 2, 10, 4, 8, 5
Validating a Red-Black BST#
Exercise 3.3.33 of the book.
Write a method is23() in RedBlackBST that checks that no node is connected
to two red links and that there is no red link to the right.
Also write a method isBalanced() that checks that any path from the root to a null link has the
same number of black links. Finally, combine isBST(), is23(), and isBalanced() to implement isRedBlackBST().
Enumerating BST Keys in Ascending Order#
How can you enumerate all stored keys in ascending order in a binary search tree? What is the time complexity of this operation? Justify your answer.
BST vs. 2-3 Tree Insertion Trace#
Starting from an initially empty binary search tree, what does the tree look like after inserting the keys 12, 5, 10, 3, 13, 14, 15, 17, 18, 15? For the same data, what would the tree look like for a 2-3 tree?
Does this example illustrate the advantages or disadvantages of these different data structures? Why?
Identifying Valid Red-Black BSTs#
Which of these trees are red-black BSTs? For each, draw the corresponding 2-3 tree (described on page 432).
MCQ on Tree Traversals#
BST Iterator#
Ceil#
Implement the ceil method of a Binary Search Tree (and BinarySearchST).
Higher Key#
Implement a method that returns the least key strictly greater than a given key: Higher key
MCQ on BST Time Complexity#
Red-Black Tree Insertions#
Red-Black Tree Conversion#
Implement a class that converts a 2-3 tree into a red-black tree: RedblackTreeConverter