1. Add a method in AVL_tree.h as follows. (35 pts) void range_search(const Record &r1, const Record &r2, vector &results) const; The method takes two input parameters r1 and r2, and one output parameter results. It requires r1 r2. The method finds all the records that are between r1 and r2 in the AVL tree (including r1 and r2), and returns them in results. The output results is empty if no record is found within the range. 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. Requirements: 1. You should implement the methods based on the C++ code given to you. 2. Try to implement the method range_search such that its time complexity is proportional to K+log2N, where K is the number of the records/nodes in the result, that is, the number of records/nodes between r1 and r2. 3. Try to implement the method immediate_predecessor such that its time complexity is proportional to log2N