We provided you with the starter code for implementing AVL Trees. Your task is to implement the functions declared in AVL tree.h that are not already implemented in AVL tree.c. Each function must be implemented in O(log n) running time, as we learned in class. Note that AVL tree.c is the only file you will submit, so make sure your implementation works with the original provided AVL tree.h. Make sure to carefully study the starter code before you begin to add your own. Functions to implement:

AVL Node* search(AVL Node* node, int key)

AVL Node* insert(AVL Node* node, int key, void* value)

AVL Node* delete(AVL Node* node, int key)

/*************************************************************************

AVL_tree.c:

#include "AVL_tree.h"

/************************************************************************* ** Suggested helper functions *************************************************************************/

/* Returns the height (number of nodes on the longest root-to-leaf path) of * the tree rooted at node 'node'. Returns 0 if 'node' is NULL. */ int height(AVL_Node* node);

/* Updates the height of the tree rooted at node 'node' based on the heights * of its children. Note: this should be an O(1) operation. */ void update_height(AVL_Node* node);

/* Returns the balance factor (height of left subtree - height of right * subtree) of node 'node'. Returns 0 of node is NULL. */ int balance_factor(AVL_Node* node);

/* Returns the result of performing the corresponding rotation in the AVL * tree rooted at 'node'. */ // single rotations: right/clockwise AVL_Node* right_rotation(AVL_Node* node); // single rotations: left/counter-clockwise AVL_Node* left_rotation(AVL_Node* node); // double rotation: right/clockwise then left/counter-clockwise AVL_Node* right_left_rotation(AVL_Node* node); // double rotation: left/counter-clockwise then right/clockwise AVL_Node* left_right_rotation(AVL_Node* node);

/* Returns the successor node of 'node'. */ AVL_Node* successor(AVL_Node* node);

/* Creates and returns an AVL tree node with key 'key', value 'value', height * of 1, and left and right subtrees NULL. */ AVL_Node* create_node(int key, void* value);

/************************************************************************* ** Provided functions *************************************************************************/ void print_tree_inorder_(AVL_Node* node, int offset) { if (node == NULL) return; print_tree_inorder_(node->right, offset + 1); printf("%*s %d [%d] ", offset, "", node->key, node->height); print_tree_inorder_(node->left, offset + 1); }

void print_tree_inorder(AVL_Node* node) { print_tree_inorder_(node, 0); }

void delete_tree(AVL_Node* node) { if (node == NULL) return; delete_tree(node->left); delete_tree(node->right); free(node); }

/************************************************************************* ** Required functions ** Must run in O(log n) where n is the number of nodes in a tree rooted ** at 'node'. *************************************************************************/

AVL_Node* search(AVL_Node* node, int key) { return node; }

AVL_Node* insert(AVL_Node* node, int key, void* value) { return node; }

AVL_Node* delete(AVL_Node* node, int key) { return node; }

/*************************************************************************

AVL_tree.h

#include #include

#ifndef __AVL_tree_header #define __AVL_tree_header

typedef struct avl_node { int key; // key stored in this node void* value; // value associated with this node's key int height; // height of tree rooted at this node struct avl_node* left; // this node's left child struct avl_node* right; // this node's right child } AVL_Node;

/* Returns the node, from the tree rooted at 'node', that contains key 'key'. * Returns NULL if 'key' is not in the tree. */ AVL_Node* search(AVL_Node* node, int key);

/* Inserts the key/value pair 'key'/'value' into the AVL tree rooted at * 'node'. If 'key' is already a key in the tree, updates the value * associated with 'key' to 'value'. Returns the root of the resulting tree. */ AVL_Node* insert(AVL_Node* node, int key, void* value);

/* Deletes the node with key 'key' from the AVL tree rooted at 'node'. If * 'key' is not a key in the tree, the tree is unchanged. Returns the root of * the resulting tree. */ AVL_Node* delete(AVL_Node* node, int key);

/* Prints the keys of the AVL tree rooted at 'node', in the in-order * traversal order. */ void print_tree_inorder(AVL_Node* node);

/* Frees all memory allocated for an AVL tree rooted at 'node'. */ void delete_tree(AVL_Node* node);

#endif /*************************************************************************

AVL_tree_tester.c

#include #include #include

#include "AVL_tree.h"

#define MAX_LIMIT 1024

AVL_Node* create_tree(FILE* f); void test_tree(AVL_Node* root); void print_tree_report(AVL_Node* root);

int main(int argc, char* argv[]) { AVL_Node* root = NULL;

// If user specified a file for reading, create a tree with keys from it. if (argc > 1) { FILE* f = fopen(argv[1], "r"); if (f == NULL) { fprintf(stderr, "Unable to open the specified input file: %s ", argv[1]); exit(0); } root = create_tree(f); fclose(f); } else { printf("You did not specify an input file."); printf(" We will start with an empty tree. "); }

test_tree(root); return 0; }

AVL_Node* create_tree(FILE* f) { char line[1024]; int key; AVL_Node* root = NULL;

while (fgets(&line[0], MAX_LIMIT, f)) { // read the next line key = atoi(&line[0]); printf("read %d ", key); root = insert(root, key, NULL); // no values for this simple tester print_tree_report(root); } return root; }

void test_tree(AVL_Node* root) { char line[1024]; AVL_Node* node;

while (1) { printf("Choose a command: (s)earch, (i)nsert, (d)elete, (q)uit "); fgets(&line[0], MAX_LIMIT, stdin); if (line[0] == 'q') { // quit printf("Quit selected. Goodbye! "); delete_tree(root); return; } if (line[0] == 's') { // search printf("Search selected. Enter key to search for: "); fgets(&line[0], MAX_LIMIT, stdin); node = search(root, atoi(&line[0])); if (node != NULL) { printf("Key %d was found at height %d. ", node->key, node->height); } else { printf("This key is not in the tree. "); } } else if (line[0] == 'i') { // insert printf("Insert selected. Enter key to insert"); printf(" (no values in this simple tester): "); fgets(&line[0], MAX_LIMIT, stdin); root = insert(root, atoi(&line[0]), NULL); print_tree_report(root); } else if (line[0] == 'd') { // delete printf("Delete selected. Enter key to delete: "); fgets(&line[0], MAX_LIMIT, stdin); root = delete(root, atoi(&line[0])); print_tree_report(root); } } }

void print_tree_report(AVL_Node* root) { printf("** The tree is now: "); print_tree_inorder(root); printf("** "); } /*************************************************************************

sample input:

0 1 2 3 4 5 6 7 8 9