RBTree

#include <vcl.h>
#pragma hdrstop

#include "RBTree.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>
#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
}


R