Given the code for managing AVL trees is available in the program named avlTree.c and the program builds its tree using programmed inputs in the main function the objective of this lab problem is to provide AVL tree support for a different input data type - floating point numbers rather than the integer support in the existing code. The updated avlTree.c should be named AVLsort.c. The program should be able to read the unsorted data from STDIN and output the sorted data to STDOUT.

/* Recap left & right rotations (simple case) T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x (on right side) y x / \ Right Rotation / \ x T3 > T1 y / \ < - - - - - - - / \ T1 T2 Left Rotation T2 T3 Keys in both of the above trees follow the following order keys(T1) < key(x) < keys(T2) < key(y) < keys(T3) So BST property is not violated anywhere. */ #include #include /***** Modifying the data stored in the AVL tree? 1. Start with the structure shown below. 2. Sort out the data type and any additional data that should be there. 3. Maybe even add a struct to support the requirements. a. All data types can be put in the struct BUT b. Make sure that there is a valid data type that can be arithmetically compared so as to maintain the integrity of the AVL tree. 4. Make sure to check all the locations that manage the "key". *****/ // An AVL tree node struct node { int key; struct node *left; struct node *right; int height; }; // A utility function to get maximum of two integers int max(int a, int b); // A utility function to get height of the tree int height(struct node *N) { if (N == NULL) return 0; return N->height; } // A utility function to get maximum of two integers int max(int a, int b) { return (a > b)? a : b; } /* Helper function that allocates a new node with the given key and NULL left and right pointers. */ struct node* newNode(int key) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; // new node is initially added at leaf return(node); } // A utility function to right rotate subtree rooted with y // See the diagram given above. struct node *rightRotate(struct node *y) { struct node *x = y->left; struct node *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right))+1; x->height = max(height(x->left), height(x->right))+1; // Return new root return x; } // A utility function to left rotate subtree rooted with x // See the diagram given above. struct node *leftRotate(struct node *x) { struct node *y = x->right; struct node *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right))+1; y->height = max(height(y->left), height(y->right))+1; // Return new root return y; } /* * RECAP Balance is based on Height * Hn = Hl - Hr * so * positive => LEFT HEAVY * negative => RIGHT HEAVY */ // Get Balance factor of node N int getBalance(struct node *N) { if (N == NULL) return 0; return height(N->left) - height(N->right); } struct node* insert(struct node* node, int key) { /* 1. Perform the normal BST insertion */ if (node == NULL) return(newNode(key)); if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); /* 2. Update height of this ancestor node */ node->height = max(height(node->left), height(node->right)) + 1; /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int balance = getBalance(node); // If this node becomes UNBALANCED, then there are 4 cases /* CASE # 1 => LEFT-LEFT aka left? T1, T2, T3 and T4 are subtrees. z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2 */ // Left Left Case in code if (balance > 1 && key < node->left->key) return rightRotate(node); /* Case #2 => RIGHT-RIGHT aka right? z y / \ / \ T1 y Left Rotate(z) z x / \ - - - - - - - -> / \ / \ T2 x T1 T2 T3 T4 / \ T3 T4 */ // Right Right Case in code if (balance < -1 && key > node->right->key) return leftRotate(node); /* CASE # 3 => LEFT-RIGHT aka left-right? z z x / \ / \ / \ y T4 Left Rotate (y) x T4 Right Rotate(z) y z / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ T1 x y T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2 */ // Left Right Case in code if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } /* CASE #4 = RIGHT-LEFT aka right-left? z z x / \ / \ / \ T1 y Right Rotate (y) T1 x Left Rotate(z) z y / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ x T4 T2 y T1 T2 T3 T4 / \ / \ T2 T3 T3 T4 */ // Right Left Case in code if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } // A utility function to print preorder traversal of the tree. // The function also prints height of every node void preOrder(struct node *root) { if(root != NULL) { printf("%2d/%1d ", root->key, root->height); preOrder(root->left); preOrder(root->right); } } /* The main function below is the test harness for the AVL tree code above. Any modifications to support alternative input modes, like STDIN, will happen here. */ /* Driver program to test above functions*/ int main() { struct node *root = NULL; /* Constructing tree given in the above figure */ root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); root = insert(root, 50); root = insert(root, 25); /* Double check height calculations during RR/LR/RRL/LRR (See case below....) */ root = insert(root, 5); root = insert(root, 4); /* The constructed AVL Tree would be 30 / \ 20 40 / \ \ 5 25 50 / \ 4 10 */ printf("Pre order traversal of the constructed AVL tree is "); preOrder(root); printf(" "); return 0; }

Annotations