//--------- AVL.cpp -------------- #include #pragma hdrstop #include #include #include "AVL.h" //--------------------------------------------------------------------------- #pragma package(smart_init) void TrimSpaces(char destination[], const char source[]) { int i; strcpy(destination, source); for(i = (strlen(source)-1); destination[i] == ' '; i--) { if(destination[i] == '\0') break; } destination[i+1] = '\0'; } TreeNode::TreeNode(TreeNode* LeftChild, TreeNode* RightChild, char string[], int FilePosition) { Left = LeftChild; Right = RightChild; strcpy(DataString, string); RecordLocation = FilePosition; Depth = 0; Deleted = false; Duplicates = 0; } AVL::AVL() { Root = 0; } AVL::~AVL() { DeleteTree(Root); //make call to DeleteTree which will free all dynamic memory } void AVL::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 } void AVL::Insert(char string[], int FilePosition) { InsertNode(string, FilePosition, Root, Root); } int AVL::InsertNode(char string[], int FilePosition, TreeNode* Node, TreeNode* PreviousNode) //creates a new node for string { if(Root == 0) //if the Root has not been established { Root = new TreeNode(0, 0, string, FilePosition); //esatablish root return 1; } char temp[20]; TrimSpaces(temp, PreviousNode->DataString); //trim spaces for comparison if(Node == 0) { char TempString[20]; TrimSpaces(TempString, string); //trim spaces for comparison if(strcmp(TempString, temp) > 0) PreviousNode->Right = new TreeNode(0, 0, string, FilePosition); //make it a right child else if(strcmp(TempString, temp) < 0) PreviousNode->Left = new TreeNode(0, 0, string, FilePosition); //make it a left child else { // The record is a duplicate, add it to the node's duplicate list PreviousNode->Duplicates = new TreeNode(0, 0, string, FilePosition); return 2; } return 1; } TrimSpaces(temp, Node->DataString); //trim spaces for comparison if(Node->Deleted) { // we use lazy deletes in this program bool GreaterThanLeft, LessThanRight; char temp2[20]; if(Node->Left!=0) { TrimSpaces(temp2, Node->Left->DataString); if(strcmp(string, temp2) > 0) //check to see if the record to be inserted is GreaterThanLeft = true; //greater than the left child of deleted node else GreaterThanLeft = false; } else GreaterThanLeft = true; //nothing in left so node is greater than it if(Node->Right!=0) { TrimSpaces(temp2, Node->Right->DataString); if(strcmp(string, temp2) > 0) LessThanRight = true; //check to see if the record to be inserted is else //greater than the right child of deleted node LessThanRight = false; } else LessThanRight = true; //nothing in right so node is greater than it if((LessThanRight && GreaterThanLeft) || strcmp(string, temp2) == 0) { //if new record is between children or the new record is equal to deleted record strcpy(Node->DataString, string); //replace the deleted node with the new node Node->RecordLocation = FilePosition; Node->Deleted = false; return 2; // no change in depth has occured, return 2 } } else if(strcmp(string, Node->DataString) < 0) //go to left subtree { int status = InsertNode(string, FilePosition, Node->Left, Node); //attempt to insert node in left if(status == 1) //if status is = to 1 we need to check for rotations { if(Node->Depth == -1) //the sub-tree is already left-sided so a rotation is needed { LeftRotation(Node); return 0; // 0 means not to check for rotation on next check } else if(Node->Depth == 0) //if the sub-tree had equal sides at the beginning Node->Depth = -1; //it has slightly more on the left after insertion else { Node->Depth = 0; //the tree now has equal sides return 0; // 0 means not to check for rotation on next check } } else if(status == 2) //status 2 means no rotations are needed return 2; } else if(strcmp(string, Node->DataString) > 0) { //insert node in right sub-tree int status = InsertNode(string, FilePosition, Node->Right, Node); if(status == 1) { if(Node->Depth == -1) { Node->Depth = 0; //the tree was left-sided, now it is balanaced return 0; // 0 means not to check for rotation on next check } else if(Node->Depth == 0) Node->Depth = 1; //The sub-tree is now heavier on the right else { RightRotation(Node); //right rotation needed return 0; // 0 means not to check for rotation on next check } } if(status == 2) // status 2 means that no roations will be needed return 2; } else { InsertNode(string, FilePosition, Node->Duplicates, Node); //the node is a duplicate return 2; // return 2 because duplicates won't be counted as adding to depth } return 1; // 1 means that rotations may be needed on recursive call that called this function } bool AVL::Remove(char string[]) { return FindAndRemove(string, Root); //Find and remove uses recursion to locate } //and destroy the node containing string void AVL::RightRotation(TreeNode* Node) //make a right rotation { TreeNode *Temp1, *Temp2, *HoldDuplicates; Temp1 = Node->Right; if(Temp1->Depth == 1) // if depth is 1 a righ-right rotations is needed { TreeNode* TempNode; // swap Temp1 with Node --// TempNode = new TreeNode(0, 0, Temp1->DataString, Temp1->RecordLocation); // strcpy(Temp1->DataString, Node->DataString); // Temp1->RecordLocation = Node->RecordLocation; // strcpy(Node->DataString, TempNode->DataString); // Node->RecordLocation = TempNode->RecordLocation; // //////////////// HoldDuplicates = Node->Duplicates; Node->Duplicates = Temp1->Duplicates; //swap the duplicate lists Temp1->Duplicates = HoldDuplicates; Node->Right = Temp1->Right; Temp1->Right = Temp1->Left; //reorder node configuration Temp1->Left = Node->Left; //node will be the parent of Temp1 Node->Left = Temp1; //and Temp1's right child Temp1->Depth = 0; // tree is now balanced delete TempNode; } else // A right-left rotation is needed { TreeNode* TempNode; Temp2 = Temp1->Left; TempNode = new TreeNode(0, 0, Temp2->DataString, Temp2->RecordLocation); strcpy(Temp2->DataString, Node->DataString); //swap node with temp2 // Temp2->RecordLocation = Node->RecordLocation; // strcpy(Node->DataString, TempNode->DataString); // Node->RecordLocation = TempNode->RecordLocation; // HoldDuplicates = Temp2->Duplicates; Temp2->Duplicates = Node->Duplicates; //swap the duplicate lists Node->Duplicates = HoldDuplicates; delete TempNode; Temp1->Left = Temp2->Right; Node->Right = Temp1; //node becomes the parent of Temp1 and Temp2 Temp2->Right = Temp2->Left; Temp2->Left = Node->Left; Node->Left = Temp2; if(Temp2->Depth == -1) Temp1->Depth = 1; //temp1 has lost its left sub-tree, update to reflex change else Temp1->Depth = 0; if(Temp2->Depth == 1) Temp2->Depth = -1; //temp2 has lost it righ-sub tree, new depth is -1 else Temp2->Depth = 0; } Node->Depth = 0; // node is now balanced } void AVL::LeftRotation(TreeNode* Node) //make a left rotation { TreeNode *Temp1, *Temp2, *HoldDuplicates; Temp1 = Node->Left; if(Temp1->Depth == -1) // if depth is -1 a left-left rotations is needed { TreeNode* TempNode; //swap node with Temp1 /// TempNode = new TreeNode(0, 0, Temp1->DataString, Temp1->RecordLocation); // strcpy(Temp1->DataString, Node->DataString); // Temp1->RecordLocation = Node->RecordLocation; // strcpy(Node->DataString, TempNode->DataString); // Node->RecordLocation = TempNode->RecordLocation; //////////// HoldDuplicates = Node->Duplicates; Node->Duplicates = Temp1->Duplicates; //swap duplicate lists Temp1->Duplicates = HoldDuplicates; Node->Left = Temp1->Left; Temp1->Left = Temp1->Right; //node becomes the parent of Temp1 Temp1->Right = Node->Right; //and Temp1's Left child Node->Right = Temp1; Temp1->Depth = 0; //temp1 is now balanced delete TempNode; } else { // left-right rotation needed TreeNode* TempNode; Temp2 = Temp1->Right; TempNode = new TreeNode(0, 0, Temp2->DataString, Temp2->RecordLocation); strcpy(Temp2->DataString, Node->DataString); //swap node with temp2 // Temp2->RecordLocation = Node->RecordLocation; // strcpy(Node->DataString, TempNode->DataString); // Node->RecordLocation = TempNode->RecordLocation; // HoldDuplicates = Temp2->Duplicates; Temp2->Duplicates = Node->Duplicates; //swap duplicate lists Node->Duplicates = HoldDuplicates; delete TempNode; Temp1->Right = Temp2->Left; Node->Left = Temp1; Temp2->Left = Temp2->Right; //node becomes the parent of Temp1 and Temp2 Temp2->Right = Node->Right; Node->Right = Temp2; if(Temp2->Depth == 1) Temp1->Depth = -1; //Temp1 has lost its right side in rotation else Temp1->Depth = 0; if(Temp2->Depth == -1) Temp2->Depth = 1; //Temp2 has lost its left side in rotation else Temp2->Depth = 0; } Node->Depth = 0; // tree is now balanced } bool AVL::FindAndRemove(char string[], TreeNode *Node) { if(Node == 0) return false; char temp[20]; TrimSpaces(temp, Node->DataString); int compare = strcmp(string, temp); if(compare < 0) return FindAndRemove(string, Node->Left); //look in left sub-tree else if(compare > 0) return FindAndRemove(string, Node->Right); //look in right sub-tree else if(Node->Duplicates!= 0) //if the node matches and it has duplicates { TreeNode* TempNode; TreeNode* PreviousNode; while(TempNode->Duplicates != 0) //find last node in duplicate list { PreviousNode = TempNode; TempNode = TempNode->Duplicates; } strcpy(Node->DataString, TempNode->DataString); //node will be set equal to the Node->RecordLocation = TempNode->RecordLocation; //last node in the duplicate list delete TempNode; //remove last node in duplicates list PreviousNode->Duplicates =0; //terminate the duplicate list } else { Node->Deleted = true; //delete the node return true; } } int AVL::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) return Node->RecordLocation; //string has been found else return -1; } } return -1; // the record cannot be found } TreeNode* AVL::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) return Node; //string has been found else return 0; } } return 0; } void AVL::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 AVL::SaveNode(const TreeNode* Node, FILE *OutputFile) { // % marks beginning of location number if(Node!=0) // # marks and of node { if(!Node->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->Duplicates, OutputFile); //save the duplicates if any } SaveNode(Node->Left, OutputFile); //save nodes in left sub-tree SaveNode(Node->Right, OutputFile); //save nodes in right sub-tree } } void AVL::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. char chr; char string[20]; 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 AVL::LeftDepth() { return TreeDepth(Root->Left); //measure the left sub-tree } int AVL::RightDepth() { return TreeDepth(Root->Right); //measure the right sub-tree } int AVL::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 AVL::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 } //---------- AVL.h -------------- #include #ifndef AVLH #define AVLH //--------------------------------------------------------------------------- class TreeNode { public: TreeNode(TreeNode* LeftChild, TreeNode* RightChild, char string[], int FilePosition); TreeNode* Left; TreeNode* Right; char DataString[20]; //hold first or last name of record int RecordLocation; //hold record's position in the relative file int Depth; bool Deleted; //to mark node as deleted (lazy delete) TreeNode* Duplicates; //will be used to list records that are duplicates }; class AVL { friend class avl_class; public: AVL(); ~AVL(); 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); //begins recursive call of InsertNode int InsertNode(char string[], int FilePosition, TreeNode*, TreeNode*); //creates new nodes 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); //used to make left rotations on the avl void RightRotation(TreeNode* Node); //used to make right rotations on the avl int TreeDepth(TreeNode*); //recursive function to find the depth from TreeNode* bool FindAndRemove(char string[], TreeNode *Node); //locates and removes the node containing string void RemoveLeaf(char[]); //removes a leaf containing the argument 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