Write 2 methods to rotate the binary search tree (BST), both left and right given a pivot node and a method to find the parent node.

/* Tree rotations with pretty print for visualization */

#include

#include

#include // std::setw

#include

#include

#include

#include

using namespace std;

class Node {

private:

int key;

Node* left;

Node* right;

friend class BinarySearchTree;

};

struct pivotFamily {

Node *pivot;

Node *pivot_leftchild;

Node *pivot_rightchild;

Node *pivot_parent;

Node *pivot_parent_leftchild;

Node *pivot_parent_rightchild;

};

/*

This class implements a binary search tree whose

nodes hold strings.

*/

class BinarySearchTree {

public:

BinarySearchTree();

void insert(int element);

void pretty_display();

/* Tree rotation */

Node* findNode(int key) const; // Returns the address of the node containing key

Node* findParentNode(Node *node) const; // Returns address of the parent of node containing key

pivotFamily findFamily(Node *pivot); // Returns all nodes needed for rotation given pivot parent

void rotateRight(Node *pivot);

void rotateLeft(Node *pivot);

private:

void add_node(Node* parent, Node* new_node) const;

/* To pretty print binary tree */

int maxHeight(Node *p) const;

string intToString(int val);

void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque& nodesQueue, ostream& out);

void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque& nodesQueue, ostream& out);

void printLeaves(int indentSpace, int level, int nodesInThisLevel, const deque& nodesQueue, ostream& out);

void printPretty(Node *root, int level, int indentSpace, ostream& out);

Node* root;

};

BinarySearchTree::BinarySearchTree()

{

root = nullptr;

}

void BinarySearchTree::add_node(Node* parent, Node* new_node) const

{

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

{

if (parent->left == nullptr) { parent->left = new_node; }

else { add_node(parent->left, new_node); }

}

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

{

if (parent->right == nullptr) { parent->right = new_node; }

else { add_node(parent->right, new_node); }

}

}

void BinarySearchTree::insert(int element)

{

Node* new_node = new Node;

new_node->key = element;

new_node->left = nullptr;

new_node->right = nullptr;

if (root == nullptr) { root = new_node; }

else { add_node(root, new_node); }

}

void BinarySearchTree::pretty_display()

{

if (root == nullptr)

return;

printPretty(root, 1, 0, cout);

}

int BinarySearchTree::maxHeight(Node *p) const {

if (!p) return 0;

int leftHeight = maxHeight(p->left);

int rightHeight = maxHeight(p->right);

return (leftHeight > rightHeight) ? leftHeight + 1: rightHeight + 1;

}

// Convert an integer value to string

string BinarySearchTree::intToString(int val) {

ostringstream ss;

ss << val;

return ss.str();

}

// Print the arm branches (eg, / \ ) on a line

void BinarySearchTree::printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque& nodesQueue, ostream& out) {

deque::const_iterator iter = nodesQueue.begin();

for (int i = 0; i < nodesInThisLevel / 2; i++) {

out << ((i == 0) ? setw(startLen-1) : setw(nodeSpaceLen-2)) << "" << ((*iter++) ? "/" : " ");

out << setw(2*branchLen+2) << "" << ((*iter++) ? "\\" : " ");

}

out << endl;

}

// Print the branches and node (eg, ___10___ )

void BinarySearchTree::printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque& nodesQueue, ostream& out) {

deque::const_iterator iter = nodesQueue.begin();

for (int i = 0; i < nodesInThisLevel; i++, iter++) {

out << ((i == 0) ? setw(startLen) : setw(nodeSpaceLen)) << "" << ((*iter && (*iter)->left) ? setfill('_') : setfill(' '));

out << setw(branchLen+2) << ((*iter) ? intToString((*iter)->key) : "");

out << ((*iter && (*iter)->right) ? setfill('_') : setfill(' ')) << setw(branchLen) << "" << setfill(' ');

}

out << endl;

}

// Print the leaves only (just for the bottom row)

