In this project, we will be implementing the two rotate functions used by AVL trees, and then comparing the running time of an AVL tree vs a regular binary search tree that does not balance itself. Files provided in the project:

1) BinarySearchTree.h and BinarySearchTree.c. These files contain the prototypes and definitions for all of the functions for a regular binary search tree that does not balance itself. You do not need to edit either of these files at all.

2) AVLTree.h and AVLTree.c. These files contain the prototypes of all of the functions we will be using for the AVL Tree implementation. AVLTree has the definitions of all of the functions except for leftRotate() and rightRotate(). You much provide the implementation of these two rotate functions in AVLTree.c.

3) abc123Project5.c. Rename this file to your abc123. This file contains a function named compareTreeRunningTimes() which takes as input an integer n. It inserts every number from 1 to n into the regular BST, then searches for every number from 1 to n, and then frees the tree. It then repeats the same process for an AVL tree, and compares the running time. The main() function calls this function with various input sizes. You do not need to edit this file, although feel free to play with the file to find other ways to compare the trees.

5) Makefile. Update the makefile to reflect your abc123. Compile using make p5. Execute the program using ./p5

please do not edit BinarySearchTree.h or BinarySearchTree.c

/************************************************************************ BinarySearchTree.h Purpose: Define constants used in the project. Struct definitions for a general Binary Search Tree. Define function prototypes used by general Binary Search Trees. ************************************************************************/ #include  #include  #include  #include  //#define constant values #define TRUE 1 #define FALSE 0 //typedef for the Element struct which constains a c string to store a URL in the BrowserList typedef struct { long key; } Element; //Typedef for a node in the doubly linked list (has next and previous pointers). typedef struct NodeT { Element element; struct NodeT *pLeft; struct NodeT *pRight; } NodeT; //Typedef for a binary search tree implementation. //Contains a pointer to the root node of the tree. typedef struct { NodeT *pRoot; } BinarySearchTreeImp; typedef BinarySearchTreeImp *BinarySearchTree; /*****Prototypes*******/ //Malloc a new BinarySearchTreeImp and return it's address. BinarySearchTree newBinarySearchTree(); //Free the BinarySearchTree and any nodes that still exist in the tree. void freeBinarySearchTree(BinarySearchTree tree); //Recursive function to free every node in a Binary Search Tree. void postOrderNodeFree(NodeT *p); //Allocate a new node and store "value" as the Element in the node. Return the address of the node. NodeT *allocateNode(Element value); //Function to search for a node with key value equal to searchValue. Return a pointer to the node if you find it or return NULL if it does not exist. Calls the recursiveSearch() function, passing it the root pointer. NodeT *search(BinarySearchTree tree, long searchValue); //Recursive algorithm for searching for a node with key value equal to searchValue. Return a pointer to the node if you find it or return NULL if it does not exist. NodeT *recursiveSearch(NodeT *p, long searchValue); //Create a node to store the given Element and add it as a leaf in the BinarySearchTree. Do not worry about balancing the tree for this project. //Return true if the insert worked successfully, and return false if the node already existed in the tree. int recursiveInsert(NodeT **p, Element value); //Create a node to store the given Element and add it as a leaf in the BinarySearchTree. Do not worry about balancing the tree for this project. //Return true if the insert worked successfully, and return false if the node already existed in the tree. int insert(BinarySearchTree tree, Element value); //Recursivly print the key values of all nodes in the subtree rooted at p in increasing order. Calls the recursive function passing it a pointer to the root node. void printInOrder(BinarySearchTree tree); //Recursive function to conduct the inorder traversal. void recursivePrintInOrder(NodeT *p); //Print the key values of all nodes in the subtree rooted at p according to a preorder traversal. Calls the recursive function passing it a pointer to the root node. void printPreOrder(BinarySearchTree tree); //Recursive function to conduct the preorder traversal. void recursivePrintPreOrder(NodeT *p); 

****************************************

