include "stdafx.h"

#include

#include

#include

//line 21 updated and line 266 while loop removed.

using namespace std;

template

class AVL;

template

class AVLNode {

AVLNode* parent, *left, *right;

int height;

T data;

public:

friend class AVL < T >;

//~AVLNode();

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;

if (right != nullptr)

rightHeight = right->height;

height = max(leftHeight, rightHeight) + 1;

//return height;

}

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);

while (prev != nullptr) {

prev->calcHeight();

if (heightDiff(prev)>1)

doRotation(prev);

prev = prev->parent;

}

}

}

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

singleCCR(point);

}

}

template

int AVL::heightDiff(AVLNode* 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() {

{AVL b;

srand(time(NULL));

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

b.insert(rand() % 1000);

b.printInOrder();

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

}

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

}

Using the code for AVL tree, modify it to into red-black tree.Do not implement removals, just insertions. In C++