Please fill in the CODE HERE parts #ifndef AVLTREE_H #define AVLTREE_H #include
ID: 3912987 • Letter: P
Question
Please fill in the CODE HERE parts
#ifndef AVLTREE_H
#define AVLTREE_H
#include "Data.h"
template
class AVLTree {
private:
struct AVLNode {
AVLNode* leftChild;
AVLNode* rightChild;
T* data;
int duplicates; // used if there are duplicate values in the tree
// instead of changing rotation rules
int height;
AVLNode () : // default constructor
leftChild {nullptr},
rightChild {nullptr},
data {nullptr},
duplicates {0},
height {0} {};
~AVLNode () = default;
AVLNode (T& value) :
leftChild {nullptr},
rightChild {nullptr},
duplicates {0},
height {0} {
data = new T{value};
};
AVLNode (T&& value):
leftChild {nullptr},
rightChild {nullptr},
duplicates {0},
height {0} {
data = new T{value};
}
AVLNode (T& value, AVLNode* left, AVLNode* right) :
leftChild {left},
rightChild {right},
duplicates {0},
height {0} {
data = new T{value};
};
AVLNode (T&& value, AVLNode* left, AVLNode* right) :
leftChild {left},
rightChild {right},
duplicates {0},
height {0} {
data = new T{value};
}
};
AVLNode* root;
// mutators ------------------------------------------------------------
// inserts a new value into the given subtree with node as the root.
// If the value already exists, just incrememnt the duplicates counter.
// Else, create memory for it and place pointers appropriately.
// Must use recursion.
void insert(T& value, AVLNode* & node){
// CODE HERE
}
// will balance the tree with node as the offending root, like
// alpha in our class discussions. Should call onf of the rotate functions.
// Don't forget to set the height at the end!
void balance(AVLNode* & node){
// CODE HERE
}
// Rotate binary tree node with left child, i.e. a single rotation
// for case 1. Update the heights, and set new root.
void rotateLeft(AVLNode*& node){
// CODE HERE
}
// Rotate binary tree node with right child, i.e. a single rotation
// for case 4. Update the heights, and set new root.
void rotateRight(AVLNode*& node){
// CODE HERE
}
// Double rotate binary tree node: first left child with its right
// child, then subroot with its new left child (was grandchild previously).
// I.e. rotation case 2. Update the heights, and set new root.
void rotateDoubleLeft(AVLNode*& node){
// CODE HERE
}
// Double rotate binary tree node: first left child with its right
// child, then subroot with its new left child (was grandchild previously).
// I.e. rotation case 2. Update the heights, and set new root.
void rotateDoubleRight(AVLNode*& node){
// CODE HERE
}
// removes a given value from the tree. If the Node containing the value
// has duplicates, decrement the duplicates. Else deallocate the memory and
// recursively call remove to fix the tree, as discussed in class.
void remove(T& value, AVLNode*& node){
// CODE HERE
}
// private function to recursively empty
void empty(AVLNode* node){
// CODE HERE
}
//Data.h---------------------------------
#ifndef DATA_H
#define DATA_H
#include
class DoubleData {
private:
double* data;
public:
DoubleData();
DoubleData(double a);
~DoubleData() = default;
// accessors -------------------------------
double getData() const ;
double compare(DoubleData& other) const;
friend std::ostream& operator<<(std::ostream& os, const DoubleData& dd);
// mutators --------------------------------
void setData(double _data);
};
#endif
Explanation / Answer
main.cpp
#include <iostream>
#include <string>
#include <cassert>
#include <vector>
// local includes
#include "AVLTree.h"
#include "Data.h"
using namespace std;
void testDoubleData(){
// testing getData
DoubleData d1 {};
DoubleData d2 {5};
assert (d1.getData() == 0); // default value
assert (d2.getData() == 5); // testing 1-arg constructor
DoubleData d3 {d2};
assert (d3.getData() == 5); // testing copy constructor
DoubleData d4 {*(new DoubleData(3))};
assert (d4.getData() == 3); // testing move constructor
// testing setData
double y = 7.5;
d1.setData(y);
assert (d1.getData() == 7.5);
d1.setData(8.5);
assert (d1.getData() == 8.5);
// testing compare, should be a.compare(b) = a-b
assert (d1.compare(d2) == 3.5);
}
void testAVLTree(){
AVLTree<DoubleData> a {};
std::vector<DoubleData*> v {5, new DoubleData{}};
assert (a.getHeight() == 0 || a.getHeight() == -1);
double counter = 0;
std::cout << "testing insertion and single rotation cases: " << std::endl;
for (auto& x : v){
x = new DoubleData(counter);
a.insert(*x);
/* These test all the single rotations */
if (counter == 1) {assert(a.getHeight() == 1);}
if (counter == 2) {assert(a.getHeight() == 1);}
if (counter == 3) {assert(a.getHeight() == 2);}
if (counter == 4) {assert(a.getHeight() == 2);}
counter++;
}
std::cout << std::endl;
std::cout << "testing double rotation cases: " << std::endl;
a.insert(DoubleData(2.5));
assert(a.getHeight() == 2);
a.insert(DoubleData(3.5));
a.insert(DoubleData(1.5));
a.insert(DoubleData(1.2));
a.insert(DoubleData(1.7));
a.insert(DoubleData(-1));
a.insert(DoubleData(0.5));
a.insert(DoubleData(1.3));
a.insert(DoubleData(1.1));
a.insert(DoubleData(1.6));
a.insert(DoubleData(-2));
a.insert(DoubleData(1.05));
assert(a.getHeight() == 4);
std::cout << std::endl;
std::cout<<"testing traversals:"<<std::endl;
a.printPreorder();
a.printInorder();
a.printPostorder();
a.printLevelOrder();
std::cout << std::endl;
std::cout << "removing 2.5:" << std::endl;
a.remove(DoubleData(2.5));
a.printLevelOrder();
std::cout << std::endl;
std::cout << "removing 1.5:" << std::endl;
a.remove(DoubleData(1.5));
a.printPostorder();
std::cout << std::endl;
// // testing copy constructor
AVLTree<DoubleData> b {a};
cout << "should be same:" << endl;
a.printPostorder();
b.printPostorder();
std::cout << std::endl;
a.empty();
cout << "should be empty now:" << endl;
assert (a.getHeight() == -1 || // a null tree can have height -1 or 0,
a.getHeight() == 0); // which is subject to preference and usage
a.printPostorder();
std::cout << "end of test"<< std::endl;
}
int main (int argc, char* argv []){
testDoubleData();
testAVLTree();
std::cout << "end of main"<< std::endl;
}
Data.cpp
#include "Data.h"
// constructors / destructor
DoubleData::DoubleData():
data {nullptr} {};
DoubleData::DoubleData(double a){
data = new double(a);
}
// accessors -------------------------------
double DoubleData::getData() const {
if (this && this->data){
return *this->data;
} else {
return 0;
}
}
// returns positive number if *this->data is greater than *other.data
double DoubleData::compare(DoubleData& other) const {
// avoids segfaults by calling getData()
return (getData() - other.getData());
}
std::ostream& operator<<(std::ostream& os, const DoubleData& dd) {
if (dd.data){
os << *(dd.data);
} else {
os << "";
}
return os;
}
// mutators --------------------------------
void DoubleData::setData(double _data) {
if (data){
*data = _data;
} else {
data = new double(_data);
}
}
Data.h
#ifndef DATA_H
#define DATA_H
#include <iostream>
class DoubleData {
private:
double* data;
public:
DoubleData();
DoubleData(double a);
~DoubleData() = default;
// accessors -------------------------------
double getData() const ;
double compare(DoubleData& other) const;
friend std::ostream& operator<<(std::ostream& os, const DoubleData& dd);
// mutators --------------------------------
void setData(double _data);
};
#endif
AVLTree.cpp
#include "AVLTree.h"
// empty because AVLTree is a template class -------
AVLTree.h
#ifndef AVLTREE_H
#define AVLTREE_H
#include "Data.h"
#include <queue>
template <typename T>
class AVLTree {
private:
struct AVLNode {
AVLNode* leftChild;
AVLNode* rightChild;
T* data;
int duplicates; // used if there are duplicate values in the tree
// instead of changing rotation rules
int height;
AVLNode () : // default constructor
leftChild {nullptr},
rightChild {nullptr},
data {nullptr},
duplicates {0},
height {0} {};
~AVLNode () = default;
AVLNode (T& value) :
leftChild {nullptr},
rightChild {nullptr},
duplicates {0},
height {0} {
data = new T{value};
};
AVLNode (T&& value):
leftChild {nullptr},
rightChild {nullptr},
duplicates {0},
height {0} {
data = new T{value};
}
AVLNode (T& value, AVLNode* left, AVLNode* right) :
leftChild {left},
rightChild {right},
duplicates {0},
height {0} {
data = new T{value};
};
AVLNode (T&& value, AVLNode* left, AVLNode* right) :
leftChild {left},
rightChild {right},
duplicates {0},
height {0} {
data = new T{value};
}
};
AVLNode* root;
int getHeight(AVLNode* node) const {
// CODE HERE
if (node == nullptr) return -1;
return 1 + std::max(getHeight(node->leftChild), getHeight(node->rightChild));
//return 0; // PLACEHOLDER FOR COMPILATION
}
// returns the depth from the current subtree (node is subroot)
// must use recursion.
int getDepthAux(const T& value, AVLNode* node) const {
// CODE HERE
if (node == nullptr) return -1;
if (node != nullptr && *node->data == value) return 0;
if (getDepthAux(value, node->leftChild) >= 0) {
return 1+getDepthAux(value, node->leftChild);
} else {
return 1+getDepthAux(value, node->rightChild);
}
//return 0; // PLACEHOLDER
}
int getDepth(const T& value, AVLNode* node) const {
if (!findNode(value, node)){
return -1; // return -1 if node does not exist in tree
} else {
return getDepthAux(value, node);
}
}
AVLNode* findNode(const T& value, AVLNode* node) const {
// CODE HERE
if (node == nullptr) return nullptr;
if (*node->data == value) return node;
AVLNode *ret = findNode(value, node->leftChild);
if (ret != nullptr) return ret;
else return findNode(value, node->rightChild);
//return nullptr; // PLACEHOLDER
}
AVLNode* findNode(const T& value) const {
return findNode(value, root);
}
// method to clone a subtree and return it.
AVLNode* clone (AVLNode* node) const {
if (!node){
return nullptr;
} else {
AVLNode* temp = new AVLNode (*node->data,
clone(node->leftChild),
clone(node->rightChild));
temp->duplicates = node->duplicates;
temp->height = getHeight(node);
return temp;
}
}
void printNode(AVLNode *node) const {
std::cout << *node->data << ", ";
}
// should print the tree in a preorder traversal
void printPreorder(AVLNode* node) const {
// CODE HERE
if (node != nullptr) {
printNode(node);
printPreorder(node->leftChild);
printPreorder(node->rightChild);
}
}
// should print the tree in an inorder traversal
void printInorder(AVLNode* node) const {
// CODE HERE
if (node != nullptr) {
printInorder(node->leftChild);
printNode(node);
printInorder(node->rightChild);
}
}
// should print the tree in a postorder traversal
void printPostorder(AVLNode* node) const {
// CODE HERE
if (node != nullptr) {
printPostorder(node->leftChild);
printPostorder(node->rightChild);
printNode(node);
}
}
void insert(T& value, AVLNode* & node){
// CODE HERE
if (node == nullptr)
node = new AVLNode(value);
else if (value.compare(*node->data) < 0) {
insert(value, node->leftChild);
if (getHeight(node->leftChild) - getHeight(node->rightChild) == 2) {
if (value.compare(*node->leftChild->data) < 0)
rotateLeft(node);
else
rotateDoubleLeft(node);
}
}
else if (value.compare(*node->data) > 0) {
insert(value, node->rightChild);
if (getHeight(node->rightChild)-getHeight(node->leftChild) == 2) {
if (value.compare(*(node->rightChild->data)) > 0)
rotateRight(node);
else
rotateDoubleRight(node);
}
}
else {
node->duplicates++;
}
}
void balance(AVLNode* & node){
// CODE HERE
if (node == nullptr) return;
int bal = getHeight(node->rightChild) - getHeight(node->leftChild);
if (bal == -2) {
if (getHeight(node->leftChild->leftChild) >=
getHeight(node->leftChild->rightChild))
rotateRight(node);
else
rotateDoubleRight(node);
} else if (bal == 2) {
if (getHeight(node->rightChild->rightChild) >=
getHeight(node->rightChild->leftChild))
rotateLeft(node);
else
rotateDoubleLeft(node);
} else {
return;
}
balance(node->leftChild);
balance(node->rightChild);
}
void rotateLeft(AVLNode*& node){
// CODE HERE
AVLNode *rn = node->leftChild;
node->leftChild = rn->rightChild;
rn->rightChild = node;
node->height = std::max( getHeight( node->leftChild ),
getHeight( node->rightChild ) ) + 1;
rn->height = std::max( getHeight( rn->leftChild ), node->height ) + 1;
node = rn;
}
void rotateRight(AVLNode*& node){
// CODE HERE
AVLNode *rn = node->rightChild;
node->rightChild = rn->leftChild;
rn->leftChild = node;
node->height = std::max( getHeight( node->leftChild ),
getHeight( node->rightChild ) ) + 1;
rn->height = std::max( getHeight( rn->rightChild ), node->height ) + 1;
node = rn;
}
void rotateDoubleLeft(AVLNode*& node){
// CODE HERE
rotateRight(node->leftChild);
rotateLeft(node);
}
void rotateDoubleRight(AVLNode*& node){
// CODE HERE
rotateLeft(node->rightChild);
rotateRight(node);
}
void remove(T& value, AVLNode*& node){
// CODE HERE
if (node == nullptr) return;
if (value.compare(*node->data) == 0) {
if (node->duplicates > 0) {
node->duplicates--;
} else {
if (node->leftChild == nullptr
&& node->rightChild == nullptr) {
delete node->data;
delete node;
node = nullptr;
} else if (node->leftChild != nullptr) {
AVLNode *father = node;
AVLNode *p = node->leftChild;
while (p->rightChild != nullptr) {
father = p;
p = p->rightChild;
}
delete node->data;
node->data = p->data;
AVLNode *del = p;
if (p->leftChild != nullptr) {
del = p->leftChild;
p->leftChild = del->leftChild;
p->rightChild = del->rightChild;
p->data = del->data;
p->height = del->height;
p->duplicates = del->duplicates;
}
del->data = nullptr;
del->leftChild = nullptr;
del->rightChild = nullptr;
if (del == p) {
if (father == node) father->leftChild = nullptr;
else father->rightChild = nullptr;
}
delete del;
} else if (node->rightChild != nullptr) {
AVLNode *father = node;
AVLNode *p = node->rightChild;
while (p->leftChild != nullptr) {
father = p;
p = p->leftChild;
}
delete node->data;
node->data = p->data;
AVLNode *del = p;
if (p->rightChild != nullptr) {
del = p->rightChild;
p->leftChild = del->leftChild;
p->rightChild = del->rightChild;
p->data = del->data;
p->height = del->height;
p->duplicates = del->duplicates;
}
del->data = nullptr;
del->leftChild = nullptr;
del->rightChild = nullptr;
if (del == p) {
if (father == node) father->rightChild = nullptr;
else father->leftChild = nullptr;
}
delete del;
}
}
} else if (value.compare(*(node->data)) < 0) {
remove(value, node->leftChild);
} else if (value.compare(*(node->data)) > 0) {
remove(value, node->rightChild);
}
}
// private function to recursively empty
void empty(AVLNode* node){
// CODE HERE
if (node != nullptr) {
empty(node->leftChild);
empty(node->rightChild);
delete node->data;
node->height = 0;
node->leftChild = nullptr;
node->rightChild = nullptr;
delete node;
node = nullptr;
}
root = nullptr;
}
public:
AVLTree():
root {nullptr} {};
~AVLTree(){
empty();
}
// copy constructor: should copy all of the data from the other tree
// into this tree.
AVLTree(const AVLTree<T>& other){
root = clone(other.root);
}
// accessors --------------------------------------------------------
int getHeight() const {
return getHeight(root);
}
int getHeight(const T& value) const {
AVLNode* node = findNode(value);
return node ? node->height : -1; // ternary operator
}
int getDepth() const {
if (root){
return 0;
} else {
return -1;
}
}
int getDepth(T& value) const {
if (!root){
return -1;
} else {
return getDepth(value, root);
}
}
char getBalanceFactor(T& value) const {
// CODE HERE
return 0; // PLACEHOLDER FOR COMPILATION
}
// driver function to call the private preorder traversal
void printPreorder(){
std::cout << "[";
printPreorder(root);
std::cout << "]" << std::endl;
}
// driver function to call the private preorder traversal
void printInorder(){
std::cout << "[";
printInorder(root);
std::cout << "]" << std::endl;
}
// driver function to call the private preorder traversal
void printPostorder(){
std::cout << "[";
printPostorder(root);
std::cout << "]" << std::endl;
}
// should print the tree in a level-order traversal (NOT driver function)
void printLevelOrder(){
// CODE HERE
std::queue<AVLNode *> Q;
Q.push(root);
std::cout << "[";
while (!Q.empty()) {
AVLNode *t = Q.front();
printNode(t);
Q.pop();
if (t->leftChild != nullptr) Q.push(t->leftChild);
if (t->rightChild != nullptr) Q.push(t->rightChild);
}
std::cout << "]" << std::endl;
}
// mutators -----------------------------------------------------
// call private balance(1) on tree
void balance(){
balance(root);
}
// calls private remove function to remove starting at root
void remove(T& value){
remove(value, root);
}
void remove(T&& value){
T temp = T{value};
remove(temp);
}
void empty(){
// CODE HERE
empty(root);
}
// calls private insert function to insert starting at root
void insert(T& value){
insert(value, root);
}
void insert(T&& value){
T temp = T{value};
insert(temp);
}
};
#endif