#include "BinarySearchTree.h" BinarySearchTree newBinarySearchTree() { BinarySearchTree tree = (BinarySearchTree)malloc(sizeof(BinarySearchTreeImp)); tree->pRoot = NULL; return tree; } void freeBinarySearchTree(BinarySearchTree tree) { postOrderNodeFree(tree->pRoot); free(tree); } void postOrderNodeFree(NodeT *p) { if(p != NULL) { postOrderNodeFree(p->pLeft); postOrderNodeFree(p->pRight); free(p); } } NodeT *allocateNode(Element value) { NodeT *pNew = (NodeT *)malloc(sizeof(NodeT)); pNew->pLeft = NULL; pNew->pRight = NULL; pNew->element = value; return pNew; } NodeT *search(BinarySearchTree tree, long searchValue) { return recursiveSearch(tree->pRoot,searchValue); } //Recursive algorithm for searching for a node with key value equal to searchValue. Return a pointer to the node if you find it or return NULL if it does not exist. NodeT *recursiveSearch(NodeT *p, long searchValue) { if(p==NULL) return NULL; if(p->element.key == searchValue) return p; else if(p->element.key > searchValue) return recursiveSearch(p->pLeft,searchValue); else return recursiveSearch(p->pRight,searchValue); } int insert(BinarySearchTree tree, Element value) { return recursiveInsert(&(tree->pRoot),value); } int recursiveInsert(NodeT **p, Element value) { if(*p == NULL) { *p = allocateNode(value); return TRUE; } if( (*p)->element.key == value.key ) return FALSE; else if( (*p)->element.key > value.key ) return recursiveInsert( &((*p)->pLeft), value); else return recursiveInsert( &((*p)->pRight), value); } void printInOrder(BinarySearchTree tree) { recursivePrintInOrder(tree->pRoot); } void recursivePrintInOrder(NodeT *p) { if(p != NULL) { recursivePrintInOrder(p->pLeft); printf("%ld ",p->element.key); recursivePrintInOrder(p->pRight); } } void printPreOrder(BinarySearchTree tree) { recursivePrintPreOrder(tree->pRoot); } void recursivePrintPreOrder(NodeT *p) { if(p != NULL) { printf("%ld ",p->element.key); recursivePrintPreOrder(p->pLeft); recursivePrintPreOrder(p->pRight); } } 

********************************************************

/************************************************************************ AVLTree.h Purpose: Define constants used in the project. Struct definitions for a general AVL Tree. Define function prototypes used by general AVL Trees. ************************************************************************/ #include  #include  #include  #include  //#define constant values #define TRUE 1 #define FALSE 0 //typedef for the Element struct which constains a c string to store a URL in the BrowserList typedef struct { long key; } ElementAVL; //Typedef for a node in the doubly linked list (has next and previous pointers). typedef struct NodeAVL { ElementAVL element; struct NodeAVL *pLeft; struct NodeAVL *pRight; struct NodeAVL *pParent; int iBalanceFactor; } NodeAVL; //Typedef for a AVL tree implementation. //Contains a pointer to the root node of the tree. typedef struct { NodeAVL *pRoot; } AVLTreeImp; typedef AVLTreeImp *AVLTree; /*****Prototypes*******/ //Malloc a new AVLTreeImp and return it's address. AVLTree newAVLTree(); //Free the AVLTree and any nodes that still exist in the tree. void freeAVLTree(AVLTree tree); //Recursive function to free every node in a AVL Tree. void postOrderAVLNodeFree(NodeAVL *p); //Allocate a new node and store "value" as the Element in the node. Return the address of the node. NodeAVL *allocateAVLNode(ElementAVL value); //Function to search for a node with key value equal to searchValue. Return a pointer to the node if you find it or return NULL if it does not exist. Calls the recursiveSearch() function, passing it the root pointer. NodeAVL *searchAVL(AVLTree tree, int searchValue); //Recursive algorithm for searching for a node with key value equal to searchValue. Return a pointer to the node if you find it or return NULL if it does not exist. NodeAVL *recursiveSearchAVL(NodeAVL *p, int searchValue); //Create a node to store the given Element and add it as a leaf in the AVLTree. Calls the recursive insert function. //Return true if the insert worked successfully, and return false if the node already existed in the tree. int insertAVL(AVLTree tree, ElementAVL value); //Create a node to store the given Element and add it as a leaf in the AVLTree. Rebalances the tree if necessary. //Return true if the insert worked successfully, and return false if the node already existed in the tree. int recursiveInsertAVL(NodeAVL *p, ElementAVL value); //Function that iteratively traces back towards the root, updating balance factors and using rotations to balance the tree if necessary. void checkForRebalancing(NodeAVL *p); //Function that "rotates p down and to the left" and pulls p's right child "up and to the left". void leftRotate(NodeAVL *p); //Function that "rotates p down and to the right" and pulls p's left child "up and to the right". void rightRotate(NodeAVL *p); //Recursivly print the key values of all nodes in the subtree rooted at p in increasing order. Calls the recursive function passing it a pointer to the root node. void printInOrderAVL(AVLTree tree); //Recursive function to conduct the inorder traversal. void recursivePrintInOrderAVL(NodeAVL *p); //Print the key values of all nodes in the subtree rooted at p according to a preorder traversal. Calls the recursive function passing it a pointer to the root node. void printPreOrderAVL(AVLTree tree); //Recursive function to conduct the preorder traversal. void recursivePrintPreOrderAVL(NodeAVL *p); 

