RedBlackTree.cpp

#include <iostream>
#include "RedBlackTree.h"
using namespace std;

/*
    Start of Node constructors
*/

Node::Node(int Tdata)
{
    data = Tdata;
    parent = NULL;
    left = NULL;
    right = NULL;
    isBlack = false;
}

Node::Node(int Tdata, Node* pL, Node *pR, Node* pParent)
{
    data = Tdata;
    parent = pParent;
    left = pL;
    right = pR;
    isBlack = false;
}

Node::Node(int Tdata, Node *pL, Node* pR, Node *pParent, bool bColour)
{
    data = Tdata;
    parent = pParent;
    left = pL;
    right = pR;
    parent = pParent;
    isBlack = bColour;
}
Node::Node(int Tdata, Node *pL, Node* pR, bool bColour)
{
    data = Tdata;
    parent = NULL;
    left = pL;
    right = pR;
    isBlack = bColour;
}

/*
    End of Node class constructors,

    Red Black tree constructor is below, initialzing the root ptr to NULL

*/
RedBlackTree::RedBlackTree()
{
    root = NULL;
}
/*
    RB Copy constructor which uses an internal helper function to make a deep copy of the tree
*/
RedBlackTree::RedBlackTree(const RedBlackTree &rhs)
{
    root = CloneTree(rhs.root);
}

/*
    Overloaded assignment operator which returns a pointer to a RB [Red Black] Tree object,
        Logic:
            1. Run alias test
            2. Deallocate memory for calling object
            3. Make deep copy of target

*/
RedBlackTree & RedBlackTree::operator=(const RedBlackTree &rhs)
{
    if(this != &rhs)
    {
        // deallocate memory for the calling object

        removeAll();
        // make a deep copy of its target
        root = CloneTree(rhs.root);
    }
    return *this;

}
/*
    Destructor for RB tree,
    uses a helper function to deallocate all nodes allocated on the heap to build the tree
*/

RedBlackTree::~RedBlackTree()
{
    removeAll();
}

/*
    Internal private helper function that gets called by the public insert method
        Takes in a pointer to a node as a parameter
        Returns true if the insert is succesful false if the client attempts to insert duplicate items into the tree

*/

bool RedBlackTree::bInsert(Node* pNode)
{
    Node *y = NULL;
    Node *x = root;
    bool bIns = false; // return value
    bool bFound = false;
    bool bEmpty = false;
    bEmpty = (root == NULL);
    // false to indicate that the value is not already in the tree, true to denote that the value is already there
    if(bPrivSearch(pNode->data, root) == true)
    {
        bIns = false;
        bFound = true;
    }
    if(bFound == false)
    {
        while(x != NULL)
        {
            y = x;
            if(pNode->data < x->data)
            {
                x = x->left;

            }
            else
            {
                x = x->right;

            }
        }  // while loop
        pNode->parent = y;
        if(y == NULL)
        {
            root = pNode;
        }
        else if(pNode->data < y->data)
        {
            y->left = pNode;
        }
            else
        {
            y->right = pNode;
        }
        pNode->left = NULL;
        pNode->right = NULL;
        pNode->isBlack = false;
        vInsertFixViolation(pNode);
        bIns = true;
    }

    return bIns;
}




/*
    Helper function that allows us to fix any violations that we may have when inserting into the tree
        Returns nothing since the function is void, takes in a node pointer as a parameter

        Violations that can occur when inserting a node into an RB tree
            1.  the node's left uncle is red
            2.  the node's uncle is black and the node is a right child
            3.  the node's uncle is black and the node is a left child
            =========================================================
            Symmetric cases
            =========================================================
            4.  the node's right uncle is red
            5.  the node's uncle is black and the node is a left child
            6.  the node's uncle is black and the node is a right child
        How to fix these issues, note case 1,2, and 3 and 4,5,6 are symmetrical siblings
            To fix case one we just perform colour changes by making the node's parent black and its uncle also black
            To fix case two, we just simply make case 2 fall into case 3 since the two cases are not mutually exclusive
                To enter case 2 via 3 we immediatly perform a left rotation about the node we have just inserted
                Afterwards we can fix case 3 by performing colour changes and a right rotation about that node's grandparent

*/

