Question
You are given a skeleton C code in the following files: -------------------avl.h--------------------------- #ifndef __AVL_H #define __AVL_H # ifndef TYPE # define TYPE int # endif
You are given a skeleton C code in the following files:
-------------------avl.h---------------------------
#ifndef __AVL_H
#define __AVL_H
# ifndef TYPE
# define TYPE int
# endif
#ifndef EQ
#define EQ(a, b) (a == b)
#endif
#ifndef LT
#define LT(a, b) (a < b)
#endif
struct AVLnode {
TYPE val;
struct AVLnode *left;
struct AVLnode *right;
int height;
};
struct AVLTree {
struct AVLnode *root;
int cnt;
};
/* the public interface */
/* Alocate and initialize AVL tree structure. */
struct AVLTree * newAVLTree();
/* Initialize AVL tree structure. */
void initAVLTree(struct AVLTree *tree);
/* Deallocate nodes in AVL tree and deallocate the AVL tree structure. */
void deleteAVLTree(struct AVLTree *tree);
/* Deallocate nodes in AVL tree. */
void clearAVLTree(struct AVLTree *tree);
void addAVLTree(struct AVLTree *tree, TYPE val);
void removeAVLTree(struct AVLTree * tree, TYPE val);
void removeAllAVLTree(struct AVLTree * tree, TYPE val);
int containsAVLTree(struct AVLTree *tree, TYPE val);
/* the internal interface */
void _freeAVL(struct AVLnode *node);
int h(struct AVLnode *current);
void setHeight (struct AVLnode * current);
int bf(struct AVLnode * current);
struct AVLnode * rotateLeft(struct AVLnode * current);
struct AVLnode * rotateRight(struct AVLnode * current);
struct AVLnode * _balance(struct AVLnode * current);
TYPE _leftMost(struct AVLnode *cur);
struct AVLnode * _removeLeftmost(struct AVLnode * cur);
struct AVLnode * _removeNode(struct AVLnode * cur, TYPE val);
struct AVLnode * _removeAllNodes(struct AVLTree * tree, struct AVLnode *
cur, TYPE val);
struct AVLnode * AVLnodeAdd(structAVLnode * current, TYPE newValue);
#endif
----------------------------------------------------------------------------------------------------------------
--------------------------------------avl.c----------------------------------------------
#include
#include
#include
#include "avl.h"
/* Alocate and initialize AVL tree structure. */
struct AVLTree * newAVLTree()
{
struct AVLTree *tree = (struct AVLTree *)malloc(sizeof(struct
AVLTree));
assert(tree != 0);
initAVLTree(tree);
return tree;
}
/* Initialize AVL tree structure. */
void initAVLTree(struct AVLTree *tree)
{
tree->cnt = 0;
tree->root = 0;
}
void _freeAVL(struct AVLnode *node)
{
if (node != 0) {
_freeAVL(node->left);
_freeAVL(node->right);
free(node);
}
}
/* Deallocate nodes in AVL tree. */
void clearAVLTree(struct AVLTree *tree)
{
_freeAVL(tree->root);
tree->root = 0;
tree->cnt = 0;
}
/* Deallocate nodes in AVL tree and deallocate the AVL tree structure. */
void deleteAVLTree(struct AVLTree *tree)
{
clearAVLTree(tree);
free(tree);
}
/* return height of current node */
int h(struct AVLnode *current)
{
if (current == 0)
return -1;
return current->height;
}
/* set height for current node */
void setHeight (struct AVLnode * current)
{
int lch = h(current->left);
int rch = h(current->right);
if (lch < rch)
current->height = 1 + rch;
else
current->height = 1 + lch;
}
/* return balance factor value */
int bf(struct AVLnode * current)
{
return h(current->right) - h(current->left);
}
/* left-rotate subtree of current node */
struct AVLnode * rotateLeft(struct AVLnode * current)
{
struct AVLnode * newtop = current->right;
current->right = newtop->left;
newtop->left = current;
setHeight(current);
setHeight(newtop);
return newtop;
}
/* right-rotate subtree of current node */
struct AVLnode * rotateRight(struct AVLnode * current)
{
struct AVLnode * newtop = current->left;
current->left = newtop->right;
newtop->right = current;
setHeight(current);
setHeight(newtop);
return newtop;
}
/* balance subtree of current node */
struct AVLnode * _balance(struct AVLnode * current)
{
int cbf = bf(current);
if (cbf < -1){
if (bf(current->left) > 0) /* double rotation */
current->left = rotateLeft(current->left);
return rotateRight(current); /* single rotation */
} else if(cbf > 1){
if(bf(current->right) < 0)
current->right = rotateRight(current->right);
return rotateLeft(current);
}
setHeight(current);
return current;
}
/* add newValue to subtree of current node */
struct AVLnode * AVLnodeAdd(structAVLnode * current, TYPE newValue)
{
/* FIX ME */
}
/* add val to AVL tree */
void addAVLTree(struct AVLTree *tree, TYPE val)
{
tree->root = AVLnodeAdd(tree->root, val);
tree->cnt++;
}
/* determine if val is contained in the AVL tree */
int containsAVLTree(struct AVLTree *tree, TYPE val)
{
struct AVLnode* cur = tree->root;
while(cur != 0){
if (EQ(cur->val, val))
return 1;
else if (LT(val, cur->val))
cur = cur->left;
else
cur = cur->right;
}
return 0;
}
/* find leftmost value from subtree of current node */
TYPE _leftMost(struct AVLnode *cur)
{
while(cur->left != 0)
cur = cur->left;
return cur->val;
}
/* remove leftmost node from subtree of current node */
struct AVLnode * _removeLeftmost(struct AVLnode * cur)
{
struct AVLnode * temp;
if(cur->left != 0){
cur->left = _removeLeftmost(cur->left);
return _balance(cur);
}
temp = cur->right;
free(cur);
return temp;
}
/* remove val from subtree of cur node */
struct AVLnode * _removeNode(struct AVLnode * cur, TYPE val)
{
struct AVLnode * temp;
if(EQ(val, cur->val)){
if(cur->right != 0){
cur->val = _leftMost(cur->right);
cur->right = _removeLeftmost(cur->right);
return _balance(cur);
} else {
temp = cur->left;
free(cur);
return temp;
}
} else if (LT(val, cur->val))
cur->left = _removeNode(cur->left, val);
else cur->right = _removeNode(cur->right, val);
return _balance(cur);
}
/* remove val from AVL tree */
void removeAVLTree(struct AVLTree * tree, TYPE val)
{
if(containsAVLTree(tree, val)){
tree->root = _removeNode(tree->root, val);
tree->cnt--;
}
}
/* remove val from AVL tree */
void removeAllAVLTree(struct AVLTree * tree, TYPE val)
{
if(containsAVLTree(tree, val))
tree->root = _removeAllNodes(tree, tree->root, val);
}
struct AVLnode * _removeAllNodes(struct AVLTree * tree, struct AVLnode *
cur, TYPE val){
struct AVLnode * temp = NULL;
while(EQ(val, cur->val)){
if(cur->right != 0){
cur->val = _leftMost(cur->right);
cur->right = _removeLeftmost(cur->right);
tree->cnt--;
} else {
temp = cur->left;
free(cur);
tree->cnt--;
cur = temp;
}
}
if (cur){
if (LT(val, cur->val))
cur->left = _removeAllNodes(tree,cur->left, val);
else
cur->right = _removeAllNodes(tree,cur->right, val);
}
return _balance(cur);
}
------------------------------------------------------------------------------------------------
---------------main.c-----------------------------------------------------------
#include
#include
#include
#include
#include "avl.h"
void preorder(struct AVLnode *node, TYPE *min_cost, TYPE *path, int *m,
TYPE *candidate_path, int *n, TYPE sumDiff, TYPE parent_value);
TYPE absoluteDiff(TYPE a, TYPE b);
int FindMinPath(struct AVLTree *tree, TYPE *path);
void printBreadthFirstTree(struct AVLTree *tree);
/* --------------------
Finds the minimum-cost path in an AVL tree
Input arguments:
tree = pointer to the tree,
path = pointer to array that stores values of nodes along the min-
cost path,
Output: return the min-cost path length
pre: assume that
path is already allocated sufficient memory space
tree exists and is not NULL
*/
int FindMinPath(struct AVLTree *tree, TYPE *path)
{
int path_len = 0; /* the initial length of the min-cost path */
struct AVLnode * current = tree->root;
TYPE min_cost = (TYPE) 10^6 * tree->cnt; /* initial high value for
minimum */
int c_path_len = 0; /* length of a candidate path */
TYPE candidate_path[100]; /* candidate path is a static array */
path[path_len] = tree->root->val; /* min-cost path must contain
the root */
path_len++;
/* Write this part of the function */
if (tree->cnt > 1){
/* Traverse the tree and find the min-cost path */
/* FIX ME */
}
return path_len;
}
/* ----------
Finds absolute difference between two input numbers
*/
TYPE absoluteDiff(TYPE a, TYPE b){
if (a<0)
return (TYPE) 0;
else
return (TYPE) abs(a-b);
}
/*-------------------------
Recursively traverses the AVL tree and finds its min cost path
Input argument:
node = pointer to the current node visited by recursion,
min_cost = the latest minimum cost,
path = array of values of nodes along the latest best path,
path_len = number of elements in path array,
candidate_path = currently considered path array
c_path_len = number of elements in the candidate path array
pre: assume that all input arguments are well initialized and have enough
memory space
post:
path points to the array of values in the min-cost path of the AVL
tree
path_len is the number of elements (i.e., nodes) in the min-cost path
of the AVL tree
*/
void preorder(struct AVLnode *node, TYPE *min_cost, TYPE *path, int
*path_len,
TYPE *candidate_path, int *c_path_len, TYPE sumDiff, TYPE
parent_value)
{
int i;
/* put the current node in a candidate path */
candidate_path[*c_path_len] = node->val;
(*c_path_len)++;
/* cumulative cost of the candidate path */
sumDiff = sumDiff + absoluteDiff(parent_value, node->val);
/* Write the recursion case(s) and the stopping-recursion case(s) */
/* FIX ME */
}
/* -----------------------
Printing the contents of an AVL tree in breadth-first fashion
param: pointer to a tree
pre: assume that tree was initialized well before calling this function
*/
void printBreadthFirstTree(struct AVLTree *tree){
struct AVLnode **queue; /* print using a queue, where queue is
implemented as a static array */
struct AVLnode *current = tree->root;
int start = 0; /* start index of queue indicating the first element to
be processed */
int end = 0; /* end index of queue indicating the latest element added
to the queue */
/* allocate memory to queque */
queue = (struct AVLnode **) malloc(100*sizeof(struct AVLnode));
/* FIX ME */
}
/* -----------------------
The main function
param: argv = pointer to the name (and path) of a file that the program
reads for adding elements to the AVL tree
*/
int main(int argc, char** argv) {
FILE *file;
int len, i;
TYPE num; /* value to add to the tree from a file */
struct timeval stop, start; /* variables for measuring execution
time */
int pathArray[50]; /* static array with values along the min-cost
path of the AVL tree */
struct AVLTree *tree;
tree = newAVLTree(); /*initialize and return an empty tree */
file = fopen(argv[1], "r"); /* filename is passed in argv[1] */
assert(file != 0);
/* Read input file and add numbers to the AVL tree */
while((fscanf(file, "%i", &num)) != EOF){
addAVLTree(tree, num);
}
/* Close the file */
fclose(file);
printf(" Printing the tree breadth-first : ");
printBreadthFirstTree(tree);
gettimeofday(&start, NULL);
/* Find the minimum-cost path in the AVL tree*/
len = FindMinPath(tree, pathArray);
gettimeofday(&stop, NULL);
/* Print out all numbers on the minimum-cost path */
printf(" The minimum-cost path is: ");
for(i = 0; i < len; i++)
printf("%d ", pathArray[i]);
printf(" ");
printf(" Your execution time to find the mincost path is %f
microseconds ", (double) (stop.tv_usec - start.tv_usec));
/* Free memory allocated to the tree */
deleteAVLTree(tree);
return 0;
}
and the file with values that should be read and added to the AVL Tree for testing your code:
------------------------input.txt-------------------------------------
50 61 42 21 6 11 23 31 40 41 12 22 16 13 25 34 5 27 30 20 2 7 8 9 4 10 0
43 73 75 74
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