***************************************************

AVLTree.c

#include "AVLTree.h" AVLTree newAVLTree() { AVLTree tree = (AVLTree)malloc(sizeof(AVLTreeImp)); tree->pRoot = NULL; return tree; } void freeAVLTree(AVLTree tree) { postOrderAVLNodeFree(tree->pRoot); free(tree); } void postOrderAVLNodeFree(NodeAVL *p) { if(p != NULL) { postOrderAVLNodeFree(p->pLeft); postOrderAVLNodeFree(p->pRight); free(p); } } NodeAVL *allocateAVLNode(ElementAVL value) { NodeAVL *pNew = (NodeAVL *)malloc(sizeof(NodeAVL)); pNew->pLeft = NULL; pNew->pRight = NULL; pNew->pParent = NULL; pNew->element = value; pNew->iBalanceFactor = 0; return pNew; } NodeAVL *searchAVL(AVLTree tree, int searchValue) { return recursiveSearchAVL(tree->pRoot,searchValue); } //Recursive algorithm for searching for a node with key value equal to searchValue. Return a pointer to the node if you find it or return NULL if it does not exist. NodeAVL *recursiveSearchAVL(NodeAVL *p, int searchValue) { if(p==NULL) return NULL; if(p->element.key == searchValue) return p; else if(p->element.key > searchValue) return recursiveSearchAVL(p->pLeft,searchValue); else return recursiveSearchAVL(p->pRight,searchValue); } int insertAVL(AVLTree tree, ElementAVL value) { if(tree->pRoot == NULL) { //The recursiveInsert() function assumes that the pointer we pass is not NULL, so if pRoot is NULL then we handle this case here. tree->pRoot = allocateAVLNode(value); return TRUE; } else { int result = recursiveInsertAVL(tree->pRoot,value); //If we rotated the root, the new root would be the parent of the old root. if(tree->pRoot->pParent != NULL){ tree->pRoot = tree->pRoot->pParent; } return result; } } //Recursive algorithm to insert value into an AVL tree. //Our base case is slightly different than the base case shown in class. Instead of checking if the current node is NULL, we check to see if the next node would be NULL if we continued. This allows us to update the parent pointer. //Given the implementation, p will never be NULL. int recursiveInsertAVL(NodeAVL *p, ElementAVL value) { if( p->element.key == value.key ) { return FALSE; } else if( p->element.key > value.key ) { if(p->pLeft != NULL) return recursiveInsertAVL(p->pLeft, value); else { //value.key is less than current node, but current node does not have a left child. //The new node should be the left child of the current node. //Ater insertion, check to see if we need to rebalance the tree. p->pLeft = allocateAVLNode(value); p->pLeft->pParent = p; checkForRebalancing(p->pLeft); return TRUE; } } else { if(p->pRight != NULL) return recursiveInsertAVL(p->pRight, value); else { //value.key is greater than current node, but current node does not have a right child. //The new node should be the right child of the current node. //Ater insertion, check to see if we need to rebalance the tree. p->pRight = allocateAVLNode(value); p->pRight->pParent = p; checkForRebalancing(p->pRight); return TRUE; } } } //We are passed p which is a pointer to the newly inserted node into the tree. //We walk from p towards the root of the tree until we find a node that needs to be rotated or until we determine that the tree is balanced. //We perform any rotations and update any balance factors that need to be updated. void checkForRebalancing(NodeAVL *p) { NodeAVL *z = p; NodeAVL *x; for(x=z->pParent; x != NULL; x = x->pParent) { //x is the parent of z. if(z == x->pLeft) { //z is the left child of x. Check to see if x was imbalanced to the left prior to insertion. if(x->iBalanceFactor < 0) { //Both are true: (1) z is left child of x, and (2) x was imbalanced to the left. //We need to fix with rotations. if(z->iBalanceFactor <= 0) { //z is NOT imbalanced to the right, so a right rotate on x will fix the tree. rightRotate(x); //Update the balance factors of x and z. x->iBalanceFactor = 0; z->iBalanceFactor = 0; } else { //z is imbalanced to the right, so a right rotation on x will cause x to be imbalanced to the left. //To fix, we left rotate z and then we right rotate x to fix the tree. //We create w to store the right child of z (before insertion), as it's balance factor will affect the ending balance factors. //Note w cannot be NULL since z is imbalanced to the right. NodeAVL *w = z->pRight; leftRotate(z); rightRotate(x); //Update the balance factors. if(w->iBalanceFactor > 0) { w->iBalanceFactor = 0; x->iBalanceFactor = 0; z->iBalanceFactor = -1; } else if(w->iBalanceFactor == 0) { w->iBalanceFactor = 0; x->iBalanceFactor = 0; z->iBalanceFactor = 0; } else { w->iBalanceFactor = 0; x->iBalanceFactor = 1; z->iBalanceFactor = 0; } } return; } else { //x was not imbalanced to the left, so we only need to update x's balance factor. if(x->iBalanceFactor == 1) { x->iBalanceFactor = 0; return; } //If here then x's balance factor before was 0. //Update balance factor, and set z to be it's parent for the next iteration of the for loop. x->iBalanceFactor = -1; z = x; } } else { //z is the right child of x. Check to see if x was imbalanced to the right prior to insertion. if(x->iBalanceFactor > 0) { //Both are true: (1) z is right child of x, and (2) x was imbalanced to the right. //We need to fix with rotations. if(z->iBalanceFactor >= 0) { //z is NOT imbalanced to the left, so a left rotate on x will fix the tree. leftRotate(x); //Update the balance factors of x and z. x->iBalanceFactor = 0; z->iBalanceFactor = 0; } else { //z is imbalanced to the left, so a left rotation on x will cause x to be imbalanced to the right. //To fix, we right rotate z and then we left rotate x to fix the tree. //We create w to store the left child of z (before insertion), as it's balance factor will affect the ending balance factors. //Note w cannot be NULL since z is imbalanced to the left. NodeAVL *w = z->pLeft; rightRotate(z); leftRotate(x); //Update the balance factors. if(w->iBalanceFactor > 0) { w->iBalanceFactor = 0; x->iBalanceFactor = -1; z->iBalanceFactor = 0; } else if(w->iBalanceFactor == 0) { w->iBalanceFactor = 0; x->iBalanceFactor = 0; z->iBalanceFactor = 0; } else { w->iBalanceFactor = 0; x->iBalanceFactor = 0; z->iBalanceFactor = 1; } } return; } else { //x was not imbalanced to the right, so we only need to update x's balance factor. if(x->iBalanceFactor == -1) { x->iBalanceFactor = 0; return; } //If here then x's balance factor before was 0. //Update balance factor, and set z to be it's parent for the next iteration of the for loop. x->iBalanceFactor = 1; z = x; } } } } void printInOrderAVL(AVLTree tree) { recursivePrintInOrderAVL(tree->pRoot); } void recursivePrintInOrderAVL(NodeAVL *p) { if(p != NULL) { recursivePrintInOrderAVL(p->pLeft); printf("%ld ",p->element.key); recursivePrintInOrderAVL(p->pRight); } } void printPreOrderAVL(AVLTree tree) { recursivePrintPreOrderAVL(tree->pRoot); } void recursivePrintPreOrderAVL(NodeAVL *p) { if(p != NULL) { printf("%ld ",p->element.key); recursivePrintPreOrderAVL(p->pLeft); recursivePrintPreOrderAVL(p->pRight); } } ***************************** 

abc123project5.c

#include  #include "BinarySearchTree.h" #include "AVLTree.h" void compareTreeRunningTimes(long n); int main() { srand(time(NULL)); long i; //Call function for inputs of size 10, 100, 1000, 10000, and 100000. for(i=10; i<1000000; i*=10) { compareTreeRunningTimes(i); printf(" --------------------------------------------------- "); } //Call function for inputs of size 200000, 300000, 400000, and 500000. for(i=200000; i<=500000; i+=100000) { compareTreeRunningTimes(i); printf(" --------------------------------------------------- "); } return 0; } //Insert the values from 1 to n into a regular binary search tree and into an AVL Tree, and then search for each of the n values. //Report the amount of time each takes in milliseconds. void compareTreeRunningTimes(long n) { printf("Time for n = %ld",n); printf(" Building regular Binary Search Tree. "); clock_t startTime = clock(); BinarySearchTree tree = newBinarySearchTree(); long i; for(i=0; i