RedBlackTree.h

#ifndef CMPT225RBTREE
#define CMPT225RBTREE

#include <iostream>
#include <string>

/*
    The node class contains the following attributes
        a data attribute
        a left child pointer
        a right child pointer
        a pointer to its parent
        a boolean flag representing the colour bit, if the boolean is true then the node is
        black and
        if it is false
        the node is red
*/
template <class T>
class Node
{
    public:
        T data;
        Node *left;
        Node *right;
        Node *parent;
        bool isBlack;
        // Node constructors
        //Node();
        Node(T data);
        Node(T data, Node* pL, Node *pR, Node* pParent);
        Node(T data, Node *pL, Node* pR, Node *pParent, bool bColour);
        Node(T data, Node *pL, Node* pR, bool bColour);

};
/*
    Red Black tree class interface
*/
template <class T>
class RedBlackTree
{
    public:
        /*
            Constructor, copy C'tor, D'tor, and overloaded assignment operator
        */
        RedBlackTree();
        RedBlackTree(const RedBlackTree<T> &rhs);
        ~RedBlackTree();
        RedBlackTree & operator=(const RedBlackTree<T> &rhs);
        // searches if a particular datum exists in the tree
        bool search(T data) const;
        // inserts and removes datums from the tree checking if the node we want to insert is already there or not
        // and if the node we want to remove exists
        bool insert(T data);
        bool remove(T data);
        // finds the values between the specified bounds and returns an array countaining those values with an
        // integer reference parameter denoting the size of the returned array
        T *search(T firstParem, T secondParem, int &iNumElements);
        // clears all of the values in the tree
        void removeAll();
        // returns an array containing all of the datums in the tree
        T *dump(int& iSize);
        // returns amount of nodes in the tree
        int size() const;
        // returns height of the tree
        int height() const;
        // returns a pointer to the root of the tree
        Node<T> *getRoot();
        // allows us to print the tree so we can see if our remove/insert methods are working as we expected
        void Print();
        // finds the minimum of the tree
        T findMin();


    private:
        Node<T> *root;
        // member variables that will enable us to perform memory allocations for dump and search
        T *aDumpData;
        T *aDumpTemp;
        // member variables for second search function to store the values for the first and second parameters respectively
        // so we can perform the comparison when we recursively call the associated helper function that gets called by the
        // public search function with the parameters and return value as follows T*search( T fval, T secondval, int &n);
        T firstvalue;
        T secondvalue;
        int iNodePos; // keeps track of index book keeping for dump function

        //int &iaPos;
        // private helper function to determine if the value we are searching for exists or not
        void PrintRecurse(Node<T> *pTr);
        bool bPrivSearch(T data, Node<T> *pTr) const;
        // helper function that will allow us find the pointer to a node that we are looking for
        Node<T> *pSearchPriv(T data, Node<T> *pTr);
        // Private helper that clones all of the nodes
        Node<T> *CloneTree(const Node<T>* pTr);
        // an internal helper function that will allow us to pass in a newly allocated node with the client's requested datum as the node's data
        bool bInsert(Node<T>* pNode);

    private:
        // private remove function that gets called by its public counterpart
        bool bRemove(Node<T> *pNode);
    private:
        // Helper function that fixes violations when deleting a node from the  tree
        void vPrivDeleteFix(Node<T> *pNode);
        // Helper function to fix any RB tree violations that we may encounter in inserting the node in the tree
        void vInsertFixViolation(Node<T> *pNode);
        // Rotation helper methods
        void LeftRotation(Node<T> *pNode);
        void RightRotation(Node<T> *pNode);
        // helper function to deallocate memory from the tree
        void DeleteTreePrivate(Node<T>* pNode);
        // helper to allow us to find the successor node
        Node<T> * findMinPriv(Node<T>* pNode);
        // helper function to help us find the height of the tree
        int heightHelper(Node<T> *pNode) const;
        // helper function to help us to find the amount of nodes in the tree
        int sizeHelper(Node<T> *pNode) const;
        // Helper function that gets called by our public dump function to return an array containing all of the nodes in the tree
        void dumpPrivate(Node<T> *pNode,int &iPos);
        // Helper function that gets called by our public searching the values between the bounds function to return an array containing those items
        // works by recursively searching the left and right subtrees with extra constraints
        void searchPrivate(Node<T>*pTr1, int &iNdex);

};
#include "RedBlackTree.cpp"
#endif