//Red-Black Tree //------ RBTree.cpp ---------- #include #pragma hdrstop #include "RBTree.h" #include #include #include #include #define Red 1 //define colors for tree nodes #define Black 0 //--------------------------------------------------------------------------- #pragma package(smart_init) TreeNode::TreeNode(char string[], int Location, TreeNode* NodeParent) { strcpy(DataString, string); RecordLocation = Location; Left = 0; Right = 0; Parent = NodeParent; //point the node to its parent Duplicates = 0; //node initially has now duplicates Color = Red; //new nodes start out red Deleted = false; //the node is not deleted } void TrimSpaces(char destination[], const char source[]) { //function to trim trailing spaces from a string int i; strcpy(destination, source); for(i = (strlen(source)-1); destination[i] == ' '; i--) { if(destination[i] == '\0') break; } destination[i+1] = '\0'; } RBTree::RBTree() { Root = 0; } RBTree::~RBTree() { DeleteTree(Root); //make call to DeleteTree which will free all dynamic memory } void RBTree::DeleteTree(TreeNode* Node) //operates with a post-order traversal { if(Node!=0) { DeleteTree(Node->Left); //delete the left sub-tree DeleteTree(Node->Right); //delete the right sub-tree DeleteTree(Node->Duplicates); delete Node; } Node = NULL; //Node is no longer in use } //3 cases may occur when inserting into tree. //Case 1: New node and its uncle are both red //Case 2: New node's parent is red and uncle is black & node is a left child //Case 3: New node's parent is red and uncle is black & node is a right child //Case 2 & 3 are opposite when node is in the right sub-tree void RBTree::Insert(char string[], int FilePosition) //creates a new node for string { TreeNode* Node; Node = InsertItem(string, FilePosition, Root); //insert string into the tree if(Node==0) return; //no changes to tree needed while((Node != Root) && (Node->Parent->Color == Red)) { if(Node->Parent == Node->Parent->Parent->Left ) //check to see if node { //is in the left sub-tree TreeNode* Node2 = Node->Parent->Parent->Right; //make node2 the uncle of node if(Node2!=0 && Node2->Color == Red) //if the uncle is red then it is case 1 { Node->Parent->Color = Black; //change color of parent to black Node2->Color = Black; //change color of uncle to black Node->Parent->Parent->Color = Red; //make node's grandparent red Node = Node->Parent->Parent; //move toward top of tree to make additional fixes } else //uncle is black, case 2 or 3 { if(Node == Node->Parent->Right) //check for case 3 { Node = Node->Parent; //node is a right child, so case 3 LeftRotation(Node); //which requires left rotation } Node->Parent->Color = Black; //adjustments for both case 2 Node->Parent->Parent->Color = Red; //and case 3 RightRotation(Node->Parent->Parent); // } } else //node is in right sub-tree { TreeNode* Node2 = Node->Parent->Parent->Left; //make node2 the uncle of node if(Node2!=0 && Node2->Color == Red) //if the uncle is red then it is case 1 { Node->Parent->Color = Black; //change color of parent to black Node2->Color = Black; //change color of uncle to black Node->Parent->Parent->Color = Red; //make node's grandparent red Node = Node->Parent->Parent; //move toward top of tree to make fixs } else //uncle is black, case 2 or 3 { if(Node == Node->Parent->Left) //check for case 3 (left and right is inverted) { Node = Node->Parent; //node is a left child, so case 3 RightRotation(Node); //which requires right rotation } Node->Parent->Color = Black; //adjustments for both case 2 Node->Parent->Parent->Color = Red; //and case 3 LeftRotation(Node->Parent->Parent); // } } } Root->Color = Black; //Root must be black by the rule of red-black trees } TreeNode* RBTree::InsertItem(char string[], int FilePosition, TreeNode* Node) { if(Root == 0) { Root = new TreeNode(string, FilePosition, 0); //establish the root Root->Color = Black; //Root must be black by the rule of red-black trees return Root; } while(1) { char temp[20], temp_string[20]; TrimSpaces(temp, Node->DataString); TrimSpaces(temp_string, string); int comparison = strcmp(temp_string, temp); if(Node->Deleted) //check to see if the node is deleted. If it is { //it may be possible to use the bool GreaterThanLeft, LessThanRight; //deleted node to hold the new if(Node->Left==0) //record if the new record falls GreaterThanLeft = true; //between the two children else { TrimSpaces(temp, Node->Left->DataString); if(strcmp(string, temp) > 0) GreaterThanLeft = true; else GreaterThanLeft = false; //string is not greater than the left child } //so deleted node can't be used for new record if(Node->Right==0) LessThanRight = true; else { TrimSpaces(temp, Node->Right->DataString); if(strcmp(string, temp) > 0) LessThanRight = true; else LessThanRight = false; //string is not less than the right child } //so deleted node can't be used for new record if(GreaterThanLeft && LessThanRight) { strcpy(Node->DataString, string); //deleted node can hold new record Node->RecordLocation = FilePosition; Node->Deleted = false; //node is no longer deleted return 0; //return 0 to avoid adjustments to tree which are } //not need since we just changed the contents of an } //existing node if(comparison < 0) { if(Node->Left == 0) //if Left is empty put the new node there { Node->Left = new TreeNode(string, FilePosition, Node); //add new node return Node->Left; //as a left child } else Node = Node->Left; //check left sub-tree } else if(comparison > 0) { if(Node->Right == 0) //if Right is empty put the new node there { Node->Right = new TreeNode(string, FilePosition, Node); //add new node return Node->Right; //as a left child } else Node = Node->Right; //check right sub-tree } else //node is a duplicate { TreeNode* TempNode = Node; while(TempNode->Duplicates != 0) //find the end of the duplicate list TempNode = TempNode->Duplicates; TempNode->Duplicates = new TreeNode(string, FilePosition, TempNode); return 0; //return 0 will prevent adjustments to tree } //which won't be needed when inserting a duplicate } } bool RBTree::Remove(char string[]) { TreeNode *Node; Node = SearchFirstMatch(string); //find the node in the tree if(Node==0) return false; //string could not be found if(Node->Duplicates!=0) { //if there is duplicates then one of the TreeNode* TempNode = Node; //duplicates can take the place of the TreeNode* PreviousNode; //deleted record while(TempNode->Duplicates!=0) { PreviousNode = TempNode; TempNode = TempNode->Duplicates; } strcpy(Node->DataString, TempNode->DataString); //copy the contents of the last Node->RecordLocation = TempNode->RecordLocation; //duplicate to the record to be delete TempNode; //deleted PreviousNode->Duplicates = 0; //terminate duplicate list return true; //deletion was successful } else Node->Deleted = true; //mark the node as deleted for lazy delete return true; } int RBTree::Search(char string[]) { TreeNode* Node = Root; int comparison; while(Node!=0) { char temp[20]; TrimSpaces(temp, Node->DataString); comparison = strcmp(string, temp); if(comparison < 0) Node = Node->Left; //look at left sub-tree else if(comparison > 0) Node = Node->Right; //look at right sub-tree else if(Node->Deleted) //check to see if the node is deleted return -1; //if it is then the record is not in the tree else return Node->RecordLocation; //string has been found } return -1; // the record cannot be found } TreeNode* RBTree::SearchFirstMatch(char string[]) //returns a pointer to the first node { //that matches string TreeNode* Node = Root; int comparison; while(Node!=0) { char temp[20]; TrimSpaces(temp, Node->DataString); comparison = strcmp(string, temp); if(comparison < 0) Node = Node->Left; //look at left sub-tree else if(comparison > 0) Node = Node->Right; //look at right sub-tree else if(Node->Deleted) //check to see if the node is deleted return 0; //if it is then the record is not in the tree else return Node; //string has been found } return 0; } void RBTree::SaveToFile(char FileName[]) //save nodes to file in the order that they { //are outputed by a preorder traversal FILE *OutputFile; OutputFile = fopen(FileName, "w"); if(OutputFile == NULL) return; SaveNode(Root, OutputFile); //recursive funciton that will save each node to file fclose(OutputFile); } void RBTree::SaveNode(const TreeNode* Node, FILE *OutputFile) { // % marks beginning of location number if(Node!=0) // # marks and of node { if(!Node->Deleted) //only save node if it is not deleted { fputs(Node->DataString, OutputFile); //output the node's string to file putc('%', OutputFile); //output flag char temp[10]; itoa(Node->RecordLocation, temp, 10); //convert int so that it can be sent to file fputs(temp, OutputFile); putc('#', OutputFile); } SaveNode(Node->Left, OutputFile); //save nodes in left sub-tree SaveNode(Node->Right, OutputFile); //save nodes in right sub-tree } } void RBTree::LoadFromFile(char FileName[]) //nodes are added to the tree in the same { //order that they were outputed by the fstream InputFile(FileName, ios::in); //pre-order traversal. As a result, the char chr; //tree has the same structures as the time char string[20]; //when it was saved to file char Location[6]; int i; for(InputFile.get(chr);!InputFile.eof(); InputFile.get(chr)) //read through the { //whole file for(i=0;chr!='%'; i++) //input the node's string until { // % is reached string[i] = chr; InputFile.get(chr); } string[i] = '\0'; //terminate the string InputFile.get(chr); for(i=0;chr!='#'; i++) { Location[i] = chr; //input the node's location until InputFile.get(chr); // # is reached } Location[i] ='\0'; Insert(string, atoi(Location)); //add the node to the tree } } int RBTree::LeftDepth() { return TreeDepth(Root->Left); //measure the left sub-tree } int RBTree::RightDepth() { return TreeDepth(Root->Right); //measure the right sub-tree } int RBTree::TreeDepth(TreeNode *Node) { int left = 0; int right = 0; if(Node->Left != 0) left = TreeDepth(Node->Left); //get the depth of the left sub-tree if(Node->Right != 0) right = TreeDepth(Node->Right); //get the depth of the right sub-tree if( left > right) //check to see which sub-tree is deeper return left+1; //return the depth of the left sub-tree plus 1 else return right+1; //return the depth of the right sub-tree plus 1 } int RBTree::NumberOfLeaves(TreeNode* Node) { int total = 0; if(Node->Left == 0 && Node->Right == 0) return 1; //the node is a leaf if(Node->Left!= 0) //count the number of leaves in the total += NumberOfLeaves(Node->Left); //left sub-tree if(Node->Right!=0) //count the number of leaves in the total += NumberOfLeaves(Node->Right); //right sub-tree return total; //return the total of all the leaves in this sub-tree } void RBTree::LeftRotation(TreeNode* Node) { TreeNode* Right = Node->Right; //hold node's right child Node->Right = Right->Left; //make the node's right child its right child's left child if(Right->Left != 0) Right->Left->Parent = Node; //point the child to its new parent if(Right != 0) Right->Parent = Node->Parent; //point the child to its new parent if(Node->Parent != 0) //if node is not the root { if(Node == Node->Parent->Left) //if node is a left child Node->Parent->Left = Right; //make node's right child its parent's left child else Node->Parent->Right = Right; //make node's right child its parent's right child } else Root = Right; //node's right child is now the root Right->Left = Node; //node becomes its right child's left child if(Node != 0) Node->Parent = Right; //point node to its new parent } void RBTree::RightRotation(TreeNode* Node) { TreeNode* Left = Node->Left; //hold node's left child Node->Left = Left->Right; //make the node's left child its left child's right child if(Left->Right != 0) Left->Right->Parent = Node; //point the child to its new parent if(Left != 0) Left->Parent = Node->Parent; //point the child to its new parent if(Node->Parent != 0) //if node is not the root { if(Node == Node->Parent->Right) //if node is a right child Node->Parent->Right = Left; //make node's left child its parent's right child else Node->Parent->Left = Left; //make node's left child its parent's left child } else Root = Left; //node's left child is now the root Left->Right = Node; //node becomes its left child's right child if(Node != 0) Node->Parent = Left; //point node to its new parent } //------ RBTree.h ------------ #include #ifndef RBTreeH #define RBTreeH //--------------------------------------------------------------------------- class TreeNode { public: TreeNode(char string[], int Location, TreeNode* NodeParent); int Color; //color propert of the node, 0=black, 1=red TreeNode* Left; TreeNode* Right; TreeNode* Parent; TreeNode* Duplicates; //hold list of duplicates char DataString[20]; //hold first or last name of record int RecordLocation; //hold record's position in the relative file bool Deleted; //flag for lazy delete }; class RBTree { public: RBTree(); ~RBTree(); int Search(char string[]); //returns the file position of string TreeNode* SearchFirstMatch(char string[]); //same as search but returns a TreeNode* //to the first matching node void Insert(char string[], int FilePosition); //creates new nodes TreeNode* InsertItem(char string[], int FilePosition, TreeNode* Node); bool Remove(char string[]); //removes nodes void LoadFromFile(char FileName[]); //recreates the tree from a file void SaveToFile(char FileName[]); //stores the tree to a file int LeftDepth(); //Finds the depth of the left sub-tree int RightDepth(); //Finds the depth of the right sub-tree int NumberOfLeaves(TreeNode*); //Finds the number of leaves in the tree TreeNode* Root; private: void LeftRotation(TreeNode* Node); //rotations used by insertion function to void RightRotation(TreeNode* Node); //balance the tree int TreeDepth(TreeNode*); //recursive function to find the depth from TreeNode* void DeleteTree(TreeNode*); //used with the destructor to destroy the tree void SaveNode(const TreeNode* Node, FILE *OutputFile); //saves the contents of a node to the file //pointed to by OutputFile }; #endif