You are asked to implement the RBT insertion of Problem 4 (ii) with C++. The framework of the code (main.cpp) is provided and you will need to fill in the missing code snippets in the node* RBtree::BSTinsert(int x) and the void RBtree::rightrotate(node *) functions, respectively. Please submit your code with a single file named main.cpp. In order to get some credits, your submitted file should at least be compilable; note that the provided code is already compilable except that it misses some pieces. Please read the comments in the code carefully and insert your code at the right places, i.e., within the star lines. The code file, main.cpp, is provided separately.

main.cpp

// main.cpp // PM II (14:332:351) HW 4, Problem 5, red-black tree (RBT) insertion; // please refer the pseudo-code at Page 24 of slide 12.pdf. // Please insert your code snippet according to the comments // Should you have any problem, please contact to shaogang.wang@rutgers.edu, before 11:55pm, 11/16/2017 #include using namespace std; // RBT node struct; a node contais 3 pointers, which point to the parenet, // left and right sub-tree, respectively. If the node were the root, its parent is set to be NULL struct node { int key; char color; node *parent; node *left; node *right; }; // RBT class class RBtree { node *root; public : RBtree() { root=NULL; } // I understand that I need to implement a destructor to release the newed memories, // but I'm too lazy to do so; it does not affect your implementation of insertion anyway, luckily. void insert(int x); // RBT insertiong node* BSTinsert(int); // you need to implement this (10 pts.) void disp(); // RBT display protected: void insertfix(node *); // fix the insertion so that the resulted tree is a RBT void leftrotate(node *); // do the left rotation void rightrotate(node *); // do the right rotation; you need to implement this (10 pts.) void display(node *); // display the subtree }; // Insert the key, x, with binary search tree (BST) insertion and return the pointer of the inserted node node* RBtree::BSTinsert(int x) { //create a node and color it red node *t=new node; t->key=x; t->left=NULL; t->right=NULL; t->color='r'; // STUDENT CODE SNIPPET HERE // Hint: you need to insert this node, t, at the appropriate place in the tree; // consider the situation when the tree is empty. //************************************* Please insert your code in between the two stat lines //************************************* return t; } void RBtree::insert(int x) { node * t = BSTinsert(x); insertfix(t); } void RBtree::insertfix(node *t) { // color it black and return if t is the root if(root==t) { t->color='b'; return; } node *u; // the node pointing to t's uncle while(t->parent!=NULL && t->parent->color=='r') { node *g = t->parent->parent; // grandparent of node t if(g->left==t->parent) { // t's parent is at the left of its grandparent u=g->right; if(u->color=='r') { // if uncle is red //change color of parent and uncle as black t->parent->color='b'; u->color='b'; // change grandparent as red g->color='r'; // change t as its grandparent t=g; } else { if(t->parent->right==t) { // t is at the right of its parent // Case 2 t=t->parent; leftrotate(t); } // Case 3 t->parent->color='b'; g->color='r'; rightrotate(g); } } else { // t's parent is at the right of its grandparent, do the mirror operation of above u=g->left; if(u->color=='r') { t->parent->color='b'; u->color='b'; g->color='r'; t=g; } else { if(t->parent->left==t) { t=t->parent; rightrotate(t); } t->parent->color='b'; g->color='r'; leftrotate(g); } } } if(root != NULL) { root->color='b'; root->parent=NULL; } } void RBtree::leftrotate(node *p) { if(p->right==NULL) return ; else { node *y=p->right; if(y->left!=NULL) { p->right=y->left; y->left->parent=p; } else p->right=NULL; if(p->parent!=NULL) y->parent=p->parent; if(p->parent==NULL) root=y; else { if(p==p->parent->left) p->parent->left=y; else p->parent->right=y; } y->left=p; p->parent=y; } } // do the right rotation; void RBtree::rightrotate(node *p) { // STUDENT CODE SNIPPET HERE // Hint: you want to refer to the leftrotate() function, which is basically the mirror operation of // the rightrotate() function //************************************* Please insert your code in between the two stat lines //************************************* } void RBtree::disp() { display(root); } void RBtree::display(node *p) { if(root==NULL) { cout<<" Empty Tree."; return ; } if(p!=NULL) { cout<<" \t NODE: "; cout<<" Key: "<key; cout<<" Colour: "; if(p->color=='b') cout<<"Black"; else cout<<"Red"; if(p->parent!=NULL) cout<<" Parent: "<parent->key; else cout<<" There is no parent of the node. "; if(p->left!=NULL) cout<<" Left Child: "<left->key; else cout<<" There is no left child of the node. "; if(p->right!=NULL) cout<<" Right Child: "<right->key; else cout<<" There is no right child of the node. "; cout<left) { cout<<" Left: "; display(p->left); } if(p->right) { cout<<" Right: "; display(p->right); } } } int main() { int keys[] = {7, 3, 18, 15, 22, 8, 17, 26, 16}; // Build a binary search tree (BST) with BSTinsert(); this is to test your BSTinsert() function // You will expect that each node is red since this is not a RBT RBtree bst; for(int i=0; i<9; i++) { bst.BSTinsert(keys[i]); } cout<<"********* Show the BST *********"<