void BinarySearchTree::printLeaves(int indentSpace, int level, int nodesInThisLevel, const deque& nodesQueue, ostream& out) {

deque::const_iterator iter = nodesQueue.begin();

for (int i = 0; i < nodesInThisLevel; i++, iter++) {

out << ((i == 0) ? setw(indentSpace+2) : setw(2*level+2)) << ((*iter) ? intToString((*iter)->key) : "");

}

out << endl;

}

// Pretty formatting of a binary tree to the output stream

// @ param

// level Control how wide you want the tree to sparse (eg, level 1 has the minimum space between nodes, while level 2 has a larger space between nodes)

// indentSpace Change this to add some indent space to the left (eg, indentSpace of 0 means the lowest level of the left node will stick to the left margin)

void BinarySearchTree::printPretty(Node *root, int level, int indentSpace, ostream& out) {

int h = maxHeight(root);

int nodesInThisLevel = 1;

int branchLen = 2*((int)pow(2.0,h)-1) - (3-level)*(int)pow(2.0,h-1); // eq of the length of branch for each node of each level

int nodeSpaceLen = 2 + (level+1)*(int)pow(2.0,h); // distance between left neighbor node's right arm and right neighbor node's left arm

int startLen = branchLen + (3-level) + indentSpace; // starting space to the first node to print of each level (for the left most node of each level only)

deque nodesQueue;

nodesQueue.push_back(root);

for (int r = 1; r < h; r++) {

printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

branchLen = branchLen/2 - 1;

nodeSpaceLen = nodeSpaceLen/2 + 1;

startLen = branchLen + (3-level) + indentSpace;

printNodes(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

for (int i = 0; i < nodesInThisLevel; i++) {

Node *currNode = nodesQueue.front();

nodesQueue.pop_front();

if (currNode) {

nodesQueue.push_back(currNode->left);

nodesQueue.push_back(currNode->right);

} else {

nodesQueue.push_back(NULL);

nodesQueue.push_back(NULL);

}

}

nodesInThisLevel *= 2;

}

printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, out);

}

Node* BinarySearchTree::findNode(int element) const

{

Node* current = root;

while (current != nullptr)

{

if (element < current->key)

{

current = current->left;

}

else if (element > current->key)

{

current = current->right;

}

else return current;

}

return nullptr;

}

Node* BinarySearchTree::findParentNode(Node* node)const

{

//

}

pivotFamily BinarySearchTree::findFamily(Node *pivot)

{

pivotFamily pF;

pF.pivot_parent = findParentNode(pivot);

pF.pivot = pivot;

pF.pivot_leftchild = pivot->left;

pF.pivot_rightchild = pivot->right;

pF.pivot_parent_leftchild = (pF.pivot_parent)->left; //same as pivot

pF.pivot_parent_rightchild = (pF.pivot_parent)->right;

return pF;

}

void BinarySearchTree::rotateRight(Node *pivot)

{

//

}

void BinarySearchTree::rotateLeft(Node *pivot)

{

//

}

int main()

{

BinarySearchTree t;

t.insert(2);

t.insert(1);

t.insert(3);

t.insert(7);

t.insert(10);

t.insert(2);

t.insert(5);

t.insert(8);

t.insert(6);

t.insert(4);

t.pretty_display();

Node *n = t.findNode(5);

cout << "Node with element 5: " << n << " And parent is " << t.findParentNode(n) << endl;

pivotFamily pFam_R = t.findFamily(n);

cout << "pivot parent: " << pFam_R.pivot_parent << " pivot: " << pFam_R.pivot << " pivot left child: " << pFam_R.pivot_leftchild << " pivot right child: " << pFam_R.pivot_rightchild << " pivot parent right child: " << pFam_R.pivot_parent_rightchild << endl;

cout << "Rotate right" << endl;

t.rotateRight(n);

t.pretty_display();

n = t.findNode(7);

pivotFamily pFam_L = t.findFamily(n);

cout << "Rotate left" << endl;

t.rotateLeft(n);

t.pretty_display();

return 0;

}