C++ Code 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.

template class AVL_tree: public Search_tree { public: Error_code insert(const Record &new_data); Error_code remove(const Record &old_data);

void range_search(const Record &r1, const Record &r2, vector &results); bool immediate_predecessor(Record &key) const;

protected: // Auxiliary functions Error_code avl_insert(Binary_node* &sub_root, const Record &new_data, bool &taller); Error_code avl_delete(Binary_node* &sub_root, const Record &old_data, bool &shorter); void left_balance(Binary_node* &sub_root); void right_balance(Binary_node* &sub_root); void rotate_left(Binary_node* &sub_root); void rotate_right(Binary_node* &sub_root); void range_search_helper(const Record &r1, const Record &r2, vector &results, Binary_node* sub_root); };

template Error_code AVL_tree::insert(const Record &new_data) /* Post: If the key of new_data is already in the AVL_tree, a code of duplicate_error is returned. Otherwise, a code of success is returned and the Record new_data is inserted into the tree in such a way that the properties of an AVL tree are preserved. Uses: avl_insert. */ { bool taller; return avl_insert(this->root, new_data, taller); }

template Error_code AVL_tree::remove(const Record &old_data) /* Post: If a Record with a key matching that of target belongs to the AVL_tree, a code of success is returned, and the corresponding node is removed from the tree. Otherwise, a code of not_present is returned. Uses: Function search_and_destroy */ { bool shorter; return avl_delete(this->root, old_data, shorter); } template void range_search(const Record &r1, const Record &r2, vector &results) { range_search_helper(r1, r2, results, sub_root); }

template void AVL_tree::range_search_helper(const Record &r1, const Record &r2, vector &results, Binary_node* sub_root) { //base case if (sub_root== NULL)

if (r1 <= sub_root->data && r2 >= sub_root->data){ results.push_back(sub_root->data); cout << sub_root->data << endl; } left = range_search_helper(r1, r2, results,sub_root->left); right= range_search_helper(r1, r2, results, sub_root->right); }

template bool AVL_tree::immediate_predecessor(Record &key) const { if (!immediate_predecessor(key)) return false; else

return true; }

template Error_code AVL_tree::avl_insert(Binary_node* &sub_root, const Record &new_data, bool &taller) /* Pre: sub_root is either NULL or points to a subtree of the AVL_tree Post: If the key of new_data is already in the subtree, a code of duplicate_error is returned. Otherwise, a code of success is returned and the Record new_data is inserted into the subtree in such a way that the properties of an AVL tree have been preserved. If the subtree is increased in height, the parameter taller is set to true; otherwise it is set to false. Uses: Methods of struct AVL_node; functions avl_insert recursively, left_balance, and right_balance. */ { Error_code result = success; if (sub_root == NULL) { sub_root = new AVL_node(new_data); taller = true; } else if (new_data == sub_root->data) { result = duplicate_error; taller = false; } else if (new_data < sub_root->data) { // Insert in left subtree. result = avl_insert(sub_root->left, new_data, taller); if (taller == true) switch (sub_root->get_balance()) {// Change balance factors. case left_higher: left_balance(sub_root); taller = false; // Rebalancing always shortens the tree. break; case equal_height: sub_root->set_balance(left_higher); break; case right_higher: sub_root->set_balance(equal_height); taller = false; break; } } else { // Insert in right subtree. result = avl_insert(sub_root->right, new_data, taller); if (taller == true) switch (sub_root->get_balance()) { case left_higher: sub_root->set_balance(equal_height); taller = false; break; case equal_height: sub_root->set_balance(right_higher); break; case right_higher: right_balance(sub_root); taller = false; // Rebalancing always shortens the tree. break; } } return result; }

template Error_code AVL_tree::avl_delete(Binary_node* &sub_root, const Record &old_data, bool &shorter) { Error_code result = success;

// Code needed here for deletion ...

return result; }

template void AVL_tree::left_balance(Binary_node* &sub_root) /* Pre: sub_root points to a subtree of an AVL_tree that is doubly unbalanced on the left. Post: The AVL properties have been restored to the subtree. Uses: Methods of struct AVL_node; functions rotate_right and rotate_left. */ { Binary_node* &left_tree = sub_root->left; switch (left_tree->get_balance()) { case left_higher: // single rotation right sub_root->set_balance(equal_height); left_tree->set_balance(equal_height); rotate_right(sub_root); break; case equal_height: // impossible case in insertion cout << "WARNING: If you see this in an insertion, program error is detected in left_balance" << endl;

// Code needed here for deletion ...

break; case right_higher: // double rotation right Binary_node* sub_tree = left_tree->right; switch (sub_tree->get_balance()) { case equal_height: // impossible case in insertion sub_root->set_balance(equal_height); left_tree->set_balance(equal_height); break; case left_higher: sub_root->set_balance(right_higher); left_tree->set_balance(equal_height); break; case right_higher: sub_root->set_balance(equal_height); left_tree->set_balance(left_higher); break; } sub_tree->set_balance(equal_height); rotate_left(left_tree); rotate_right(sub_root); break; } }

template void AVL_tree::right_balance(Binary_node *&sub_root) /* Pre: sub_root points to a subtree of an AVL_tree that is doubly unbalanced on the right. Post: The AVL properties have been restored to the subtree. Uses: Methods of struct AVL_node; functions rotate_right and rotate_left. */ { Binary_node* &right_tree = sub_root->right; switch (right_tree->get_balance()) { case right_higher: // single rotation left sub_root->set_balance(equal_height); right_tree->set_balance(equal_height); rotate_left(sub_root); break; case equal_height: // impossible case in insertion cout << "WARNING: If you see this in an insertion, program error is detected in right_balance" << endl;

// Code needed here for deletion ...

break; case left_higher: // double rotation left Binary_node *sub_tree = right_tree->left; switch (sub_tree->get_balance()) { case equal_height: // impossible case in insertion sub_root->set_balance(equal_height); right_tree->set_balance(equal_height); break; case left_higher: sub_root->set_balance(equal_height); right_tree->set_balance(right_higher); break; case right_higher: sub_root->set_balance(left_higher); right_tree->set_balance(equal_height); break; } sub_tree->set_balance(equal_height); rotate_right(right_tree); rotate_left(sub_root); break; } }

template void AVL_tree::rotate_left(Binary_node *&sub_root) /* Pre: sub_root points to a subtree of the AVL_tree. This subtree has a nonempty right subtree. Post: sub_root is reset to point to its former right child, and the former sub_root node is the left child of the new sub_root node. */ { if (sub_root == NULL || sub_root->right == NULL) // impossible cases cout << "WARNING: program error detected in rotate_left" << endl; else { Binary_node *right_tree = sub_root->right; sub_root->right = right_tree->left; right_tree->left = sub_root; sub_root = right_tree; } }

template void AVL_tree::rotate_right(Binary_node *&sub_root) /* Pre: sub_root points to a subtree of the AVL_tree. This subtree has a nonempty left subtree. Post: sub_root is reset to point to its former left child, and the former sub_root node is the right child of the new sub_root node. */ { if (sub_root == NULL || sub_root->left == NULL) // impossible cases cout << "WARNING: program error detected in rotate_left" << endl; else { Binary_node *left_tree = sub_root->left; sub_root->left = left_tree->right; left_tree->right = sub_root; sub_root = left_tree; } }

main.cpp is

#include "utility.h" #include "Binary_node.h" #include "Binary_tree.h" #include "Search_tree.h" #include "AVL_node.h" #include "AVL_tree.h"

int main(){ string input = ""; bool exit_now = false; AVL_tree atree; while(!exit_now){ cout << endl; cout << "***********************" << endl; cout << "Menu:" << endl; cout << "1. Incremental Insert" << endl; cout << "2. Insert from File" << endl; cout << "3. Range Search" << endl; cout << "4. Immediate Predecessor" << endl; cout << "5. Incremental Delete" << endl; cout << "6. Delete from File" << endl; cout << "p. Print Tree" << endl; cout << "x. Exit" << endl; cout << "***********************" << endl;

getline(cin, input);

if(input == "1"){ cout << endl; cout << "Enter new integer keys to insert. Enter \"q\" to quit." << endl; cout << endl; getline(cin, input); while(input != "q"){ atree.insert(string_to_int(input)); atree.print(); getline(cin, input); } } else if(input == "2"){ cout << endl << "Enter Insertion File Name:" << endl; getline(cin, input); ifstream insertion_file; insertion_file.open(input.c_str()); if(!insertion_file.fail()){ while(getline(insertion_file, input)){ int input_num = string_to_int(input); atree.insert(input_num); } atree.print(); } else cout << "Invalid file name." << endl; } else if(input == "3"){ int v1, v2; vector results;

cout << endl; cout << "Enter the lower value:" << endl; getline(cin, input); v1 = string_to_int(input); cout << endl;

cout << "Enter the upper value:" << endl; getline(cin, input); v2 = string_to_int(input);

atree.range_search(v1, v2, results);

if (results.size() == 0) { cout << endl; cout << "There is no resord within the range." << endl; cout << endl; } else { cout << endl; for (unsigned int i = 0; i < results.size(); i++) cout << results[i] << " "; cout << endl; } } else if(input == "4"){ int key;

cout << endl; cout << "Enter the key:" << endl; getline(cin, input); key = string_to_int(input); cout << endl;

cout << endl; if (atree.immediate_predecessor(key)) { cout << "The immediate predecessor is " << key << ". "; } else { cout << "The immediate predecessor of " << key << " does not exist in the tree. "; } cout << endl; } else if(input == "5"){ cout << endl; cout << "Enter integer keys to delete. Enter \"q\" to quit." << endl; cout << endl; getline(cin, input); while(input != "q"){ atree.remove(string_to_int(input)); atree.print(); getline(cin, input); } } else if(input == "6"){ cout << endl << "Enter Deletion File Name:" << endl; getline(cin, input); ifstream deletion_file; deletion_file.open(input.c_str()); if(!deletion_file.fail()){ while(!deletion_file.fail() && !deletion_file.eof()){ getline(deletion_file, input); atree.remove(string_to_int(input)); } atree.print(); } else cout << "Invalid file name." << endl; } else if (input == "p") atree.print(); else if(input == "x") exit_now = true; }

/* for(int i=12; i>8; i--) tree.insert(i); tree.insert(2); tree.insert(1); tree.insert(3); tree.insert(4); tree.insert(5); tree.insert(6); tree.insert(7); tree.insert(8); atree.print();*/ }