16.7 Exercises

Factual

1. What is the best and worst-case height of a BST?

Problem 1

If we insert everything in order, the worst-case height of $\Theta(N)$ results. In the best case of a perfectly balanced BST, the best-case height is $\Theta(\log N)$.

Procedural

1. Suppose that a certain BST has keys that are integers between 1 and 10. During the search for 5, which of the following sequences of keys are possible?

   • 10, 9, 8, 7, 6, 5

   • 4, 10, 8, 7, 5, 3

   • 1, 10, 2, 9, 3, 8, 4, 7, 6, 5

   • 1, 2, 6, 8, 9, 5

2. Consider the below BST. What is the result after deleting 4 using Hibbard deletion, choosing the sucessor as the replacement?

1. Suppose we implement the Stack ADT using an array. What is the worst case runtime of a push operation with this underlying data structure?

Problem 1

• 10, 9, 8, 7, 6, 5: possible; this is the situation where we have a worst-case linear BST.

• 4, 10, 8, 7, 5, 3: not possible; we terminate our search once we reach the desired node.

• 1, 10, 2, 9, 3, 8, 4, 7, 6, 5: possible; the idea is that we should always search in the correct "direction" of our target node. If our target node is greater than our current node, then we should go to the right, and our next node should be larger. If our target node is less than our current node, then we should go to the left, and our next node should be smaller.

• 1, 2, 6, 8, 9, 5: not possible; note that this violates the constraint described above. When we reach 8, we should move to its left branch since our target node 5 is smaller, so we would never search 9.

Problem 2

Problem 3

The worst-case runtime is $\Theta(N)$, since a push might cause us to resize the underlying array.

Metacognitive

1. If inserting our data into a BST in random order yields $\log N$ height with high probability, why don't we just shuffle our data before inserting into the BST?
2. When we do Hibbard deletion from a BST, we always choose the successor as a replacement. The successor is guaranteed to only have zero or one child--why?

Problem 1

Often in real-world applications, we don't have all our data at once. For example, imagine you're collecting time-based data that you insert into a BST each time a new value is reported. There is no easy way to shuffle your data when you only get one or a few points at a time.

Problem 2

By definition, the successor is the maximum value in the subtree. Suppose, for the sake of contradiction, that the sucessor had two children. Then, it is not the maximum, since it is less than its right child. This is a contradiction, since we said the sucessor is the maximum value in the subtree. As such, the successor is guaranteed to have one child or less (if it has one child, it is its left child). Previous 16.6 Summary Next 17. Tree Traversals and Graphs