## Question

• AVL tree and applications

• Data merge and stats aggregation

Write C programs avl.h and avl.c to implement and test AVL trees. Requirements:

1. avl.h and avl.c contain the following definition of AVL tree structures and functions, using data name field as key for search, insert and delete operations.

typedef struct rec {

char name[40];

float score;

} RECORD;

typedef struct node {

RECORD data;

int height;

struct node *left;

struct node *right;

} TNODE;

/* check if the tree is AVL tree, return 1 if true, 0 otherwise */

int is_avl(TNODE *root);

/* do left rotation */

TNODE *rotate_left(TNODE *root);

/* do right rotation */

TNODE *rotate_right(TNODE *root);

/* insert record (name, score) into the AVL using name as key */

void insert(TNODE **rootp, char *name, float score);

/* delete node of data.name from the AVL */

void delete(TNODE **rootp, char *name); //

// following functions are from a7

TNODE *extract_smallest_node(TNODE **rootp);

void display_inorder(TNODE *root);

void display_tree(TNODE *root, int prelen);

TNODE *search(TNODE *root, char *name);

void clean_tree(TNODE **rootp);

Use the provided a8q1.c to test the implementations of the above functions. The output should be like the following.

public test

gcc avl.c a8q1.c -o a8q1

a8q1

Write C programs markstats.h, markstats.c, to store partitioned data using AVL trees, stats, merge, and stats aggregation. Requirements:

1. Ase avl.h and avl.c from the question 1

2. Adapt and modify markstats.h and markstats.c from a7q2. Add the following two functions to markstats.h and markstats.c

3. void merge_tree(TNODE **rootp1, TNODE **rootp2) this merges data from AVL tree rootp2 into AVL tree rootp1.

4. void merge_data(MARKS *ds1, MARKS *ds2) this merges two trees of ds1 and ds2 using the merge_tree function and aggregates the statistics summaries.

Use the provided test program a8q2.c, and data sets marks.txt.1, marks.txt.1 to test the above functions.

public test

gcc avl.c markstats.c a8q2.c -o a8q2

a8q2 marks.txt.1 marks.txt.2 report.txt

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#include<string.h>#include "avl.h"

// A utility functions

int max(int a, int b)

{

return (a > b)? a : b;

}

int height(TNODE *np)

{

if (np != NULL) {

return np->height;

}

return 0;

}

int balance_factor(TNODE* np) {

if (np != NULL) {

return height(np->left) - height(np->right);

}

return 0;

}

int is_avl(TNODE *root) {

if (root != NULL) {

int bf = balance_factor(root);

if (bf >= 2 || bf <= -2) {

return 0;

}

}

return 1;

}

TNODE *rotate_right(TNODE *y)

{

TNODE *t = y->left;

TNODE *p = t->right;

t->right = y;

y->left = p;

y->height = max(height(y->left), height(y->right)) + 1;

t->height = max(height(t->left), height(t->right)) + 1;

return t;

}

TNODE *rotate_left(TNODE *x)

{

TNODE...

By purchasing this solution you'll be able to access the following files:

Solution.zip.