Comment on page

# 16.7 Exercises

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

- 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?

- 3.Suppose we implement the Stack ADT using an array. What is the worst case runtime of a
`push`

operation with this underlying data structure?

`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`

.

- 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?

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

Last modified 8mo ago