void RedBlackTree::vInsertFixViolation(Node *pNode)
{
    Node *y;
    while((pNode != root)&&(pNode->parent->isBlack == false))// start of while
    {
        //start if
        if((pNode->parent != NULL )&&(pNode->parent == pNode->parent->parent->left))
        {
            y = pNode->parent->parent->right; // the right uncle of y
            if((y!=NULL)&&(y->isBlack == false))
            {
                pNode->parent->isBlack = true;
                y->isBlack = true;
                pNode->parent->parent->isBlack = false;
                pNode = pNode->parent->parent;
            }
            else
            {
                if(pNode == pNode->parent->right)
                {
                    pNode = pNode->parent;
                    LeftRotation(pNode);
                }
                if(pNode->parent != NULL)
                {
                    pNode->parent->isBlack = true;
                    if(pNode->parent->parent != NULL)
                    {
                        pNode->parent->parent->isBlack = false;//
                        RightRotation(pNode->parent->parent);
                    }

                }

            }
        }// end if
        else
        {//
        /*start of else*/
            if(pNode->parent == pNode->parent->parent->right)
            {
                y = pNode->parent->parent->left; // uncle of node pNode on the left side;
                if((y!= NULL)&&(y->isBlack == false))
                {
                    pNode->parent->isBlack = true;
                    y->isBlack = true;
                    pNode->parent->parent->isBlack = false;
                    pNode = pNode->parent->parent;
                }
                else
                {
                    if(pNode == pNode->parent->left)
                    {
                        pNode = pNode->parent;
                        RightRotation(pNode);
                    }
                    if(pNode->parent != NULL)
                    {
                        pNode->parent->isBlack = true;
                        if(pNode->parent->parent != NULL)
                        {
                            pNode->parent->parent->isBlack = false;
                            LeftRotation(pNode->parent->parent);
                        }
                    }

                }
            }
        }// end of else
    }// end of while
    root->isBlack = true;
}
/*
    A private helper function that will enable us to return a pointer to a node in a tree,
    if it doesn't exist we just simply return NULL
    else we keep searching the right or left subtrees as needed until we reach the appropiate spot in the
    tree in which its node countains the appropiate datum that we are trying to find.
    Takes in two parameters: the data we would like to search for and a node pointer indicating where we would
    like to start the recursion
    Return: a pointer to the node indicating where in the tree our data is countained in, if it doesn't exist it simply returns NULL
*/

Node* RedBlackTree::pSearchPriv(int dataS, Node *pTr)
{
    if(pTr == NULL)
    {
        return NULL;
    }
    else if(dataS < pTr->data)
    {
        return pSearchPriv(dataS,pTr->left);
    }
    else if(pTr->data < dataS)
    {
        return pSearchPriv(dataS,pTr->right);
    }
    else
    {
        return pTr;
    }

}
/*
    Public search function:
    Takes in the data we would like to find as a parameter
    Returns true or false depending if we find that specific data or not.
*/
bool RedBlackTree::search(int data) const
{
    return bPrivSearch(data,root);
}
/*
    Follows the same structure as the other privateSearch function
*/
bool RedBlackTree::bPrivSearch(int dataS, Node *pTr) const
{//
    if((pTr == NULL))
    {
        return false;
    }
    else if(dataS < pTr->data)
    {
        return bPrivSearch(dataS,pTr->left);
    }
    else if(pTr->data < dataS)
    {
        return bPrivSearch(dataS, pTr->right);
    }
    else
    {
        return true;
    }
}

