To get some practice with AVL Trees. As a compromise, he\'s decided that it\'s g

Question

To get some practice with AVL Trees. As a compromise, he's decided that it's good enough if the students just implement the insert function instead of both the insert and delete. To make his assignment easy to grade, he'll simply give students a sequence of inserts to perform and then ask the students to output a pre-order traversal after each insertion to make sure that the structure of the tree is correct.

In Computer Science I, you implemented a regular binary search tree. Due to your busy schedule, you've decided that it would be best if you could simply reuse this code without any changes. You realize that your code would ONLY work for Arup's assignment on the cases where NO rebalancing or rotations occur. Thus, you've come up with a nefarious plan. You will infiltrate Arup's office by bribing the janitorial staff, steal his test cases and remove all of the cases where a rebalancing would have been required.

For this program, read in a sequence of inserts into an AVL tree and simply determine if performing those inserts ever requires a rebalancing. If so, print out "REMOVE", otherwise print out "KEEP".

Input

The first line of input will contain a single positive integer, T (T ? 100), the number of input cases. The following T lines will contain each of the test cases, one test case per line. For each test case, the first integer on the line, n (n < 1024), will represent the total number of inserts for the test case. The following distinct n positive integers on the line represent the values to insert into the AVL tree, in the order that they are given. All of these values will be separated by a space. (There may or may not be a space at the end of each of these lines.)

Output

For each test case, start the output with a header of the following form:

Tree #k:

where k is the number of the test case, starting with 1.

Follow this with a space and either the string "REMOVE" or "KEEP", based on the cases described above.

Sample Input

2

3 1 2 3

7 4 2 6 7 3 1 5

Sample Output

Tree #1: REMOVE

Tree #2: KEEP

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>

int ans;

struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
};

int max(int a, int b);

int height(struct node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

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;
    return(node);
}
struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;

    x->right = y;
    y->left = T2;

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

    return x;
}

struct node *leftRotate(struct node *x)
{
    struct node *y = x->right;
    struct node *T2 = y->left;

    y->left = x;
    x->right = T2;

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

    return y;
}

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)
{
    if (node == NULL)
        return(newNode(key));

    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

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

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
    {
        ans=1;
        return rightRotate(node);
    }

    if (balance < -1 && key > node->right->key)
    {
        ans=1;
        return leftRotate(node);
    }

    if (balance > 1 && key > node->left->key)
    {
        ans=1;
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && key < node->right->key)
    {
        ans=1;
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

int main()
{
    int t,i;
    scanf("%d",&t);
    i=1;
    while(i<=t)
    {
        struct node *root = NULL;

        int n,j,val;
        scanf("%d",&n);
        ans=0;

        for(j=0;j<n;j++)
        {
            scanf("%d",&val);
            root = insert(root, val);
        }

            if(ans == 1)
                printf("Tree #%d: REMOVE ",i);
            else
                printf("Tree #%d: KEEP ",i);

        i++;
    }

    return 0;
}

This is the required in C.

Cheers! :)

Comment for any doubts.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.