1. You should implement a data structure for tree node with data eld of type int
ID: 3633145 • Letter: 1
Question
1. You should implement a data structure for tree node with data eld of type int; and coloreld of type char, taking values of either r (for red) or b (for black). It should also have the fields for parent, lchild and rchild.
2. You should implement a function named RBwrite to write out the current red-black tree tothe screen, where the tree is stored in a pre-order format.
3. You should implement a function named RBread to read in a red-black tree from a file named RBinput.txt, where the tree is stored in a pre-order format (see below for details).
4. You should implement a function named RBinsert to insert a new node with the data field given as a parameter of the function and perform the x-up if necessary.
5. You should implement a function named RBdelete to delete the node whose data field matches the data given as a parameter of the function, and perform the x-up if necessary.
6. You should implement a main function which takes the following commands from the keyboard:
C
R
W
I n (first letter is capital i)
D n
S
On reading S, the program stops. On reading C, the program creates an empty tree, and waits for the next command.
On reading R, the program reads in the tree from file RBinput.txt,and waits for the next command.
On reading W, the program writes the current tree to the screen in pre-order format, and waits for the next command.
On reading I n, the programinserts a new node with data n into the current red-black tree and perform the correspondingxes, and waits for the next command. Insertion is only performed when there is no node in the tree with data field equal to n. When there is already such a node, your program should print out a line "node already in the tree" and wait for the next command.
On reading D n,the program will delete the node with data n, perform the necessary fix-up, and waits for the next command. If there is no node with data field equal to n, the program prints "no such node in the tree" and waits for the next command.
Explanation / Answer
class RBT{private: struct node { int count; // counts the number of times the string has been inserted std::string data; // Storage for String Data node *parent; // pointer to this node's parent node *LCH; // pointer to this node's left child node *RCH; // pointer to this node's right child bool isRed; // bool value to specify color of node }; node *root; // pointer to the tree's root node node *nil; // nil node used to implement RBT(aka sentinel) void traverse(node *t); // perform an in-order traversal int height(node *p); // gets height of tree int totalNodes(node *p); // gets total nodes in tree int totalWords(node *p); // gets total words in tree void insertFix(node *z); // fixes tree if RBT rules are broken void RR(node *z); // performs Right rotation at z void LR(node *z); // performs Left rotation at zpublic: int insert(std::string str); // tries to add str to tree. Returns the new count for str int search(std::string str); // searches for str. Returns count for str, 0 if not found void list(); // prints in-order traversal of tree void getHeight(); // prints the height of tree void getTotal(); // prints the total number of nodes in the tree, as well as total number of words void getComparisons(); // prints the number of comparisons used RBT(); // constructor -- just builds an empty tree with a NULL root pointer int numComp; // tracks number of comparisons, only counts for search and insert commands}; void RBT::insertFix(node *z){ // Private method to fix any rules that might be broken in the RBT. // Takes a starting node z, as an input parameter and returns nothing, // except for a happy feeling knowing the you are not breaking any RBT laws. // Definitions of placeholder nodes used in this method: // z = z // y = left or right uncle of z node *y; while (z->parent->isRed) { if(z->parent == z->parent->parent->LCH) { y = z->parent->parent->RCH; if(y->isRed) { z->parent->isRed = false; y->isRed = false; z->parent->parent->isRed = true; z = z->parent->parent; } else { if( z == z->parent->RCH) { z = z->parent; void RBT::LR(node *x){ // Method to perform a Left Rotation at Node z. Takes a node pointer // as a parameter. Returns void. node *y; // y is x's right child y = x->RCH; x->RCH = y->LCH; if (y->LCH != nil) {y->LCH->parent = x;} y->parent = x->parent; if (x->parent == nil) {root = y;} else { if (x == x->parent->LCH) {x->parent->LCH = y;} else {x->parent->RCH = y;} } y->LCH = x; x->parent = y;}void RBT::RR(node *x){ // Method to perform a Left Rotation at Node z. Takes a node pointer // as a parameter. Returns void. node *y; // y is x's left child y = x->LCH; x->LCH = y->RCH; if (y->RCH != nil) {y->RCH->parent = x;} y->parent = x->parent; if (x->parent == nil) {root = y;} else { if (x == x->parent->RCH) {x->parent->RCH = y;} else {x->parent->LCH = y;} } y->RCH = x; x->parent = y;} RBT::LR(z->parent->parent); } z->parent->isRed = false; z->parent->parent->isRed = true; RBT::RR(z); } else { y = z->parent->parent->LCH; if(y->isRed) { z->parent->isRed = false; y->isRed = false; z->parent->parent->isRed = true; z = z->parent->parent; } else { if( z == z->parent->LCH) { z = z->parent; RBT::RR(z->parent->parent); } z->parent->isRed = false; z->parent->parent->isRed = true; RBT::LR(z); } } } root->isRed = false;}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.