void RedBlackTree:: LeftRotation(Node *pNode)
{
    Node *y = pNode->right; // y is pNode's right child
    pNode->right = y->left;

    if(y->left != NULL)
    {
        y->left->parent = pNode;
    }
    y->parent = pNode->parent;
    if(pNode->parent == NULL)
    {
        root = y;
    }
    else
    {
        if(pNode == pNode->parent->left)
        {
            pNode->parent->left = y;
        }
        else
        {
            pNode->parent->right = y;
        }
    }
    /*else if (pNode == pNode->parent->left)
    {
        pNode->parent->left = y;
    }
    else
    {
        pNode->parent->right = y;
    }*/
    y->left = pNode;
    pNode->parent = y;
}

void RedBlackTree::RightRotation(Node *pNode)
{
    Node *y = pNode->left; // y is pNode's left child
    pNode->left = y->right;
    if(y->right != NULL)
    {
        y->right->parent = pNode;
    }
    y->parent = pNode->parent;
    if(pNode->parent == NULL)
    {
        root = y;
    }
    else
    {
        if(pNode == pNode->parent->right)
        {
            pNode->parent->right = y;
        }
        else
        {
            pNode->parent->left = y;
        }
    }
    /*else if(pNode == pNode->parent->right)
    {
        pNode->parent->right = y;
    }
    else
    {
        pNode->parent->left = y;
    }*/
    y->right = pNode;
    pNode->parent = y;
}

// Helper function
void RedBlackTree::PrintRecurse(Node *pTr)
{
    int i = 0;
    if(pTr != NULL)
    {
        //i++;
        PrintRecurse(pTr->left);
        cout << pTr->data << "";
        //i++;
        cout << "[" ;
        if(pTr->isBlack == true)
        {
            cout << "Black" << " ";
        }
        else
        {
            cout << "Red" << " ";
        }
        cout << "]";
        if(pTr->parent != NULL)
        {
            cout<< "(" << "parent is " << pTr->parent->data << ")" <<endl;
        }
        else
        {
            cout << endl;
        }
        PrintRecurse(pTr->right);
        //i++;

    }
    return;
}

void RedBlackTree::Print()
{
    PrintRecurse(root);
}

bool RedBlackTree::insert(int datum)
{
    Node *pNewNode = new Node(datum);
    pNewNode->isBlack = true;
    pNewNode->parent = NULL;
    pNewNode->left = NULL;
    pNewNode->right = NULL;
    return bInsert(pNewNode);
}

// Helper function that allows us to find the successor node in the Red-Black tree

Node* RedBlackTree::findMinPriv(Node *pNode)
{
    if(pNode == NULL)
    {
        return NULL;
    }
    if(pNode->left == NULL)
    {
        return pNode;
    }
    return findMinPriv(pNode->left);
}

int RedBlackTree::findMin()
{
    Node *pTr = findMinPriv(root);

    int iMin = 0;
    if(pTr != NULL)
    {
        iMin = pTr->data;
    }
    return iMin;
}

bool RedBlackTree::remove(int data)
{
    bool bRmv = false;
    Node* pNodetoRemove = pSearchPriv(data,root);
    if(pNodetoRemove!= NULL)
        bRmv = bRemove(pNodetoRemove);
    else
    {
        bRmv = false;
    }
    return bRmv;
}

