In this lab, you will be implementing AVL trees. The point is just to fully impl
ID: 3891896 • Letter: I
Question
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.
---------------------------------------------------------------------------------------------
#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
#ifndef DANI_AVL_TREE_H_
#define DANI_AVL_TREE_H_
#include <iostream>
#include "list.h"
namespace dani {
template <class T>
class AVLNode {
public:
AVLNode(const T& value) : data_(value), left_(NULL), right_(NULL), parent_(NULL) {}
~AVLNode() {}
const T& GetValue() const { return data_; }
void SetLeft(AVLNode* left) { left_ = left; }
AVLNode* GetLeft() const { return left_; }
void GetRight(AVLNode* right) { right_ = right; }
AVLNode* GetRight() const { return right_; }
void SetParent(AVLNode* parent) { parent_ = parent; }
AVLNode* GetParent() const { return parent_; }
void Print() const { std::cout << data_ << std::endl; }
private:
AVLNode();
T data_;
AVLNode* left_;
AVLNode* right_;
AVLNode* parent_;
};
template <class T>
class AVLTree {
public:
AVLTree() : root_(NULL) {}
~AVLTree();
bool Insert(const T& value);
AVLNode<T>* GetRoot() const { return root_; }
AVLNode<T>* Find(AVLNode<T>* root, const T& value) const;
int Height(AVLNode<T>* root) const;
int BalanceFactor(AVLNode<T>* root) const;
void RotateLeft (AVLNode<T>* root);
void RotateRight(AVLNode<T>* root);
void PrintPreOrder (AVLNode<T>* root) const; // Parent, Left, Right
void PrintInOrder (AVLNode<T>* root) const; // Left, Parent, Right
void PrintPostOrder(AVLNode<T>* root) const; // Left, Right, Parent
void PrintBreadthSearchFirst() const;
private:
void InsertAVLNode(AVLNode<T>* root, AVLNode<T>* ins);
void DeleteAVLNode(AVLNode<T>* node);
AVLNode<T>* root_;
};
template <class T>
AVLTree<T>::~AVLTree() {
if( root_ ) {
DeleteAVLNode(root_);
}
}
template <class T>
void AVLTree<T>::DeleteAVLNode(AVLNode<T>* node) {
if( node ) {
DeleteAVLNode( node->GetLeft() );
DeleteAVLNode( node->GetRight() );
delete node; // Post Order Deletion
}
}
template <class T>
bool AVLTree<T>::Insert(const T& value) {
AVLNode<T>* new_node = new (std::nothrow) AVLNode<T>(value);
if( !new_node )
return true; // Out of memory
if( !root_ ) // Special case
root_ = new_node;
else
InsertAVLNode(root_, new_node);
return false;
}
template <class T>
void AVLTree<T>::InsertAVLNode(AVLNode<T>* root, AVLNode<T>* ins) {
// Binary Search Tree insertion algorithm
if( ins->GetValue() <= root->GetValue() ) {
if( root->GetLeft() ) // If there is a left child, keep searching
InsertAVLNode(root->GetLeft(), ins);
else { // Found the right spot
root->SetLeft(ins);
ins->SetParent(root);
}
}
else {
if( root->GetRight() ) // If there is a right child, keep searching
InsertAVLNode(root->GetRight(), ins);
else {// Found the right spot
root->SetRight(ins);
ins->SetParent(root);
}
}
// AVL balancing algorithm
int balance = BalanceFactor(root);
if( balance > 1 ) { // left tree unbalanced
if( BalanceFactor( root->GetLeft() ) < 0 ) // right child of left tree is the cause
RotateLeft( root->GetLeft() ); // double rotation required
RotateRight(root);
}
else if( balance < -1 ) { // right tree unbalanced
if( BalanceFactor( root->GetRight() ) > 0 ) // left child of right tree is the cause
RotateRight( root->GetRight() );
RotateLeft(root);
}
}
template <class T>
void AVLTree<T>::PrintPreOrder(AVLNode<T>* root) const {
if( root ) {
root->Print(); // Parent
PrintPreOrder(root->GetLeft()); // Left
PrintPreOrder(root->GetRight()); // Right
}
}
template <class T>
void AVLTree<T>::PrintInOrder(AVLNode<T>* root) const {
if( root ) {
PrintInOrder(root->GetLeft()); // Left
root->Print(); // Parent
PrintInOrder(root->GetRight()); // Right
}
}
template <class T>
void AVLTree<T>::PrintPostOrder(AVLNode<T>* root) const {
if( root ) {
PrintPostOrder(root->GetLeft()); // Left
PrintPostOrder(root->GetRight()); // Right
root->Print(); // Parent
}
}
// Depth-First Search
template <class T>
AVLNode<T>* AVLTree<T>::Find(AVLNode<T>* root, const T& value) const {
if( root ) {
//std::cout << root->GetValue() << std::endl;
if( root->GetValue() == value )
return root; // Found
else if( value < root->GetValue() )
return Find( root->GetLeft(), value );
else
return Find( root->GetRight(), value );
}
return NULL;
}
template <class T>
int AVLTree<T>::Height(AVLNode<T>* root) const {
int height = 0;
if( root ) {
int left = Height(root->GetLeft());
int right = Height(root->GetRight());
height = 1 + ((left > right) ? left : right) ;
}
return height;
}
template <class T>
int AVLTree<T>::BalanceFactor(AVLNode<T>* root) const {
int balance = 0;
if( root ) {
balance = Height(root->GetLeft()) - Height(root->GetRight());
}
return balance;
}
template <class T>
void AVLTree<T>::RotateLeft (AVLNode<T>* root) {
AVLNode<T>* newroot = root->GetRight();
root->SetRight(newroot->GetLeft());
newroot->SetLeft(root);
if( root->GetParent() == NULL ) {
root_ = newroot;
newroot->SetParent(NULL);
}
else {
if( root->GetParent()->GetLeft() == root ) {
root->GetParent()->SetLeft(newroot);
}
else {
root->GetParent()->SetRight(newroot);
}
newroot->SetParent(root->GetParent());
}
root->SetParent(newroot);
}
template <class T>
void AVLTree<T>::RotateRight(AVLNode<T>* root) {
// Rotate node
AVLNode<T>* newroot = root->GetLeft();
root->SetLeft(newroot->GetRight());
newroot->SetRight(root);
// Adjust tree
if( root->GetParent() == NULL ) {
root_ = newroot;
newroot->SetParent(NULL);
}
else {
if( root->GetParent()->GetLeft() == root ) {
root->GetParent()->SetLeft(newroot);
}
else {
root->GetParent()->SetRight(newroot);
}
newroot->SetParent(root->GetParent());
}
root->SetParent(newroot);
}
template <class T>
void AVLTree<T>::PrintBreadthSearchFirst() const {
List< AVLNode<T>* > node_list;
node_list.PushFront(root_);
while( node_list.Length() > 0 ) {
AVLNode<T>* n;
node_list.PopFront(&n);
n->Print();
if( n->GetLeft() ) node_list.PushBack(n->GetLeft());
if( n->GetRight() ) node_list.PushBack(n->GetRight());
}
}
}
#endif // DANI_AVL_TREE_H_
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.