Fill in the CODE HERE parts //AVLtree.h #ifndef AVLTREE_H #define AVLTREE_H #inc
ID: 3912985 • Letter: F
Question
Fill in the CODE HERE parts
//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);
}
//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
Explanation / Answer
Hope it helps!!!
//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);
}
// 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);
}
// 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);
}
//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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.