C++ Code 2. Add a method in “AVL_tree.h” as follows. (40 pts) bool immediate_pre
ID: 3853010 • Letter: C
Question
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 Record>
class AVL_tree: public Search_tree<Record> {
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<Record> &results);
bool immediate_predecessor(Record &key) const;
protected:
// Auxiliary functions
Error_code avl_insert(Binary_node<Record>* &sub_root, const Record &new_data, bool &taller);
Error_code avl_delete(Binary_node<Record>* &sub_root, const Record &old_data, bool &shorter);
void left_balance(Binary_node<Record>* &sub_root);
void right_balance(Binary_node<Record>* &sub_root);
void rotate_left(Binary_node<Record>* &sub_root);
void rotate_right(Binary_node<Record>* &sub_root);
void range_search_helper(const Record &r1, const Record &r2, vector<Record> &results,
Binary_node<Record>* sub_root);
};
template <class Record>
Error_code AVL_tree<Record>::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 <class Record>
Error_code AVL_tree<Record>::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 <class Record>
void range_search(const Record &r1, const Record &r2, vector<Record> &results)
{
range_search_helper(r1, r2, results, sub_root);
}
template <class Record>
void AVL_tree<Record>::range_search_helper(const Record &r1, const Record &r2, vector<Record> &results,
Binary_node<Record>* 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 <class Record>
bool AVL_tree<Record>::immediate_predecessor(Record &key) const {
if (!immediate_predecessor(key))
return false;
else
return true;
}
template <class Record>
Error_code AVL_tree<Record>::avl_insert(Binary_node<Record>* &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<Record>(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 <class Record>
Error_code AVL_tree<Record>::avl_delete(Binary_node<Record>* &sub_root,
const Record &old_data, bool &shorter)
{
Error_code result = success;
// Code needed here for deletion ...
return result;
}
template <class Record>
void AVL_tree<Record>::left_balance(Binary_node<Record>* &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<Record>* &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<Record>* 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 <class Record>
void AVL_tree<Record>::right_balance(Binary_node<Record> *&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<Record>* &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<Record> *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 <class Record>
void AVL_tree<Record>::rotate_left(Binary_node<Record> *&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<Record> *right_tree = sub_root->right;
sub_root->right = right_tree->left;
right_tree->left = sub_root;
sub_root = right_tree;
}
}
template <class Record>
void AVL_tree<Record>::rotate_right(Binary_node<Record> *&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<Record> *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<int> 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<Enter>" 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<int> 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<Enter>" 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();*/
}
Explanation / Answer
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl_node
{
int data;
struct avl_node *left;
struct avl_node *right;
}*root;
class avlTree
{
public:
int height(avl_node *);
int diff(avl_node *);
avl_node *rr_rotation(avl_node *);
avl_node *ll_rotation(avl_node *);
avl_node *lr_rotation(avl_node *);
avl_node *rl_rotation(avl_node *);
avl_node* balance(avl_node *);
avl_node* insert(avl_node *, int );
void display(avl_node *, int);
void inorder(avl_node *);
void preorder(avl_node *);
void postorder(avl_node *);
avlTree()
{
root = NULL;
}
};
int main()
{
int choice, item;
avlTree avl;
while (1)
{
cout<<" ---------------------"<<endl;
cout<<"AVL Tree Implementation"<<endl;
cout<<" ---------------------"<<endl;
cout<<"1.Insert Element into the tree"<<endl;
cout<<"2.Display Balanced AVL Tree"<<endl;
cout<<"3.InOrder traversal"<<endl;
cout<<"4.PreOrder traversal"<<endl;
cout<<"5.PostOrder traversal"<<endl;
cout<<"6.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
root = avl.insert(root, item);
break;
case 2:
if (root == NULL)
{
cout<<"Tree is Empty"<<endl;
continue;
}
cout<<"Balanced AVL Tree:"<<endl;
avl.display(root, 1);
break;
case 3:
cout<<"Inorder Traversal:"<<endl;
avl.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal:"<<endl;
avl.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal:"<<endl;
avl.postorder(root);
cout<<endl;
break;
case 6:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
int avlTree::height(avl_node *temp)
{
int h = 0;
if (temp != NULL)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int max_height = max (l_height, r_height);
h = max_height + 1;
}
return h;
}
int avlTree::diff(avl_node *temp)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int b_factor= l_height - r_height;
return b_factor;
}
avl_node *avlTree::rr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}
avl_node *avlTree::ll_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}
avl_node *avlTree::lr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}
avl_node *avlTree::rl_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}
avl_node *avlTree::balance(avl_node *temp)
{
int bal_factor = diff (temp);
if (bal_factor > 1)
{
if (diff (temp->left) > 0)
temp = ll_rotation (temp);
else
temp = lr_rotation (temp);
}
else if (bal_factor < -1)
{
if (diff (temp->right) > 0)
temp = rl_rotation (temp);
else
temp = rr_rotation (temp);
}
return temp;
}
avl_node *avlTree::insert(avl_node *root, int value)
{
if (root == NULL)
{
root = new avl_node;
root->data = value;
root->left = NULL;
root->right = NULL;
return root;
}
else if (value < root->data)
{
root->left = insert(root->left, value);
root = balance (root);
}
else if (value >= root->data)
{
root->right = insert(root->right, value);
root = balance (root);
}
return root;
}
void avlTree::display(avl_node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->right, level + 1);
printf(" ");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);
}
}
void avlTree::inorder(avl_node *tree)
{
if (tree == NULL)
return;
inorder (tree->left);
cout<<tree->data<<" ";
inorder (tree->right);
}
void avlTree::preorder(avl_node *tree)
{
if (tree == NULL)
return;
cout<<tree->data<<" ";
preorder (tree->left);
preorder (tree->right);
}
void avlTree::postorder(avl_node *tree)
{
if (tree == NULL)
return;
postorder ( tree ->left );
postorder ( tree ->right );
cout<<tree->data<<" ";
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.