#ifndef AVLTREE_H #define AVLTREE_H #include #include

class AvlTree { public: AvlTree* leftChild; AvlTree* rightChild; int height; int data;

};

AvlTree* createOnee(int val) { AvlTree* newAvl = new AvlTree(); newAvl->leftChild = nullptr; newAvl->rightChild = nullptr; newAvl->data = val; newAvl->height = 0; return newAvl;

}

int getheight(AvlTree *root) { if(root == nullptr) return 0; return root->height; }

int getBalance(AvlTree *root) { if(root == nullptr) return 0; return getheight(root->leftChild) - getheight(root->rightChild); }

AvlTree* right_rotation(AvlTree* root) { AvlTree* leftC_of_root = root->leftChild; AvlTree* rightC_of_leftC_of_root = leftC_of_root->rightChild;

leftC_of_root->rightChild = root; root->leftChild = rightC_of_leftC_of_root;

leftC_of_root->height = std::max(getheight(leftC_of_root->leftChild),getheight(leftC_of_root->rightChild)) + 1; root->height = std::max(getheight(root->leftChild),getheight(root->rightChild)) + 1;

return leftC_of_root;

}

AvlTree* left_rotation(AvlTree* root) { AvlTree* rightC_of_root = root->rightChild; AvlTree* leftC_of_rightC_of_root = rightC_of_root->leftChild;

rightC_of_root->leftChild = root; root->rightChild = leftC_of_rightC_of_root;

rightC_of_root->height = std::max(getheight(rightC_of_root->leftChild),getheight(rightC_of_root->rightChild)) + 1; root->height = std::max(getheight(root->leftChild),getheight(root->rightChild)) + 1; return rightC_of_root;

}

AvlTree* insert_avl(AvlTree* root,int val) { if(root == nullptr) return createOnee(val);

if(val < root->data) // if the data is greater than root->data, in order to binary search instructions , it will go through rightChild root->leftChild = insert_avl(root->leftChild,val); else if(root->data < val)// if the data is smaller than root->data, in order to binary search instructions , it will go through leftChild root->rightChild = insert_avl(root->rightChild,val); else return root;

root->height = std::max(getheight(root->leftChild),getheight(root->rightChild)) + 1; // updating the height

int ifbalance = getBalance(root);

// Right Right Case if (ifbalance < -1 && val > root->rightChild->data) return left_rotation(root);

// Left Left Case if (ifbalance > 1 && val < root->leftChild->data) return right_rotation(root);

// Left Right Case if (ifbalance > 1 && val > root->leftChild->data) { root->leftChild = left_rotation(root->leftChild); return right_rotation(root); }

// Right Left Case if (ifbalance < -1 && val < root->rightChild->data) { root->rightChild = right_rotation(root->rightChild); return left_rotation(root); }

return root; }

AvlTree* search_avl(AvlTree* root, int val) { if(root==nullptr) return nullptr; else if(val < root->data) // if val is smaller than root->data , it means we go to leftChild in order to binary search tree return search_avl(root->leftChild,val); else if(root->data < val) // if val is greater than root->data , it means we go to rightChild in order to binary search tree return search_avl(root->rightChild,val); else return root; }

#endif // AVLTREE_H

-----------------------------------------------------------------------------

#ifndef BINARYST_H #define BINARYST_H #include

struct binaryST { binaryST* leftChild; binaryST* rightChild; int data;

binaryST() { leftChild =nullptr; rightChild = nullptr; data = 0; }

};

binaryST* createOne(int val) { binaryST* newBinary = new binaryST(); newBinary->leftChild = nullptr; newBinary->rightChild = nullptr; newBinary->data = val; return newBinary;

}

binaryST* search_binary(binaryST* root, int val) { if(root==nullptr) return nullptr; else if(val < root->data) // if val is smaller than root->data , it means we go to leftChild in order to binary search tree return search_binary(root->leftChild,val); else if(root->data < val) // if val is greater than root->data , it means we go to rightChild in order to binary search tree return search_binary(root->rightChild,val); else return root; }

binaryST* insert_binary(binaryST* root, int val) { if(root == nullptr) return createOne(val);

if(val < root->data) // if the data is greater than root->data, in order to binary search instructions , it will go through rightChild root->leftChild = insert_binary(root->leftChild,val); else if(root->data < val)// if the data is smaller than root->data, in order to binary search instructions , it will go through leftChild root->rightChild = insert_binary(root->rightChild,val); else return root; }

#endif // BINARYST_H

--------------------------------------------------------------------------------

#include "binaryST.h" #include "avlTree.h" #include #include #include #include #include

using std::chrono::nanoseconds; constexpr int step = 100; constexpr int max_length = 10000; constexpr int times = 100;

nanoseconds cal_avl(AvlTree* root,int val, AvlTree* func(AvlTree*,int)) { auto begin =std::chrono::steady_clock::now(); root = func(root, val); auto end = std::chrono::steady_clock::now();

nanoseconds total (end - begin); return total; }

nanoseconds cal_binary(binaryST* root,int val, binaryST* func(binaryST*,int)) {

auto begin = std::chrono::steady_clock::now(); root = func(root, val); auto end = std::chrono::steady_clock::now();

nanoseconds total (end - begin); return total;

}

int main() { std::ofstream data("data.csv"); data << "SIZE,AVL INSERTION ORDERED,AVL INSERTION RANDOM,BINARY INSERTION ORDERED,BINARY INSERTION RANDOM,AVL SEARCH ORDERED,AVL SEARCH RANDOM,BINARY SEARCH ORDERED,BINARY SEARCH RANDOM"<

nanoseconds avl_search_ordered(0); nanoseconds binary_search_ordered(0); nanoseconds avl_search_random(0); nanoseconds binary_search_random(0);

AvlTree* avl_insertion_ordered = new AvlTree(); AvlTree* avl_insertion_random = new AvlTree();

binaryST* Binsertion_ordered = new binaryST(); binaryST* Binsertion_random = new binaryST();

for(int j = 0 ; j < i ; j++) { avl_ordered += cal_avl(avl_insertion_ordered,j*1,&insert_avl); binary_ordered += cal_binary(Binsertion_ordered,j*1,&insert_binary); avl_random += cal_avl(avl_insertion_random,rand()%10001,&insert_avl); binary_random += cal_binary(Binsertion_random,rand()%10001,&insert_binary);

}

avl_search_ordered +=cal_avl(avl_insertion_ordered,rand()%10001,&search_avl); binary_search_ordered += cal_binary(Binsertion_ordered,rand()%10001,&search_binary); avl_search_random +=cal_avl(avl_insertion_random,rand()%10001,&search_avl); binary_search_random +=cal_binary(Binsertion_random,rand()%10001,&search_binary);

std::cout<

// to the file

data<

}

data.close(); return 0; }

Can you make it work properly?