In this assignment you will write 2 methods to rotate the binary search tree (BST), both left and right given a pivot node. Tree rotations are an important operation used in balancing binary search trees such as AVL, Red-Black, and Splay. Additionally, you will need to write a private helper method for finding the parent node. BRIDGES is used to display the tree. The final output is a web link that displays the tree after all nodes are inserted, after right, and after left rotations.

// BST implementation with nodes as BRIDGES BSTElement objects. insert,

add_node(), getNode(), getNode() methods provided. Students to code

rotateRight() and rotateLeft() methods.

#include

#include

#include "Bridges.h"

#include "BSTElement.h"

using namespace std;

using namespace bridges;

std::string getEnvVar(string const & key);

struct pivotFamily {

BSTElement *pivot;

BSTElement *pivot_leftchild;

BSTElement *pivot_rightchild;

BSTElement *pivot_parent;

BSTElement *pivot_parent_leftchild;

BSTElement *pivot_parent_rightchild;

BSTElement *pivot_grandparent;

};

class BST {

public:

BST();

int insert(int key, string value);

BSTElement* getNode(int key) const;

void rotateRight(BSTElement *pivot);

void rotateLeft(BSTElement *pivot);

void display();

private:

BSTElement *root;

// Private methods

void add_node(BSTElement *parent,

BSTElement *new_node);

BSTElement* findParentNode(BSTElement

string> *node) const;

pivotFamily findFamily(BSTElement *pivot);

};

int main() {

BST my_tree;

my_tree.insert(2, "two");

my_tree.insert(1, "one");

my_tree.insert(3, "three");

my_tree.insert(7, "seven");

my_tree.insert(10, "ten");

my_tree.insert(2, "two");

my_tree.insert(5, "five");

my_tree.insert(8, "eight");

my_tree.insert(6, "six");

my_tree.insert(4, "four");

my_tree.display();

BSTElement *n = my_tree.getNode(5);

if (n != nullptr) {

cout << "Value of key is " << n->getValue() << endl;

my_tree.rotateRight(n);

my_tree.display(); // Check if right rotation was

correctly implemented

n = my_tree.getNode(7);

my_tree.rotateLeft(n);

my_tree.display();

}

else {

cout << "Node does not exist" << endl;

}

return 0;

}

BST::BST() {

root = nullptr;

}

int BST::insert(int key, string value) {

BSTElement *new_node = new BSTElement(key,

value);

assert(new_node);

new_node->setKey(key);

new_node->setLeft(nullptr);

new_node->setRight(nullptr);

if (root == nullptr) {

root = new_node;

}

else

add_node(root, new_node);

return 1; //Success

}

BSTElement* BST::getNode(int element) const {

BSTElement* current = root;

while (current != nullptr)

{

if (element < current->getKey())

{

current = current->getLeft();

}

else if (element > current->getKey())

{

current = current->getRight();

}

else return current;

}

return nullptr;

}

void BST::rotateRight(BSTElement *pivot)

{

// Your code here

}

void BST::rotateLeft(BSTElement *pivot)

{

// Your code here

}

void BST::display() {

string hilite_color = "orange",

def_color = "green",

end_color = "red";

Bridges::initialize(7, getEnvVar("BRIDGESUSERNAME"),

getEnvVar("BRIDGESKEY"));

Bridges::setTitle("Binary Search Tree Visualization");

Bridges::setDataStructure(root);

root->getVisualizer()->setColor(Color("red"));

Bridges::visualize();

}

// Private methods

void BST::add_node(BSTElement *parent, BSTElement

string> *new_node) {

if (new_node->getKey() < parent->getKey())

{

if (parent->getLeft() == nullptr)

parent->setLeft(new_node);

else

add_node(parent->getLeft(), new_node);

}

else if (new_node->getKey() > parent->getKey())

{

if (parent->getRight() == nullptr)

parent->setRight(new_node);

else

add_node(parent->getRight(), new_node);

}

}

BSTElement* BST::findParentNode(BSTElement

*node) const

{

// Your code here

}

pivotFamily BST::findFamily(BSTElement *pivot)

{

pivotFamily pF;

pF.pivot = pivot;

pF.pivot_parent = findParentNode(pivot);

pF.pivot_leftchild = pivot->getLeft();

pF.pivot_rightchild = pivot->getRight();

pF.pivot_parent_leftchild = (pF.pivot_parent)->getLeft(); //possibly

same as pivot

pF.pivot_parent_rightchild = (pF.pivot_parent)->getRight(); //possible

same as pivot

pF.pivot_grandparent = findParentNode(pF.pivot_parent);

return pF;

}

string getEnvVar(string const & key) {

char * val = getenv( key.c_str() );

return val == NULL ? string("") : string(val);

}