Fill in the CODE HERE part of AVLtree.h In this lab, you will be implementing AV
ID: 3912771 • Letter: F
Question
Fill in the CODE HERE part of AVLtree.h
In this lab, you will be implementing AVL trees. The point is just to fully implement an AVL tree that accepts a Data class as its type (it is a template class). The Data class DoubleData defines a method to compare to other DoubleData objects, which you should use when comparing those objects. AVLTree is a template class, so all the code is going in the header file again.
//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
//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);
}
}
//AVLtree.h
#ifndef AVLTREE_H
#define AVLTREE_H
#include "Data.h"
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;
// accessors -------------------------------------------------------------
// will return the height of a given AVLNode*. Look at the definition for
// height. -1 if the tree is empty, or max height of children + 1.
// Must use recursion, since it counts leaves-up and we start traversals
// at root.
int getHeight(AVLNode* node) const {
// CODE HERE
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
return 0; // PLACEHOLDER
}
// driver function for getDepthAux(T&,AVLNode*), which does the recursion.
// getDepth(T&,AVLNode*) does an extra check for node not found in tree.
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);
}
}
// returns the AVLNode* that points to the node containing the
// parameter value in its data member.
// the node parameter is the root of the current subtree.
// Must use recursion.
AVLNode* findNode(const T& value, AVLNode* node) const {
// CODE HERE
return nullptr; // PLACEHOLDER
}
// returns the AVLNode* that points to the node containing the
// parameter value in its data member.
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;
}
}
// Possibly several functions to be used by printing traversal functions
// (below). These functions may need to know what the last leaf in a
// subtree is to print nicely (by my standards, anyway).
// CODE HERE
// should print the tree in a preorder traversal
void printPreorder(AVLNode* node) const {
// CODE HERE
}
// should print the tree in an inorder traversal
void printInorder(AVLNode* node) const {
// CODE HERE
}
// should print the tree in a postorder traversal
void printPostorder(AVLNode* node) const {
// CODE HERE
}
// 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
}
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);
}
// searches the tree for a value. If it is found, the height
// is returned. If not, then -1 is returned.
int getHeight(const T& value) const {
AVLNode* node = findNode(value);
return node ? node->height : -1; // ternary operator
}
// returns the depth for the whole tree. should be 0 if the
// tree is nonempty, and -1 if it is empty.
int getDepth() const {
if (root){
return 0;
} else {
return -1;
}
}
// returns the depth for a given value.
// should be -1 if tree is empty, or the number of steps
// down from root node if not.
int getDepth(T& value) const {
if (!root){
return -1;
} else {
return getDepth(value, root);
}
}
// will return the balance factor of a value in the tree.
// if the value does not exist, return -128 (the lowest value for
// a 1-byte char). If it does exist, return the balance factor.
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
}
// 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);
}
// driver function for emptying the tree, since there is no public access
// to root of tree (as many other functions do in this file)
void empty(){
// CODE HERE
}
// 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
Explanation / Answer
//Data.h
#include<stdlib.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
//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);
}
}
//AVLtree.h
#ifndef AVLTREE_H
#define AVLTREE_H
#include "Data.h"
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;
// accessors -------------------------------------------------------------
// will return the height of a given AVLNode*. Look at the definition for
// height. -1 if the tree is empty, or max height of children + 1.
// Must use recursion, since it counts leaves-up and we start traversals
// at root.
int getHeight(AVLNode* node) const {
if (node==NULL)
return -1;
else
{
int leftTree = getHeight(node->left);
int rightTree = getHeight(node->right);
if (leftTree > rightTree)
return(leftTree+1);
else
return(rightTree+1);
}
}
// returns the depth from the current subtree (node is subroot)
// must use recursion.
int getDepthAux(const T& value, AVLNode* node) const {
AVLNode* n=findNode(value,node);
return getHeight(n); // PLACEHOLDER
}
// driver function for getDepthAux(T&,AVLNode*), which does the recursion.
// getDepth(T&,AVLNode*) does an extra check for node not found in tree.
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);
}
}
// returns the AVLNode* that points to the node containing the
// parameter value in its data member.
// the node parameter is the root of the current subtree.
// Must use recursion.
AVLNode* findNode(const T& value, AVLNode* node) const {
if(node==nullptr)
return nullptr;
else
{
if(node->data == value)
return node;
else if((node->data)>value)
return findNode(value,node->left);
else if((node->data)<value )
return findNode(value,node->right);
}
}
// returns the AVLNode* that points to the node containing the
// parameter value in its data member.
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;
}
}
// Possibly several functions to be used by printing traversal functions
// (below). These functions may need to know what the last leaf in a
// subtree is to print nicely (by my standards, anyway).
// CODE HERE
// should print the tree in a preorder traversal
void printPreorder(AVLNode* node) const {
if(node==nullptr)
return;
else{
std::cout<<root->key;
std::cout<<' ';
printPreorder(node->leftChild);
printPreorder(node->rightChild);
}
}
// should print the tree in an inorder traversal
void printInorder(AVLNode* node) const {
if(node==nullptr)
return;
else{
printInorder(node->leftChild);
std::cout<<root->key;
std::cout<<' ';
printInorder(node->rightChild);
}
}
// should print the tree in a postorder traversal
void printPostorder(AVLNode* node) const {
if(node==nullptr)
return;
else{
printPreorder(node->leftChild);
printPreorder(node->rightChild);
std::cout<<root->key;
std::cout<<' ';
}
}
// 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){
if (node == nullptr)
return 0;
return getheight(node->leftChild) - getheight(node->rightChild);
}
// 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){
AVLNode *ne = node->rightChild;
AVLNode *temp = ne->leftChild;
temp->left = ne;
ne->right = temp;
if(getHeight(ne->leftChild)<=getHeight(ne->rightChild) ){
ne->height=getHeight(ne->rightChild)+1;
}
else{
ne->height=getHeight(ne->leftChild)+1;
}
if(getHeight(temp->leftChild)<=getHeight(temp->rightChild) ){
temp->height=getHeight(temp->rightChild)+1;
}
else{
temp->height=getHeight(temp->leftChild)+1;
}
// Return new root
return temp;
}
// 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){
AVLNode *ne = node->leftChild;
AVLNode *temp = ne->rightChild;
ne->right = temp;
temp->left = ne;
if(getHeight(ne->leftChild)<=getHeight(ne->rightChild) ){
ne->height=getHeight(ne->rightChild)+1;
}
else{
ne->height=getHeight(ne->leftChild)+1;
}
if(getHeight(temp->leftChild)<=getHeight(temp->rightChild) ){
temp->height=getHeight(temp->rightChild)+1;
}
else{
temp->height=getHeight(temp->leftChild)+1;
}
// Return new root
return ne;
}
// 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){
AVLTree* temp;
temp= rotateLeft(node);
node=rotateLeft(temp->leftChild);
node->height=getHeight(node);
}
// 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){
AVLTree* temp;
temp= rotateRight(node);
node=rotateRight(temp->rightChild);
node->height=getHeight(node);
}
// 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){
if(!findNode(value))
return;
else{
AVLTree* n=findNode(value);
if(n->duplicates>0){
duplicates-=1;
return;
}
else{
}
}
}
// private function to recursively empty
void empty(AVLNode* node){
if(node==nullptr)
return;
else{
empty(node->leftChild);
free(node);
empty(node->rightChild);
}
}
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);
}
// searches the tree for a value. If it is found, the height
// is returned. If not, then -1 is returned.
int getHeight(const T& value) const {
AVLNode* node = findNode(value);
return node ? node->height : -1; // ternary operator
}
// returns the depth for the whole tree. should be 0 if the
// tree is nonempty, and -1 if it is empty.
int getDepth() const {
if (root){
return 0;
} else {
return -1;
}
}
// returns the depth for a given value.
// should be -1 if tree is empty, or the number of steps
// down from root node if not.
int getDepth(T& value) const {
if (!root){
return -1;
} else {
return getDepth(value, root);
}
}
// will return the balance factor of a value in the tree.
// if the value does not exist, return -128 (the lowest value for
// a 1-byte char). If it does exist, return the balance factor.
char getBalanceFactor(T& value) const {
if(!findNode(value))
return -128;
else{
return getBalance(findNode(value));
}
}
// 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(){
// Base Case
if (root == NULL) return;
// Create an empty queue for level order tarversal
queue<AVLTree *> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false)
{
// Print front of queue and remove it from queue
AVLtree *node = q.front();
cout << node->data << " ";
q.pop();
/* Enqueue left child */
if (node->leftChild != NULL)
q.push(node->leftChild);
/*Enqueue right child */
if (node->rightChild != NULL)
q.push(node->rightChild);
}
}
// 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);
}
// driver function for emptying the tree, since there is no public access
// to root of tree (as many other functions do in this file)
void empty(){
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.