AVL Tree Creation main.cpp #include #include #include #include #include #include #include "AVLTree.h" using namespace std; int main() {    AVLTree* tree1Root = new AVLTree(50, nullptr);    srand(time(NULL));    uint32_t numNodes = 10;    for (uint32_t i=1; i < numNodes; i++ ) {        tree1Root = tree1Root->insert(( rand() % 10000));        //Uncomment to help debug lost nodes //       if (tree1Root->countNodes() != i+2) { //           std::cout<<"Lost node "<updateHeight(); //       if ( ! tree1Root->isBalanced() ) { //           std::cout<<"Tree1Root balanced: FAILED at node insertion "<countNodes() == numNodes) {        std::cout<<"tree1Root lost Nodes: PASSED"<countNodes()<updateHeight();    float expectedHeight = log2(numNodes) * 1.5;    if (tree1Root->getHeight() < expectedHeight) {        std::cout<<"tree1Root height: PASSED"<getHeight()<isBalanced()) {        std::cout<<"Tree1Root is balanced: PASSED"< using namespace std; //************** already implemented helper functions AVLTree::AVLTree(int t_data, AVLTree* t_parent, AVLTree* t_left, AVLTree* t_right) {    data = t_data;    height = 0;    parent = t_parent;    left = t_left;    right = t_right; } bool AVLTree::isLeaf() {    //insert code here    return ((left == nullptr) and (right == nullptr)); } uint32_t AVLTree::getHeight() {    return height; } //******* int AVLTree::getBalance() {    //insert code here } AVLTree* AVLTree::rotateRight() {    //insert code here } AVLTree* AVLTree::rotateLeft() {    //insert code here } AVLTree* AVLTree::rebalance() {    //insert code here } AVLTree* AVLTree::insert(int new_data) {    //insert code here to insert and rebalance tree } //*************************** //Do not edit code below here uint32_t AVLTree::countNodes() {    //insert code here    if (isLeaf()) {        return 1;    }    if (left != nullptr) {        if (right != nullptr) {            return 1 + left->countNodes() + right->countNodes();        }        return 1+ left->countNodes();    }    return 1 + right->countNodes(); } void AVLTree::updateHeight() {    //insert code here    if (isLeaf()) {        height = 0;        return;    }    if (left != nullptr) {        left->updateHeight();        if (right != nullptr) {            right->updateHeight();            height = (1 + max(left->getHeight(), right->getHeight()));            return;        }        height = 1 + left->getHeight();        return;    }    right->updateHeight();    height = 1 + right->getHeight();    return; } bool AVLTree::isBalanced() {    if ( isLeaf() ) {        return true;    }    if (left == nullptr) {        return ( right->getHeight() < 1 );    }    if (right == nullptr) {        return ( left->getHeight() < 1 );    }    return ( left->isBalanced() and right->isBalanced() and abs(getBalance() < 2) ); } AVLTree.h #include class AVLTree { public:        int data;        uint32_t height;        AVLTree* parent;        AVLTree* left;        AVLTree* right;        //base functions defined for you        AVLTree(int data, AVLTree* parent=nullptr, AVLTree* left=nullptr, AVLTree* right=nullptr);        bool isLeaf();        uint32_t getHeight();        //*******************        //functions you need to define        //insert a node and rebalance tree to maintain AVL balanced tree        //return new root of tree        AVLTree* insert(int data);        //computes a node's balance factor by subtracting the right subtree height from the left subtree height.        int getBalance();        //checks for imbalance and rebalances if neccessary        //return new root of tree        AVLTree* rebalance();        //implement a right rotate        //return new root of tree        AVLTree* rotateRight();        //implement a left rotate        //return new root of tree        AVLTree* rotateLeft();        //Do not edit these three functions        bool isBalanced();        uint32_t countNodes();        void updateHeight(); };

AVL Tree Creation

main.cpp

#include <fstream>
#include <iostream>
#include <cmath>
#include <time.h>
#include <stack>
#include <queue>

#include "AVLTree.h"

using namespace std;