bool RedBlackTree::bRemove(Node *pNode)
{
    Node *y;
    Node *x;
    bool bYOrigColour = false;
    bool bFound = false;
    bool bDel = false;

    if ((pNode != NULL)&&(bPrivSearch(pNode->data,root) == true))
    {
        bDel = false;
        bFound = true;

    }
#ifdef _oldcode
    if((pNode != NULL)&&(bFound == true))
    {

        if((pNode->left == NULL) || (pNode->right == NULL)) // case of one child
        {
            y = pNode;
        }
        else
        {
            y = findMinPriv(pNode->right); // case that there are two children;
        }
        if(y->left == NULL)
        {
            x = y->right;
        }
        else
        {
            x = y->left;
        }
        if((x!= NULL) && (y!= NULL))
        {
            x->parent = y->parent;
        }
        if(root == (x->parent = y->parent))
        {
            root->left = x;
        }
        else
        {
            if((y!= NULL) && (y == y->parent->left))
            {
                y->parent->left = x;
            }
            else
            {
                if( y != NULL)
                {
                    y->parent->right = x;
                }

            }
        }
        if((y!= NULL) && (y != pNode))
        {
            y->left = pNode->left;
            y->right = pNode->right;
            y->parent = pNode->parent;
            pNode->left->parent = pNode->right->parent = y;
            if(pNode == pNode->parent->left)
            {
                pNode->parent->left = y;
            }
            else
            {
                pNode->parent->right = y;
            }
            if((y!= NULL)&&(y->isBlack == true))
            {
                y->isBlack = pNode->isBlack;
                vPrivDeleteFix(x);

            }
            else
            {
                y->isBlack = pNode->isBlack;

            }
            delete pNode;

        }
        else
        {
            if((y!= NULL)&&(y->isBlack == true))
            {
                vPrivDeleteFix(x);
                delete y;
            }
        }

    }
#else
#ifdef _oldcode2
  bool bCont = true;
  y= ((pNode->left == NULL) || (pNode->right == NULL)) ? pNode : findMinPriv(pNode->right); // case that z has one or no children else z has two children
  x= (y->left == NULL) ? y->right : y->left;
  if(pNode == root)
  {
      if((pNode->left == NULL) && (pNode->right == NULL))
      {
          delete root;
          root = NULL;
          bCont = false;
      }
  }
  if(bCont)
  {
      // tries to identify if y's only child is right or left

     /* if (root == (x->parent = y->parent))*/ //{ /* assignment of y->p to x->p is intentional */
      if(y->parent == NULL)
        root = x;
      } else {
        if (y == y->parent->left) {
          y->parent->left=x;
        } else {
          y->parent->right=x;
        }
      }
      if (y != pNode) { /* y should not be nil in this case */

    #ifdef DEBUG_ASSERT
        Assert( (y!=nil),"y is nil in DeleteNode \n");
    #endif
        /* y is the node to splice out and x is its child */

        y->left=pNode->left;
        y->right=pNode->right;
        y->parent=pNode->parent;
        pNode->left->parent=pNode->right->parent=y;
        if (pNode == pNode->parent->left) {
          pNode->parent->left=y;
        } else {
          pNode->parent->right=y;
        }
        if ((x!= NULL)&&(y->isBlack == false)) {
            y->isBlack = pNode->isBlack;
          //DeleteFixUp(x);
            vPrivDeleteFix(x);
        } else
          y->isBlack = pNode->isBlack;
        delete pNode;
    #ifdef CHECK_RB_TREE_ASSUMPTIONS
        CheckAssumptions();
    #elif defined(DEBUG_ASSERT)
        Assert(!nil->red,"nil not black in RedBlackTree::Delete");
    #endif
      } else {
        if ((x != NULL)&&(y->isBlack== false)) vPrivDeleteFix(x);
        delete y;
    #ifdef CHECK_RB_TREE_ASSUMPTIONS
        CheckAssumptions();
    #elif defined(DEBUG_ASSERT)
        Assert(!nil->red,"nil not black in RedBlackTree::Delete");
    #endif
      }
  }
#else
#ifdef conceptcode_
    y = ((pNode->left == NULL)) || ((pNode->right == NULL)) ?
    pNode:
    findMinPriv(pNode->right);
    x =  (y->left != NULL)?
    y->left:
    y->right;
    /*if(pNode->left == NULL || pNode->right == NULL)
    {
        y = pNode;
    }
    else
    {
        y = findMinPriv(pNode->right);
    }*/
    /*if(y->left != NULL)
    {
        x = y->left;
    }
    else
    {
        x = y->right;
    }*/
    if(x != NULL)
    {
        x->parent = y->parent;
    }
    if(y->parent == NULL)
    {
        root = x;
    }
    else
    {
        if( y == y->parent->left)
        {
            y->parent->left = x;
        }
        else
        {
            y->parent->right = x;
        }

    }
    if( y!= pNode)
    {
        pNode->data = y->data;
    }
    if( (x!= NULL)&& (y->isBlack == true))
    {
        vPrivDeleteFix(x);
    }
    delete y;
    y = NULL;
    bDel = true;
