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. 1 Objectives 1.1 Inputs

There is only one additional command parameter, the sort order (ascending or descending - 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. Reading the data in from a file would be as follows:

AVLsort a < someFilename Assuming the file redirected to STDIN was named SixUnsorted, the command would be as shown below: //SixUnsorted contents 10.4759 99.2010 32.7510 78.3219 45.9431 25.1705 NID@Eustis$AVLsort a < SixUnsorted // The command, parameter, and redirection

2 Process The program can assume that only one floating point number will be on a line and will be input from STDIN. In the event that the input is NOT a floating point number, it is acceptable to discard that number. Each number, once succesffuly converted from text to floating point, will be added to or inserted into the AVL tree.

When all the input has been consumed, the program will then output the data, sorted in the order specified in the command line. Specifically, if the command line parameter is a then the numbers would be output in ascending order. Likewise, if the command line parameter is d, the numbers would be output in descending order.

2.1 HW 3 Considerations This assignment uses floating point numbers for the key. It is well worth the while to consider using this to also code a test harness using the three or four character airport LocID as the key. We discussed in lecture that casting these characters as integers might produce meaningful alphabetically sorted results. This testing cycle, that is floating point and characters cast as integers, will streamline completing HW 3. 3 Outputs The output of the program will be the appropriately sorted input data. For the data shown above the outputs are shown below. 10.4759 25.1705 32.7510 45.9431 78.3219 99.2010

Code to be Modified:

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

/ \ < - - - - - - - / \

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;

}