Lab Program 3 - Updating AVL Tree to support input from STDIN & a bit more. Mich
ID: 3860344 • Letter: L
Question
Lab Program 3 - Updating AVL Tree to support
input from STDIN & a bit more.
Michael McAlpin
Instructor - COP3502 - CS-1
Spring 2017
EECS-UCF
michael.mcalpin@ucf.edu
July 21, 2017
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 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 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.
•
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
-----------------------Provided Code----------------------------
/* 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<stdio.h>
#include<stdlib.h>
/*****
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
/
10 25 50
*/
printf("Pre order traversal of the constructed AVL tree is ");
preOrder(root);
printf(" ");
return 0;
}
Explanation / Answer
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
#define HEIGHT 1
struct node
{
int data;
struct node* left;
struct node* right;
int height;
};
struct node* get_node(int val){
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->left = NULL;
new_node->right = NULL;
new_node->data = val;
new_node->height = HEIGHT;
return new_node;
}
int get_height(struct node* root){
if(!root)
return 0;
else
return root->height;
}
int get_balance(struct node* root){
if(!root)
return 0;
return (get_height(root->left) - get_height(root->right));
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct node* left_rotate(struct node* root){
struct node* right = root->right;
struct node* left = right->left;
right->left = root;
root->right = left;
root->height = max(get_height(root->left), get_height(root->right)) + 1;
right->height = max(get_height(right->left), get_height(right->right)) + 1;
return right;
}
struct node* right_rotate(struct node* root){
struct node* left = root->left;
struct node* right = left->right;
left->right = root;
root->left = right;
root->height = max(get_height(root->left), get_height(root->right)) + 1;
left->height = max(get_height(left->left), get_height(left->right)) + 1;
return left;
}
struct node* insert(struct node* root, int val){
if(!root){
struct node* new_node = get_node(val);
return new_node;
}
if(root->data > val)
root->left = insert(root->left, val);
else
root->height = max(get_height(root->left), get_height(root->right)) + 1;
int balance = get_balance(root);
if(balance > 1 && root->left->data > val){
root = right_rotate(root);
}
else if(balance < -1 && root->right->data < val){
root = left_rotate(root);
}
else if(balance > 1 && root->left->data < val){
root->left = left_rotate(root->left);
root = right_rotate(root);
}
else if(balance < -1 && root->right->data > val){
root->right = right_rotate(root->right);
root = left_rotate(root);
}
return root;
}
struct node* balance_tree(struct node* root){
struct node* x, *y;
int lheight,rheight;
lheight = get_height(root->left);
rheight = get_height(root->right);
if(lheight >= rheight)
x = root->left;
else
x = root->right;
lheight = get_height(x->left);
rheight = get_height(x->right);
if(x == root->left){
if(lheight >= rheight){
y = x->left;
}
else
y = x->right;
}
if(x == root->right){
if(lheight > rheight){
y = x->left;
}
else
y = x->right;
}
if(root->left == x && x->left == y){
root = right_rotate(root);
}
else if(x == root->right && x->right == y){
root = left_rotate(root);
}
else if(x == root->left && y == x->right){
root->left = left_rotate(root->left);
root = right_rotate(root);
}
else if(x == root->right && y == x->left){
root->right = right_rotate(root->right);
root = left_rotate(root);
}
return root;
}
struct node* inorder_succ_right_tree(struct node* root){
struct node* temp = root->right;
while(temp->left){
temp = temp->left;
}
return temp;
}
struct node* deletion(struct node* root, int val){
if(!root)
return NULL;
if(root->data > val){
root->left = deletion(root->left, val);
}
else if(root->data < val){
root->right = deletion(root->right, val);
}
else{
struct node* temp;
if(root->left == NULL || root->right == NULL){
if(root->left)
temp = root->left;
else if(root->right)
temp = root->right;
else
temp = NULL;
root = NULL;
free(root);
return temp;
}
else{
temp = inorder_succ_right_tree(root);
root->data = temp->data;
root->right = deletion(root->right,temp->data);
}
}
if(root){
root->height = max(get_height(root->left), get_height(root->right)) + 1;
int balance = get_balance(root);
if(balance > 1 || balance < -1)
root = balance_tree(root);
}
return root;
}
void preorder(struct node* root){
if(!root)
return;
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
void inorder(struct node* root){
if(!root)
return;
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
main(){
struct node* root = NULL;
root = insert(root, 5);
root = insert(root, 9);
root = insert(root, 10);
root = insert(root, 11);
root = insert(root, 17);
root = insert(root, 23);
root = insert(root, 31);
root = insert(root, 1);
root = insert(root, 2);
printf("Preorder ");
preorder(root);
printf(" ----------- ");
printf("Inorder ");
inorder(root);
printf(" ----------- ");
root = deletion(root,10);
printf("After deletion ");
printf("Preorder ");
preorder(root);
printf(" ----------- ");
printf("Inorder ");
inorder(root);
printf(" ----------- ");
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.