Red Black Tree implementation trouble

[dwrib]

Hi,

Sorry in advance for the formatting.. I was unable to figure out how to make it show up as code in this post.
I'm working on a project where the assignment is to take code provided to me for an AVL tree and turn it into a red/black tree. I have attempted this, but I'm not having luck completing it. I believe that the issue comes when I attempt to do the rotations in the 'doRotation' function. Below is the code I'm working on:


<
#include <iostream>
#include <ctime>
#include <algorithm>
//line 21 updated and line 266 while loop removed.
using namespace std;

const char RED = 'r';
const char BLACK = 'b';

template <class T>
class RBT;

template <class T>
class RBTNode {
RBTNode<T>* parent = NULL;
RBTNode<T>* left = NULL;
RBTNode<T>* right = NULL;
char color = RED;
T data;
public:
friend class RBT <T>;

RBTNode(const T& newdata = T(), RBTNode<T>* newparent = nullptr, RBTNode<T>* newleft = nullptr, RBTNode<T>* newright = nullptr, char newColor = RED) :
data(newdata), parent(newparent), left(newleft), right(newright), color(newColor) {};
void printInOrder()const {
if (left != nullptr)
left->printInOrder();
cout << data << endl;
if (right != nullptr)
right->printInOrder();
}
int size()const {
int leftSize = 0;
int rightSize = 0;
if (left != nullptr)
leftSize = left->size();
if (right != nullptr)
rightSize = right->size();
return 1 + leftSize + rightSize;
}
int depth() const {
int parentDepth = -1;
if (parent != nullptr)
parentDepth = parent->depth();
return 1 + parentDepth;
}
};

template <class T>
class RBT {
RBTNode<T>* root;
int size;
RBTNode<T>* recursiveCopy(RBTNode<T>* toCopy);
void singleCCR(RBTNode<T>*& point);
void doubleCR(RBTNode<T>*& point);
void singleCR(RBTNode<T>*& point);
void doubleCCR(RBTNode<T>*& point);
int heightDiff(RBTNode<T>* point);
void doRotation(RBTNode<T>* point, const bool &isLeft);
public:
RBT() :size(0) { root = nullptr; }

//memory on the heap so.... here comes the big 3!
RBT(const RBT<T>& rhs) :root(nullptr) { *this = rhs; }
//virtual ~RBT() { clear(); }
//since we were told not to worry about deletion
RBT& operator=(const RBT<T>& rhs);

bool isInTree(const T& toFind) const { return find(toFind) != nullptr; }
bool isEmpty()const { return root == nullptr; }
int getSize()const { return size; }
void insert(const T&);
RBTNode<T>* find(const T& toFind) const;
void printInOrder()const { root->printInOrder(); }
bool isBlack(T data) {return data -> color == BLACK;}
};
template <class T>
void RBT<T>::doubleCCR(RBTNode<T>*& point) {
singleCR(point->right);
singleCCR(point);
}

template <class T>
void RBT<T>::doubleCR(RBTNode<T>*& point) {
singleCCR(point->left);
singleCR(point);
}

template <class T>
void RBT<T>::singleCR(RBTNode<T>*& point) {
RBTNode<T>* grandparent = point -> parent -> parent;
RBTNode<T>* parent = point->parent;


parent->parent = grandparent->parent;
grandparent->parent = parent;
grandparent->left = parent->right;
parent->right = grandparent;
if (grandparent->left != nullptr) //if we now have a left child, update its parent pointer
grandparent->left->parent = grandparent;
if (parent->parent == nullptr)//if we were the root, update the root!
root = parent;
else if (parent->parent->left == grandparent)
parent->parent->left = parent;
else
parent->parent->right = parent;
}

template <class T>
void RBT<T>::singleCCR(RBTNode<T>*& point) {
RBTNode<T>* grandparent = point;
RBTNode<T>* parent = point->right;
parent->parent = grandparent->parent;
grandparent->parent = parent;
grandparent->right = parent->left;
parent->left = grandparent;
if (grandparent->right != nullptr) //if we now have a right child, update its parent pointer
grandparent->right->parent = grandparent;
if (parent->parent == nullptr)//if we were the root, update the root!
root = parent;
else if (parent->parent->right == grandparent)
parent->parent->right = parent;
else
parent->parent->left = parent;
}