#else
{
    // Case 1: node has no children = remove
    // Case 2: node has 1 children = move right or left, ignore node
    // Case 3: node has 2 children = find the successor and swap content
       Node *y = NULL;
       Node *x = NULL;
       bool   bRoot = false;

       if (pNode->left && pNode->right)
             y = findMinPriv (pNode->right);         // get the successor
       else
             y = pNode;

       // Case 2, check for right or left node
       if(y->left != NULL)
             x = y->left;
       else
             x = y->right;

       // Case 1 & 2: ignore node
       // Case 3: ignore successor
       if(x != NULL)
             x->parent = y->parent;

       if(y->parent == NULL)
       {
             // this means this is the root node DELETION!!
             root = y;
             bRoot = true;
       }
       else
       {
             // now change the y's parent node left & right pointers
             if( y == y->parent->left)
             {
                    // y is the left node of parent then
                    y->parent->left = x;
             }
             else
                    y->parent->right = x;
       }

       // Case 1 & Case 2: y is always equal to node
       // Case 3: y = successor(node)
       // Case 3: pending thing, swap content between node & y
       if (y != pNode)
       {
             pNode->data = y->data;
             // we can ignore left, right, parent
             // as successor is greater than left and lesser than right
       }
        /*
            This is to ensure that our delete fix-up private function gets called
        */
       if (y->isBlack && !bRoot)
       {
             if (x && x->parent)
                    vPrivDeleteFix(x->parent);
             else if (pNode->parent->parent)
                    vPrivDeleteFix(pNode->parent->parent);
             else
                    vPrivDeleteFix(pNode->parent);
       }

       delete (y);

       // Reset the root to NULL if indeed the real root node has been deleted:
       if (bRoot)
             root = NULL;

       return (true);
}
#endif
#endif
#endif
    return bDel;
}


void RedBlackTree::vPrivDeleteFix(Node *pNode)
{
    //Node *rootChild = root->left;
    Node *w; // pointer to allow us to find pNode's sibling which will take y's place in the tree
    while(((pNode != root)) && ((pNode!= NULL))&&((pNode->isBlack == true)))
    {
        if(pNode == pNode->parent->left)
        {
            w = pNode->parent->right;
            if((w!= NULL)&&(w->isBlack == false))// case 1
            {
                w->isBlack = true;
                pNode->parent->isBlack = false;
                LeftRotation(pNode->parent);
                w = pNode->parent->right;
            }
            if((w != NULL)&&(w->left->isBlack == true) && (w->right->isBlack == true))
            {
                w->isBlack = false;
                pNode = pNode->parent;
            }
            else
            {
                if((w != NULL)&&(w->right->isBlack == true))
                {
                    w->left->isBlack = true;
                    w->isBlack = false;
                    RightRotation(w);
                    w = pNode->parent->right;
                }
                if((w!= NULL) && (pNode->parent != NULL))
                {
                    w->isBlack = pNode->parent->isBlack;
                }
                if(pNode->parent != NULL)
                {
                    pNode->parent->isBlack = true;
                }
                if( (w != NULL) && (w->right != NULL))
                {
                    w->right->isBlack = true;
                }
                if(pNode->parent != NULL)
                {
                    LeftRotation(pNode->parent);
                }
                pNode = root;
            }
        }
        else
        {
            if(pNode == pNode->parent->right)
            {
                w = pNode->parent->left;
                if( (w!= NULL) && (w->isBlack == false))
                {
                    w->isBlack = true;
                    pNode->parent->isBlack = false;
                    if(pNode->parent != NULL)
                    {
                        RightRotation(pNode->parent);
                        w = pNode->parent->left;
                    }

                }
                if( (w != NULL) && (w->right->isBlack == true) && (w->left->isBlack == true))
                {
                    w->isBlack = false;
                    pNode = pNode->parent;
                }
                else
                {
                    if((w != NULL)&&(w->left->isBlack == true))
                    {
                        w->right->isBlack = true;
                        w->isBlack = false;
                        LeftRotation(w);
                        w = pNode->left;
                    }
                    if((w!= NULL) && (pNode->parent != NULL))
                    {
                        w->isBlack = pNode->parent->isBlack;
                    }
                    if(pNode->parent != NULL)
                    {
                        pNode->parent->isBlack = true;
                    }
                    if( (w != NULL) && (w->left != NULL))
                    {
                        w->left->isBlack = true;
                    }
                    if(pNode->parent != NULL)
                    {
                        RightRotation(pNode->parent);
                    }
                    pNode = root;
                }
            }
        }
    }
    if(pNode != NULL)
    {
        pNode->isBlack = true;
    }

}

