8
\$\begingroup\$

I have an assignment for which I need to write an AVL tree. This is what I have written so far. It works on all of my tests, but suddenly fails in checking system with TL (time limit exceeded).

Personally I think there could be a bug with input data in test (although I have already solved this problem with Cartesian tree).

struct node
{
    int key;
    int data;    

    int height;

    struct node* left;
    struct node* right;
};

typedef struct node node;

node* new_node(int key, int data)
{
    node* p = malloc(sizeof(*p));

    p -> key    = key;
    p -> data   = data;
    p -> height = 1;
    p -> left   = NULL;
    p -> right  = NULL;

    return p;
}

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

int height(node* p)
{
    return p ? p -> height : 0;
}

void recalc(node* p)
{
    p -> height = 1 + max(height(p -> left), height(p -> right));
}

node* rotate_right(node* p)
{
    node* q = p -> left;

    p -> left = q -> right;
    q -> right = p;

    recalc(p);
    recalc(q);

    return q;
}

node* rotate_left(node* p)
{
    node* q = p -> right;
    p -> right = q -> left;
    q -> left = p;

    recalc(p);
    recalc(q);

    return q;
}

node* balance(node* p)
{
    recalc(p);

    if ( height(p -> left) - height(p -> right) == 2 )
    {
        if ( height(p -> left -> right) > height(p -> left -> left) )
            p -> left = rotate_left(p -> left);
        return rotate_right(p);
    }
    else if ( height(p -> right) - height(p -> left) == 2 )
    {
        if ( height(p -> right -> left) > height(p -> right -> right) )
            p -> right = rotate_right(p -> right);
        return rotate_left(p);
    }

    return p;
}

node* search(node* p, int key)
{
    if ( !p )
        return NULL;

    if ( key < p -> key )
        return search(p -> left, key);
    else if ( key > p -> key )
        return search(p -> right, key);
    else
        return p;        
}

node* insert(node* p, int key, int data)
{
    if ( !p )
        return new_node(key, data);

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

    return balance(p);
}

node* find_min(node* p)
{
    if ( p -> left != NULL )
        return find_min(p -> left);
    else
        return p;
}

node* remove_min(node* p)
{
    if ( p -> left == NULL )
        return p -> right;

    p -> left = remove_min(p -> left);
    return balance(p);
}

node* remove_item(node* p, int key)
{
    if ( !p )
        return NULL;

    if ( key < p -> key )
        p -> left = remove_item(p -> left, key);
    else if ( key > p -> key )
        p -> right = remove_item(p -> right, key);
    else
    {
        node* l = p -> left;
        node* r = p -> right;
        free(p);

        if ( r == NULL )
            return l;

        node* m = find_min(r);
        m -> left = l;
        m -> right = remove_min(r);        

        return balance(m);
    }

    return balance(p);
}

void free_tree(node* p)
{
    if ( !p )
        return;

    free_tree(p -> left);
    free_tree(p -> right);
    free(p);
}

int main(void)
{
    node* root = NULL;

    char c;
    int k, d;
    while ( scanf("%c", &c) && c != 'F' )
    {
        if ( c == 'A' )
        {
            scanf("%d %d", &k, &d);
            root = insert(root, k, d);
        }
        else if ( c == 'S' )
        {
            scanf("%d", &k);
            node* n = search(root, k);
            if ( n ) 
                printf("%d %d\n", n -> key, n -> data);
        }
        else if ( c == 'D' )
        {
            scanf("%d", &k);
            root = remove_item(root, k);
        }
    }

    free_tree(root);

    return 0;
}
\$\endgroup\$
1
6
\$\begingroup\$

Overall, this seems to be some well-crafted code that is clear, concise and doesn't leak memory. Here are some things that may help you improve your code.

Use the appropriate #includes

In order to compile and link, this code requires the following two lines:

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

For the program to be complete, these should be listed, too.

Fix node deletion

There is a problem with the remove_item code. In particular, if we construct a tree with just three items and then attempt to remove the root, the current code causes a crash because the left subtree is added before the call to remove_min(r). To fix that, simply swap the lines in remove_item so that this part of the code looks like this:

    node* m = find_min(r);
    m -> right = remove_min(r);        
    m -> left = l;

This is likely to be the problem that causes the time limit to be exceeded.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Actually, I solved my problem yesterday. Matter of time limit was that there were a lot of spaces after each query, so the while were simply going on eating one space at a time. So I just needed to read all those spaces at once. \$\endgroup\$ – justanothercoder Dec 7 '14 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.