QuestionQuestion

Objectives
• 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 PreviewSolution 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.

$45.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Computer Science - Other Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats