$2.$ Add a method in $$AVL$\_$tree.h$$ as follows. $(40$ pts$)$

bool immediate$\_$predecessor$($Record &key$)$ const;

The method looks for the immediate predecessor of the input key in the AVL$-$tree. If not found, the method returns false. Otherwise, it returns true and place the found immediate predecessor in key.

Note that if the given key is less than any record currently in the tree, its immediate predecessor does not exist. Also note that it is possible that key does not exist in the tree. But you can still find its immediate predecessor as long as key is not less than all the records currently in the tree.