(avlTree.c)

/* 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 / \

#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 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 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 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 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;

}

Abstract 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 fora 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. 1 Objectives 1.1 Inputs There is only one additional command parameter, the sort order (ascending or descend- ing - a or d, respectively), passed via the command line. The data will be delivered through STDIN. 1.1.1 Command Line arguments The code will be invoked as follows .AVLsort a Note that the command given above will read the data in from STDIN. Also note that the End-Of-File (EOF) key sequence will vary depending on the operating system. This is a moot point in the event that redirection is used to input data from a simple text file. The a parameter indicates the data will be sorted in ascending order. Likewise, the d parameter indicates the data will be sorted in descending order. Abstract 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 fora 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. 1 Objectives 1.1 Inputs There is only one additional command parameter, the sort order (ascending or descend- ing - a or d, respectively), passed via the command line. The data will be delivered through STDIN. 1.1.1 Command Line arguments The code will be invoked as follows .AVLsort a Note that the command given above will read the data in from STDIN. Also note that the End-Of-File (EOF) key sequence will vary depending on the operating system. This is a moot point in the event that redirection is used to input data from a simple text file. The a parameter indicates the data will be sorted in ascending order. Likewise, the d parameter indicates the data will be sorted in descending order