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 Θ(N)\Theta(N) results. In the best case of a perfectly balanced BST, the best-case height is Θ(logN)\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?

  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
Problem 2
Problem 3

The worst-case runtime is Θ(N)\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 logN\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

Last updated