consider the following proposed extension to an AVLTree class. T is any type. Wed like to add
Question:
consider the following proposed extension to an AVLTree class. T is any type. We’d like to add a method T firstAfter(T v) that, given a value v, returns the least element of the set that is ≥ v. If no such element exists, the method should return a special value “notFound”. v itself may or may not be in the set.
1. Suppose we implement firstAfter() as a top-down tree walk. What should we do if the root of the tree has a key < v? Justify why the behavior you specify is correct.
2. If the root has a key k > v, what should we do to determine whether k is the least key ≥ v? Justify why the behavior you specify is correct.
3. Based on your answers above, give pseudocode for an implementation of firstAfter() that runs on a BST in time proportional to its height.
Expert Answer:
1 If the root of tree has key v then we need to search in the rightsubtree o... View the full answer