int main() {

   AVLTree* tree1Root = new AVLTree(50, nullptr);
   srand(time(NULL));
   uint32_t numNodes = 10;
   for (uint32_t i=1; i < numNodes; i++ ) {
       tree1Root = tree1Root->insert(( rand() % 10000));

       //Uncomment to help debug lost nodes
//       if (tree1Root->countNodes() != i+2) {
//           std::cout<<"Lost node "<<std::endl;
//           return 1;
//       }

       //uncomment to help debug unbalanced trees
//       tree1Root->updateHeight();
//       if ( ! tree1Root->isBalanced() ) {
//           std::cout<<"Tree1Root balanced: FAILED at node insertion "<<i<<std::endl;
//           return 1;
//       }

   }

   if (tree1Root->countNodes() == numNodes) {
       std::cout<<"tree1Root lost Nodes: PASSED"<<std::endl;
   }
   else {
       std::cout<<"tree1Root lost Nodes: FAILED expected: 100 actual: "<<tree1Root->countNodes()<<std::endl;
   }

   tree1Root->updateHeight();
   float expectedHeight = log2(numNodes) * 1.5;
   if (tree1Root->getHeight() < expectedHeight) {
       std::cout<<"tree1Root height: PASSED"<<std::endl;
   }
   else {
       std::cout<<"tree1Root height: FAILED expected: <" <<expectedHeight<<" actual: "<<tree1Root->getHeight()<<std::endl;
   }

   if ( tree1Root->isBalanced()) {
       std::cout<<"Tree1Root is balanced: PASSED"<<std::endl;
   }
   else {
       std::cout<<"Tree1Root is balanced: FAILED"<<std::endl;
   }
}

AVLTree.cpp

#include "AVLTree.h"

#include <iostream>

using namespace std;
//************** already implemented helper functions
AVLTree::AVLTree(int t_data, AVLTree* t_parent, AVLTree* t_left, AVLTree* t_right) {
   data = t_data;
   height = 0;
   parent = t_parent;
   left = t_left;
   right = t_right;
}

bool AVLTree::isLeaf() {
   //insert code here
   return ((left == nullptr) and (right == nullptr));
}

uint32_t AVLTree::getHeight() {
   return height;
}

//*******

int AVLTree::getBalance() {
   //insert code here
}

AVLTree* AVLTree::rotateRight() {
   //insert code here
}

AVLTree* AVLTree::rotateLeft() {
   //insert code here
}

AVLTree* AVLTree::rebalance() {
   //insert code here
}

AVLTree* AVLTree::insert(int new_data) {
   //insert code here to insert and rebalance tree
}

//***************************
//Do not edit code below here
uint32_t AVLTree::countNodes() {
   //insert code here
   if (isLeaf()) {
       return 1;
   }
   if (left != nullptr) {
       if (right != nullptr) {
           return 1 + left->countNodes() + right->countNodes();
       }
       return 1+ left->countNodes();
   }
   return 1 + right->countNodes();
}

void AVLTree::updateHeight() {
   //insert code here
   if (isLeaf()) {
       height = 0;
       return;
   }
   if (left != nullptr) {
       left->updateHeight();
       if (right != nullptr) {
           right->updateHeight();
           height = (1 + max(left->getHeight(), right->getHeight()));
           return;
       }
       height = 1 + left->getHeight();
       return;
   }
   right->updateHeight();
   height = 1 + right->getHeight();
   return;
}

bool AVLTree::isBalanced() {
   if ( isLeaf() ) {
       return true;
   }
   if (left == nullptr) {
       return ( right->getHeight() < 1 );
   }
   if (right == nullptr) {
       return ( left->getHeight() < 1 );
   }
   return ( left->isBalanced() and right->isBalanced() and abs(getBalance() < 2) );
}

AVLTree.h

#include <iostream>

class AVLTree {
public:
       int data;
       uint32_t height;
       AVLTree* parent;
       AVLTree* left;
       AVLTree* right;

       //base functions defined for you
       AVLTree(int data, AVLTree* parent=nullptr, AVLTree* left=nullptr, AVLTree* right=nullptr);
       bool isLeaf();
       uint32_t getHeight();

       //*******************
       //functions you need to define

       //insert a node and rebalance tree to maintain AVL balanced tree
       //return new root of tree
       AVLTree* insert(int data);

       //computes a node's balance factor by subtracting the right subtree height from the left subtree height.
       int getBalance();

       //checks for imbalance and rebalances if neccessary
       //return new root of tree
       AVLTree* rebalance();

       //implement a right rotate
       //return new root of tree
       AVLTree* rotateRight();

       //implement a left rotate
       //return new root of tree
       AVLTree* rotateLeft();

       //Do not edit these three functions
       bool isBalanced();
       uint32_t countNodes();
       void updateHeight();
};