In C++ utilizing the given height function, implement the following functions to
ID: 3757121 • Letter: I
Question
In C++ utilizing the given height function, implement the following functions to rebalance a BST, do not implement or include anything besides what is given
#include <vector>
#include <string>
using namespace std;
int height(Node* root)
{
if (root == nullptr)
return -1;
return root->height;
}
class Node
{
public:
Node()
{
height = 0;
left = right = nullptr;
}
Node(string data)
{
this->data = data;
height = -1;
left = right = nullptr;
}
string data;
int height;
Node* left;
Node* right;
};
//Implement the following in O(k) time
void rebalance(Node* &root);
void right_rotate(Node* &root);
void left_rotate(Node* &root);
Explanation / Answer
//Modified C++ program
#include <vector>
#include <string>
using namespace std;
class Node
{
public:
Node()
{
height = 0;
left = NULL;
right = NULL;
}
Node(string data)
{
this->data = data;
height = -1;
left = NULL;
right = NULL;
}
string data;
int height;
Node* left;
Node* right;
};
int height(Node* root)
{
if (root == NULL)
return -1;
return root->height;
}
//Implement the following in O(k) time
void rightRotate(Node* &root ){
Node *x = root->left;
Node *T = x->right;
x->right = root;
root->left = T;
root->height = max(height(root->left), height(root->right))+1;
x->height = max(height(x->left), height(x->right))+1;
}
void leftRotate(Node* &root){
Node *y = root->right;
Node *T = y->left;
y->left = root;
root->right = T;
root->height = max(height(root->left), height(root->right))+1;
y->height = max(height(y->left), height(y->right))+1;
}
void rebalance(Node* &root ){
int balance = height(root->left) - height(root->right);
if (balance > 1 && root->data < root->left->data)
rightRotate(root);
if (balance < -1 && root->data > root->right->data)
leftRotate(root);
if (balance > 1 && root->data > root->left->data)
{
leftRotate(root->left);
rightRotate(root);
}
if (balance < -1 && root->data < root->right->data)
{
rightRotate(root->right);
leftRotate(root);
}
}