void RedBlackTree::TransplantRB(Node *pNodeU, Node *pNodeV)
{
    if(pNodeU->parent == NULL)
    {
        root = pNodeV;
    }
    else if(pNodeU == pNodeU->parent->left)
    {
        pNodeU->parent->left = pNodeV;
    }
    else
    {
        pNodeU->parent->right = pNodeV;
    }
    if(pNodeV != NULL)
    {
        pNodeV->parent = pNodeU->parent;
    }

}

int RedBlackTree:: heightHelper(Node *pNode) const
{
    int iHeight = 0;
    if(pNode == NULL)
    {
        iHeight = 0;
    }
    else
    {
        iHeight = 1+ max(heightHelper(pNode->right),heightHelper(pNode->left));
    }
    return iHeight;
}

int RedBlackTree::sizeHelper(Node *pNode) const
{
    if(pNode == NULL)
    {
        return 0;
    }
    else
    {
        return (sizeHelper(pNode->left)+ sizeHelper(pNode->right))+1;
    }
}

int RedBlackTree::height() const
{
    return heightHelper(root);
}

int RedBlackTree::size() const
{
     return sizeHelper(root);
}

void RedBlackTree:: DeleteTreePrivate(Node* pNode)
{
    if(pNode != NULL)
    {
        DeleteTreePrivate(pNode->left);
        DeleteTreePrivate(pNode->right);
        delete pNode;
    }
    pNode = NULL;
}

void RedBlackTree::removeAll()
{
    DeleteTreePrivate(root);
}

Node *RedBlackTree::CloneTree(const Node* pTr)
{
    Node *pNewRB = NULL;
    if(pTr != NULL)
    {
        pNewRB = new Node(pTr->data,NULL,NULL, NULL,pTr->isBlack);
        pNewRB->left = CloneTree(pTr->left);
        pNewRB->right = CloneTree(pTr->right);

    }
    return pNewRB;

}

Node* RedBlackTree:: getRoot()
{
    return root;
}

int* RedBlackTree::dump(int& iSize)
{
    //int iStart = 0;
    return dumpPrivate(root,iSize);
}

int *RedBlackTree::dumpPrivate(Node *pNode, int& iSize)
{
    int iNumElements = size();
    int *pNewArr = new int[iNumElements];
    int iStart = 0;
    int iData = 0;
    if(pNode != NULL)
    {
        //iSize++;
        iStart++;
        dumpPrivate(pNode->left,iSize);
        //iData = pNode->data;
        // stuck on where to put the incrementer
        pNewArr[iSize] = pNode->data;
        iSize++;
        dumpPrivate(pNode->right,iSize);
        //iSize++;
    }

    return pNewArr;
}