Using the code for the AVL tree, below, Create a class, RBT, which implements a red black tree. You DO NOT need to implement removals.

#include

#include

using namespace std;

template

class AVL;

template

T& max(T& left, T& right){

if (left > right)

return left;

else

return right;

}

template

T max(const T& left, const T& right){

if (left > right)

return left;

else

return right;

}

template

class AVLNode{

AVLNode* parent, *left, *right;

int height;

T data;

public:

friend class AVL < T >;

AVLNode(const T& newdata = T(), AVLNode* newparent = nullptr, AVLNode* newleft = nullptr, AVLNode* newright = nullptr) :

data(newdata), parent(newparent), left(newleft), right(newright) { calcHeight(); }

void calcHeight(){

int leftHeight = -1;

int rightHeight = -1;

if (left != nullptr)

leftHeight = left->height + 1;

if (right != nullptr)

rightHeight = right->height + 1;

height = max(leftHeight, rightHeight) + 1;

}

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 height()const{

int leftSize = -1;

int rightSize = -1;

if (left != nullptr)

leftSize = left->height();

if (right != nullptr)

rightSize = right->height();

return 1 + max(leftSize, rightSize);

}*/

int depth() const{

int parentDepth = -1;

if (parent != nullptr)

parentDepth = parent->depth();

return 1 + parentDepth;

}

};

template

class AVL{

AVLNode* root;

int size;

AVLNode* recursiveCopy(AVLNode* toCopy);

void singleCCR(AVLNode*& point);

void doubleCR(AVLNode*& point);

void singleCR(AVLNode*& point);

void doubleCCR(AVLNode*& point);

int heightDiff(AVLNode* point);

void doRotation(AVLNode* point);

public:

AVL() :size(0){ root = nullptr; }

//memory on the heap so.... here comes the big 3!

AVL(const AVL& rhs) :root(nullptr){ *this = rhs; }

virtual ~AVL(){ clear(); }

AVL& operator=(const AVL& rhs);

bool isInTree(const T& toFind) const{ return find(toFind) != nullptr; }

bool isEmpty()const{ return root == nullptr; }

int getSize()const { return size; }

void remove(const T& toRemove){

AVLNode* item = find(toRemove);

if (item != nullptr)

remove(item);

}

void insert(const T&);

void remove(AVLNode*);

AVLNode* find(const T& toFind) const;

void clear(){ while (!isEmpty()) remove(root); }

void printInOrder()const{ root->printInOrder(); }

};

template

void AVL::doubleCCR(AVLNode*& point){

singleCR(point->right);

singleCCR(point);

}

template

void AVL::doubleCR(AVLNode*& point){

singleCCR(point->left);

singleCR(point);

}

template

void AVL::singleCR(AVLNode*& point){

AVLNode* grandparent = point;

AVLNode* parent = point->left;

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;

grandparent->calcHeight();

parent->calcHeight();

}

template

void AVL::singleCCR(AVLNode*& point){

AVLNode* grandparent = point;

AVLNode* 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;

grandparent->calcHeight();

parent->calcHeight();

}

template

AVLNode* AVL::recursiveCopy(AVLNode* toCopy){

if (toCopy == nullptr)

return nullptr;

AVLNode* temp = new AVLNode(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

AVL& AVL::operator=(const AVL& rhs){

if (this == &rhs)

return *this;

clear();

root = recursiveCopy(rhs.root);

size = rhs.size;

return *this;

}

template

void AVL::remove(AVLNode* toRemove){

if (root == nullptr)

return; //Remove from an empty tree????

if (toRemove->left == nullptr && toRemove->right == nullptr){ //leaf node case

if (toRemove->parent == nullptr){

root = nullptr;

}

else if (toRemove == toRemove->parent->left) //left child!

toRemove->parent->left = nullptr; //fix the parent's pointer!

else

toRemove->parent->right = nullptr;

delete toRemove;

size--;

}

else if (toRemove->right == nullptr){ //has one (left) child

if (toRemove->parent == nullptr){

root = toRemove->left;

root->parent = nullptr;

}

else if (toRemove == toRemove->parent->left){ //we're the left child of our parent

toRemove->parent->left = toRemove->left;

toRemove->left->parent = toRemove->parent;

}

else{

toRemove->parent->right = toRemove->left;

toRemove->left->parent = toRemove->parent;

}

delete toRemove;

size--;

}

else if (toRemove->left == nullptr){ //has one right child, almost same solution as left child only

if (toRemove->parent == nullptr){

root = toRemove->right;

root->parent = nullptr;

}

else if (toRemove == toRemove->parent->left){ //we're the left child of our parent

toRemove->parent->left = toRemove->right;

toRemove->right->parent = toRemove->parent;

}

else{

toRemove->parent->right = toRemove->right;

toRemove->right->parent = toRemove->parent;

}

delete toRemove;

size--;

}

else{ //sigh... two children!

AVLNode* temp = toRemove->right;

while (temp->left != nullptr)

temp = temp->left;

toRemove->data = temp->data;

remove(temp);

}

}

template

AVLNode* AVL::find(const T& toFind) const{

AVLNode* temp = root;

while (temp != nullptr && temp->data != toFind){

if (toFind < temp->data)

temp = temp->left;

else

temp = temp->right;

}

return temp;

}

template

void AVL::insert(const T& toInsert){

size++;

if (root == nullptr){

root = new AVLNode(toInsert);

}

else{

AVLNode* temp = root;

AVLNode* 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 AVLNode(toInsert, prev);

}

else

prev->right = new AVLNode(toInsert, prev);

if(prev != nullptr){

prev->calcHeight();

if (heightDiff(prev)>1)

doRotation(prev);

}

}

}

template

void AVL::doRotation(AVLNode* point){

int leftChild = -1;

int rightChild = -1;

if (point->left != nullptr)

leftChild = point->left->height;

if (point->right != nullptr)

rightChild = point->right->height;

if (leftChild > rightChild){//CR, but is it single or double?

int leftGC = -1;

int rightGC = -1;

if (point->left->left != nullptr)

leftGC = point->left->left->height;

if (point->left->right != nullptr)

rightGC = point->left->right->height;

if (leftGC > rightGC) // single rotation

singleCR(point);

else

doubleCR(point);

}

else{//definitely a CCR, but which one?

int leftGC = -1;

int rightGC = -1;

if (point->right->left != nullptr)

leftGC = point->right->left->height;

if (point->right->right != nullptr)

rightGC = point->right->right->height;

if (leftGC > rightGC) // double rotation

doubleCCR(point);

else

singleCR(point);

}

}

template

int AVL::heightDiff(AVLNode* point){

int leftHeight = -1;

int rightHeight = -1;

if (point->left != nullptr)

leftHeight = point->left->height;

if (point->right != nullptr)

rightHeight = point->right->height;

return (abs(leftHeight - rightHeight));

}

int main(){

{

AVL b;

srand(time(NULL));

for (int i = 0; i < 100; i++)

b.insert(rand() % 1000);

b.printInOrder();

cout << "Got here!" << endl;

}

cout << "Got here #2" << endl;

}