Consider an operation replace(replacement Item, search Key) that locates, if possible, the item in a dictionary with the given search key. If the dictionary contains such an item, the method replaces it with replacement Item.

a. Write implementations of replace for the classes Array Dictionary, Tree Dictionary, and Hashed Dictionary, as described in this chapter.

b. For Tree Dictionary, under what circumstances can replace replace an item without altering the structure of the binary search tree? (See Exercise 6 in Chapter 16 .)

Chapter 16 Exercise 6:

Suppose that the ADT binary tree has the operation

It locates, if possible, the node in a binary tree that contains item and replaces item with replacement Item.

a. Add the operation replace to the link-based implementation of the ADT binary tree given in this chapter. The operation should replace an item without altering the tree structure.

b. Add the operation replace to the link-based implementation of the ADT binary search tree. Be sure that the tree remains a binary search tree.

c. Implement a method replace within a client of Binary Search Tree.