Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef CMPT225RBTREE
- /*
- CMPT 225 D2 Summer 2014 --- Assignment 4 (RedBlack Tree)
- Student: Echo Liu
- Professor: John Edgar
- Class: RedBlack Tree
- Description:
- Before we describe what a red black tree is we must go over briefly what a binary search tree is. A binary
- search tree or BST for short is a tree in which each node has at most two children with the left and right children having
- the following set of properties.
- 1. The children themselves are roots of their own subtrees
- 2. The left child and its associated subtree is less than the "main" root of the whole tree
- 3. The right child and its associated subtree is greater than the "main" root of the whole tree
- The order the keys inserted into the BST affect the shape of the tree, if the keys come in sorted order
- then the tree becomes anaemic closely resembling a linear chain of nodes forcing its performance to be O(n) instead of
- O(logn).
- A Red Black tree is a variation of a binary search tree in which preserves the logarithmic height of a binary search tree
- by colouring a node red or black and also imposing the following set of properties to make the tree approximately balanced.
- 1. No consecutive red nodes are allowed along any path.
- 2. The root is always black
- 3. Every red node has two black children
- 4. The amount of black nodes from the root to any descendent leaves on a simple path are equal, the root does
- not get factored into the calculation this calculation is the black height.
- 5. Consecutive black nodes along a path are allowed
- Prof: John Edgar
- */
- #include <iostream>
- #include <string>
- //#include "RedBlackTree.h"
- using namespace std;
- /*
- Start of Node constructors
- */
- /* This constructor takes a datum as its parameter and initializes its parent, left, and right pointer to the default NULL as well
- and isBlack to true false i.e red
- */
- template <class T>
- Node<T>::Node(T Tdata)
- {
- data = Tdata;
- parent = NULL;
- left = NULL;
- right = NULL;
- isBlack = false;
- }
- /*
- This constructor takes in a datum and three node pointers as its parameters. The
- three parameters represent left, right, and parent respectively and the default colour to red [false]
- */
- template <class T>
- Node<T>::Node(T Tdata, Node* pL, Node *pR, Node* pParent)
- {
- data = Tdata;
- parent = pParent;
- left = pL;
- right = pR;
- isBlack = false;
- }
- /*
- Node constructor that has four parameters
- that takes in a datum, three node pointers and a colour which is denoted by a boolean flag
- the three node pointers represent the values of the left, right, and parent pointer respectively
- */
- template <class T>
- Node<T>::Node(T Tdata, Node *pL, Node* pR, Node *pParent, bool bColour)
- {
- data = Tdata;
- parent = pParent;
- left = pL;
- right = pR;
- parent = pParent;
- isBlack = bColour;
- }
- /*
- C'tor that takes in four parameters
- a datum, node pointers representing left and right child respectively and a colour value by a boolean
- */
- template <class T>
- Node<T>::Node(T 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, initializing the root pointer to NULL
- and other private attributes to defaults
- */
- template <class T>
- RedBlackTree<T>::RedBlackTree()
- {
- root = NULL;
- aDumpData = NULL;
- iNodePos = 0;
- aDumpTemp = NULL;
- }
- /*
- RB Copy constructor which uses an internal helper function to make a deep copy of the tree
- */
- template <class T>
- RedBlackTree<T>::RedBlackTree(const RedBlackTree<T> &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
- */
- template <class T>
- RedBlackTree<T> & RedBlackTree<T>::operator=(const RedBlackTree<T> &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
- */
- template <class T>
- RedBlackTree<T>::~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 successful false if the client attempts to insert duplicate items into the tree
- pointer x determines point of insertion
- pointer y determines the node before x so we know where to wedge the node we want to insert
- */
- template <class T>
- bool RedBlackTree<T>::bInsert(Node<T>* pNode)
- {
- Node<T> *y = NULL;
- Node<T> *x = root;
- bool bIns = false; // return value
- bool bFound = false;
- // 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 counterparts
- 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 immediately 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
- Return type is void and the function does not return anything
- Parameter is a node pointer which represents the node we would like to insert
- */
- template <class T>
- void RedBlackTree<T>::vInsertFixViolation(Node<T> *pNode)
- {
- Node<T> *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 appropriate spot in the
- tree in which its node contains the appropriate 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 contained in, if it doesn't exist it simply returns NULL
- */
- template <class T>
- Node<T>* RedBlackTree<T>::pSearchPriv(T dataS, Node<T> *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.
- */
- template <class T>
- bool RedBlackTree<T>::search(T data) const
- {
- return bPrivSearch(data,root);
- }
- /*
- Follows the same structure as the other privateSearch function
- but returns a boolean instead
- takes in a datum to search for and a node pointer to start the recursion as parameters
- */
- template <class T>
- bool RedBlackTree<T>::bPrivSearch(T dataS, Node<T> *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 helper function that enables us to perform a left rotation
- takes in a Node pointer which indicates the node we are rotating about
- while maintaining the BST properties
- Return is none since the function is void
- */
- template <class T>
- void RedBlackTree<T>:: LeftRotation(Node<T> *pNode)
- {
- Node<T> *y = pNode->right; // y is pNode's right child
- pNode->right = y->left; // make y's left subtree into Pnode's right
- if(y->left != NULL)
- {
- y->left->parent = pNode;
- }
- y->parent = pNode->parent; // link the parent of y to pNode's
- if(pNode->parent == NULL) // special case if we are rotating about the root
- {
- root = y;
- }
- else
- {
- if(pNode == pNode->parent->left) // checking if pNode is a left or right child
- {
- pNode->parent->left = y;
- }
- else
- {
- pNode->parent->right = y;
- }
- }
- y->left = pNode; // reposition subtrees
- pNode->parent = y;
- }
- /*
- Private helper function that enables right rotations
- takes in a node pointer that indicates the node we perform the
- rotation about,
- Return type is void so function does not return anything
- */
- template <class T>
- void RedBlackTree<T>::RightRotation(Node<T> *pNode)
- {
- Node<T> *y = pNode->left; // y is pNode's left child
- pNode->left = y->right; // make pNode's left subtree become y's right
- if(y->right != NULL)
- {
- y->right->parent = pNode;
- }
- y->parent = pNode->parent;
- if(pNode->parent == NULL) // special case if pNode is the root
- {
- root = y;
- }
- else
- {
- if(pNode == pNode->parent->right) // checking if the node we want to rotate about is a right or left child
- {
- pNode->parent->right = y;
- }
- else
- {
- pNode->parent->left = y;
- }
- }
- /* repositioning subtrees */
- y->right = pNode;
- pNode->parent = y;
- }
- /*
- Private helper function that enables us to print the whole tree
- takes in a pointer to a node to indicate the start of the recursion
- return type is none since it is void
- */
- template <class T>
- void RedBlackTree<T>::PrintRecurse(Node<T> *pTr)
- {
- int i = 0;
- if(pTr != NULL)
- {
- //i++;
- PrintRecurse(pTr->left);
- std::cout << pTr->data << "";
- //i++;
- std::cout << "[" ;
- if(pTr->isBlack == true)
- {
- std::cout << "Black" << " ";
- }
- else
- {
- std::cout << "Red" << " ";
- }
- std::cout << "]";
- if(pTr->parent != NULL)
- {
- std::cout<< "(" << "parent is " << pTr->parent->data << ")" <<endl;
- }
- else
- {
- std::cout << endl;
- }
- PrintRecurse(pTr->right);
- //i++;
- }
- return;
- }
- /*
- Public print function that takes in no parameters and calls a private
- helper print function which starts its recursion from the root
- */
- template <class T>
- void RedBlackTree<T>::Print()
- {
- PrintRecurse(root);
- }
- /*
- Public insert function which takes a data that one wants to insert
- and calls a private helper function which takes a node allocated in dynamic memory as a parameter
- Returns a boolean
- */
- template <class T>
- bool RedBlackTree<T>::insert(T datum)
- {
- Node<T> *pNewNode = new Node<T>(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
- takes in a pointer to a node as a parameter to indicate the start of the recursion
- returns the minimum value in the subtree it was starting the recursion from
- */
- template <class T>
- Node<T>* RedBlackTree<T>::findMinPriv(Node<T> *pNode)
- {
- if(pNode == NULL)
- {
- return NULL;
- }
- if(pNode->left == NULL)
- {
- return pNode;
- }
- return findMinPriv(pNode->left);
- }
- /*
- Public function for debugging purposes,
- calls a private helper function so we can recursively
- search the left subtree for the appropriate node
- */
- template <class T>
- T RedBlackTree<T>::findMin()
- {
- Node<T> *pTr = findMinPriv(root);
- T iMin;
- if(pTr != NULL)// check if the pointer is NULL first since the tree can be empty
- {
- iMin = pTr->data;
- }
- return iMin;
- }
- /*
- Public function that takes in a datum that we would like to remove as a parameter
- returns false if the removal was unsuccessful or the datum is already there
- returns true if the removal was successful or the datum wasn't inserted previously
- calls a private helper function that does the removal
- */
- template <class T>
- bool RedBlackTree<T>::remove(T data)
- {
- bool bRmv = false;
- Node<T>* pNodetoRemove = pSearchPriv(data,root);
- if(pNodetoRemove!= NULL)
- bRmv = bRemove(pNodetoRemove);
- else
- {
- bRmv = false;
- }
- return bRmv;
- }
- /*
- Private helper function that enables us to reassign pointers as needed to remove the node
- while preserving the BST tree properties
- */
- template <class T>
- bool RedBlackTree<T>::bRemove(Node<T> *pNode)
- {
- Node<T> *y;
- Node<T> *x;
- bool bYOrigColour = false;
- bool bFound = false;// boolean flag indicating to us if the node is found or not
- bool bDel = false; // return value
- /* Checks if the node we would like to remove exists*/
- if ((pNode != NULL)&&(bPrivSearch(pNode->data,root) == true))
- {
- bDel = false;
- bFound = true;
- }
- // 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 contents
- // case that z has one or no children else z has two children
- y = ((pNode->left == NULL)) || ((pNode->right == NULL)) ?
- pNode:
- findMinPriv(pNode->right);
- // the node we want to remove
- x = (y->left != NULL)?
- y->left:
- y->right;
- // indicates point of insertion
- 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;
- return bDel;
- }
- /*
- Helper function that allows us to fix RB tree violations when deleting a node from a tree
- Eight cases to consider, the latter three are symmetrical:
- 1. The child of the node we want to remove [x] has a red sibling
- 2. The child of the node we want to remove has a sibling that is black and both of that sibling's children are black
- 3. The child of the node we want to remove has a sibling that is black, the sibling's left child is red, and the sibling's right child is black
- 4. The child of the node we want to remove has a black sibling and that sibling's right child is red.
- ================================================================================================================================================
- Symmetric cases:
- 5. The child of the node we want to remove [x] has a red sibling
- 6. The child of the node we want to remove has a sibling that is black and both of that sibling's children are black
- 7. The child of the node we want to remove has a sibling that is black, the sibling's right child is red, and the sibling's left child is black
- 8. The child of the node we want to remove has a black sibling and that sibling's left child is red.
- How to deal with case 1/[5]:
- Switch the colours of the sibling and x's parent then perform a left rotation about x's parent
- Case 1 can then be converted to case 2,3,4 or 6,7,8 depending on the shape of the tree
- How to deal with case 2/[6]:
- Both of the sibling's children are black. In addition that sibling node is also black so one can take a
- black off both the child of the node we want to remove. To compensate we add an extra black to the x's parent
- How to deal with case 3/[7]:
- We swap the colours of x's sibling and its left [right] child and then perform a right [left] rotation
- How to deal with case 4/[8]:
- Perform colour changes and a left [right] rotation
- Return type is none since the function is of type void parameter is a node pointer which represents
- the child of the node we want to remove
- */
- template <class T>
- void RedBlackTree<T>::vPrivDeleteFix(Node<T> *pNode)
- {
- //Node *rootChild = root->left;
- Node<T> *w; // pointer to allow us to find pNode's sibling which will take y's place in the tree
- while((pNode!= NULL)&&(pNode != root) && (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; // to exit while loop
- }
- }
- }
- }
- if(pNode != NULL)
- {
- pNode->isBlack = true;
- }
- }
- /*
- A private helper function that enables us to find the height of a binary search tree
- The function takes in a Node pointer which indicates the start of the recursion, the
- return type is an integer representing the height
- Logic is as follows:
- 1. if the node is Null then the tree has height zero.
- 2. else we employ the recursive definition of height to perform our desired calculation
- */
- template <class T>
- int RedBlackTree<T>:: heightHelper(Node<T> *pNode) const
- {
- int iHeight = 0;
- if(pNode == NULL)
- {
- iHeight = 0;
- }
- else
- {
- iHeight = 1+ max(heightHelper(pNode->right),heightHelper(pNode->left));
- }
- return iHeight;
- }
- /*
- Private helper that enables us to find the amount of nodes in a binary search tree
- Takes in a Node pointer as a parameter which indicates the start of the recursion
- the return type is the amount of nodes in both of the subtrees including the root
- */
- template <class T>
- int RedBlackTree<T>::sizeHelper(Node<T> *pNode) const
- {
- if(pNode == NULL)
- {
- return 0;
- }
- else
- {
- return (sizeHelper(pNode->left)+ sizeHelper(pNode->right))+1;
- }
- }
- /*
- Public function that enables us to find the height of a tree
- no parameters are taken and the return type is an integer value denoting
- the amount of nodes in the tree
- */
- template <class T>
- int RedBlackTree<T>::height() const
- {
- return heightHelper(root);
- }
- /*
- Public function that allows us to find the amount of nodes in the tree
- no parameters are taken and the return type is an integer value denoting the amount of
- nodes in the tree
- */
- template <class T>
- int RedBlackTree<T>::size() const
- {
- return sizeHelper(root);
- }
- /*
- Internal private function that takes in an node pointer in which to start the recursion so we clear all
- of the nodes in the binary search tree or any tree that contains two children, note we employ a post order traversal because
- we want to clear both the right and left subtrees before visiting the node. In addition, we set our node to NULL for good practice
- */
- template <class T>
- void RedBlackTree<T>:: DeleteTreePrivate(Node<T>* pNode)
- {
- if(pNode != NULL)
- {
- DeleteTreePrivate(pNode->left);
- DeleteTreePrivate(pNode->right);
- delete pNode;
- }
- pNode = NULL;
- }
- /*
- Public remove function that allows us to deallocate all of the nodes in the binary search tree
- takes in no parameters and doesn't return anything
- Calls a private helper function that deletes all of the nodes of the tree with the recursion starting at the root
- */
- template <class T>
- void RedBlackTree<T>::removeAll()
- {
- if (root)
- {
- DeleteTreePrivate(root);
- root = NULL;
- }
- }
- /*
- Private helper function that enables us to deep copy the binary search tree
- */
- template <class T>
- Node<T> *RedBlackTree<T>::CloneTree(const Node<T>* pTr)
- {
- Node<T> *pNewRB = NULL;
- if(pTr != NULL)
- {
- //pNewRB = new Node<T>(pTr->data,NULL,NULL, NULL,pTr->isBlack); >> this piece was used for debugging purposes
- pNewRB = new Node<T>(pTr->data,pTr->left,pTr->right, pTr->parent,pTr->isBlack);
- pNewRB->left = CloneTree(pTr->left);
- pNewRB->right = CloneTree(pTr->right);
- }
- return pNewRB;
- }
- /*
- This function takes in no parameters and returns the root as a NODE POINTER!
- */
- template <class T>
- Node<T>* RedBlackTree<T>:: getRoot()
- {
- return root;
- }
- /*
- The dump function takes in an integer reference parameter that returns the total amount of items in the array
- The function returns an array in dynamic memory
- */
- template <class T>
- T* RedBlackTree<T>::dump(int& iSize)
- {
- //int iStart = 0;
- iSize = size();
- int iPosi = 0;
- iNodePos = 0;
- if(iSize > 0)
- {
- aDumpData = new T[iSize];
- dumpPrivate(root,iPosi);
- }
- return aDumpData;
- }
- /*
- This helper function takes in two parameters, a pointer to a node in which to start the recursion
- and an integer reference parameter to check if we incremented our index correctly 'i.e iNodePos
- */
- template <class T>
- void RedBlackTree<T>::dumpPrivate(Node<T> *pNode,int &iPos)
- {
- if(pNode != NULL)
- {
- dumpPrivate(pNode->left,iPos);
- aDumpData[iNodePos] = pNode->data;
- iNodePos++;
- dumpPrivate(pNode->right,iPos);
- }
- }
- /*
- Ok we must admit, we are making a risky assumption that our first parameter is less than our second parameter however in practice
- we are probably going to have to switch that around.
- The function takes the following parameters:
- two values that represent the range that the user is looking for
- an integer reference parameter that denotes the amount of items in the returned array
- Returns a pointer to an array in dynamic memory
- If there are no values between the first and second parameters the function returns NULL
- i.e search(15,19,n) returns NULL if the array looks like this
- [1,5,11,13,14,21,25,30,63]
- If the first parameter equals second parameter and that particular value is in the tree then the function should return that value
- i.e search(0,0,n) should return 0 if the array looks like this
- [0.33.99]
- but returns NULL if the array looks like this
- [33,99]
- If the tree is empty it should return NULL
- */
- template <class T>
- T *RedBlackTree<T>::search(T firstParem, T secondParem, int &iNumElements)
- {
- iNumElements = size();
- int iLocIndex = 0;
- T *aDumpBetweenValues = NULL;
- iNodePos = 0;
- firstvalue = firstParem;
- secondvalue = secondParem;
- if(iNumElements > 0) // checks if the tree is empty
- {
- aDumpTemp = new T[iNumElements]; // allocates enough memory for all of the nodes in the tree
- searchPrivate(root,iLocIndex);// helper function to search the tree for the datums in the requested bounds
- if(iLocIndex > 0)// checks if there are any values in between the two parameters
- {
- aDumpBetweenValues = new T[iLocIndex]; // allocates enough memory for all of the values that are between parameter 1 and parameter 2
- // we use a local memory allocation so we don't have to worry about that memory block used by a previous search call
- // copies the values yielded from searchPrivate over to the memory allocated just enough for all of the values in
- // between the bounds
- for(int i = 0;i<iLocIndex;i++)
- {
- aDumpBetweenValues[i] = aDumpTemp[i];
- }
- // we set our iNumElements integer parameter to the amount of values that are in between our bounds
- iNumElements = iLocIndex;
- }
- else
- {
- iNumElements = 0;
- }
- if(aDumpTemp!= NULL)
- {
- delete [] aDumpTemp;
- aDumpTemp = NULL;
- }
- }
- else
- {
- iNumElements = 0;
- }
- return aDumpBetweenValues;
- }
- /*
- Helper function that will allow us to search the left and right subtrees
- Parameters are a pointer to a node that will enable us to start the recursion and an integer reference parameter
- to keep track the amount of items inserted into the array
- */
- template <class T>
- void RedBlackTree<T>::searchPrivate(Node<T>*pTr1, int &iNdex)
- {
- // base case
- if(pTr1 == NULL)
- {
- return;
- }
- /*If the current value we are looking at is greater than the first value in the range
- that we are looking for we keep on traversing the left subtree
- */
- if(firstvalue < pTr1->data)
- {
- searchPrivate(pTr1->left,iNdex);
- }
- /*
- If the value we are looking for is indeed in the range we push its appropriate datum into the associated
- index in the array.
- */
- if( firstvalue <= pTr1->data && secondvalue >= pTr1->data)
- {
- aDumpTemp[iNdex] = pTr1->data;
- iNdex++;
- }
- /*
- If the current node with its associated datum is less than the datum in the second value of our interval
- then we keep on recursively going down its right subtree
- */
- if(secondvalue > pTr1->data)
- {
- searchPrivate(pTr1->right,iNdex);
- }
- }
- #endif
Add Comment
Please, Sign In to add comment