template <class T>
RBTNode<T>* RBT<T>::recursiveCopy(RBTNode<T>* toCopy) {
if (toCopy == nullptr)
return nullptr;
RBTNode<T>* temp = new RBTNode<T>(toCopy->data, nullptr, recursiveCopy(toCopy->left), recursiveCopy(toCopy->right));
if (temp->left != nullptr)
temp->left->parent = temp;
if (temp->right != nullptr)
temp->right->parent = temp;
return temp;
}

template <class T>
RBTNode<T>* RBT<T>::find(const T& toFind) const {
RBTNode<T>* temp = root;
while (temp != nullptr && temp->data != toFind) {
if (toFind < temp->data)
temp = temp->left;
else
temp = temp->right;
}
return temp;
}

template <class T>
void RBT<T>::insert(const T& toInsert) {

bool isLeft;

size++;
if (root == nullptr) {
root = new RBTNode<T>(toInsert);
root -> parent = NULL;
root -> left = NULL;
root -> right = NULL;
}
else {
RBTNode<T>* temp = root;
RBTNode<T>* prev = temp;
while (temp != nullptr) {
prev = temp;
if (toInsert < temp->data)
temp = temp->left;
else
temp = temp->right;
}
//now temp points to null and prev points to the node we want to insert onto
if (toInsert < prev->data) { //insert onto the left of Prev
prev->left = new RBTNode<T>(toInsert, prev);
isLeft = true;
}
else {
prev->right = new RBTNode<T>(toInsert, prev);
isLeft = false;
}

while (prev != NULL) {
if (prev -> color == RED) {
doRotation(prev, isLeft);
}
prev = prev->parent;
}
}
root -> color = BLACK;
}
template <class T>
void RBT<T>::doRotation(RBTNode<T>* point, const bool &isLeft) {

RBTNode<T>* uncleOfNewNode, *grandparentOfNewNode, *parentOfNewNode;

parentOfNewNode = point;

if (parentOfNewNode -> parent != root) {
grandparentOfNewNode = parentOfNewNode -> parent;
}
else {
grandparentOfNewNode = NULL;
}

if (grandparentOfNewNode != NULL) {
if (grandparentOfNewNode -> right != NULL) {
uncleOfNewNode = grandparentOfNewNode -> right;
}
else if (grandparentOfNewNode -> left != NULL) {
uncleOfNewNode = grandparentOfNewNode -> left;
}
else {
uncleOfNewNode = NULL;
}

if (parentOfNewNode -> color == RED && uncleOfNewNode -> color == RED) { //node, parent, and uncle are all red. Push black down from grandparent so parent and uncle are black
uncleOfNewNode -> color = BLACK;
parentOfNewNode -> color = BLACK;
}
else if (grandparentOfNewNode -> left == parentOfNewNode) { //clockwise, but how many?
if (isLeft == true) { //node is left child and parent is left
singleCR(point);
}
else if (isLeft == false) { //node is right child and parent is left
doubleCR(point);
}
}
else if (grandparentOfNewNode -> right == parentOfNewNode) { //counter-clockwise, but how many?
if (isLeft == false) { //node is right child and parent is right
singleCCR(point);
}
else if (isLeft == true) { //node is left child and parent is right
doubleCCR(point);
}
}
}
}


template<class T>
int RBT<T>::heightDiff(RBTNode<T>* point) {
int leftHeight = 0;
int rightHeight = 0;
if (point->left != nullptr)
leftHeight = point->left->height;
if (point->right != nullptr)
rightHeight = point->right->height;
return (abs(leftHeight - rightHeight));
}


int main() {
{RBT<int> b;

srand((int)time(NULL));
for (int i = 0; i < 1000; i++)
b.insert(rand() % 1000);

b.printInOrder();
cout << "Got here!" << endl;
}
cout << "Got here #2" << endl;
}
>