Click here to Skip to main content
15,898,010 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
C++
struct node
{
    int key ;
    int h;
    node *left;
    node *root;
    node *right;
};


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


int balanceavl(struct node *n)
{
    if (n == NULL)
        return 0;
    return (h(n->left) , h(n->right));


}


node* rightrotate(struct node *y)
{
    struct node *x = y->left;
    struct node *z = x->right;

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

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

    return x;
}


node* leftrotate(struct node *x)
{
    struct node *y = x->right;
    struct node *z = y->left;

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

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

    return y;
}


struct node *remove(struct node *root, int key)
{

    struct node *remove_node;
    if (root == NULL)
    {
        return root;
    }

    if ( key < root->key)
    {
        root->left = remove(root->left, key);

    }
    else if ( key > root->key)
    {
        root->right = remove(root->right,key);

    }
    else {

        if ((root->left == NULL) && (root->right != NULL)){
            remove_node = root->right;
            *root = *remove_node;
            free(remove_node); // this is for free-ing the memory

        } else if ((root->right == NULL)  && (root->left != NULL)){
            remove_node = root->left;
            *root = *remove_node;
            free(remove_node);

        } else if ((root->right == NULL)  && (root->left == NULL)){
            remove_node = root;
            root = NULL;

        } else {

            remove_node = successor(root);
            root->key = remove_node->key;
            root->right = remove(root->right, remove_node->key);
        }
    }

    if (root == NULL) {
        return root;
//lr
    if (balanceavl(root) == 2){
        if (balanceavl(root->left) == -1) {
            root->left =  leftrotate(root->left);
            return rightrotate(root);
//ll
        } else if (balanceavl(root->left) == 1) {
            return rightrotate(root);
        }
    }
//rr
    if (balanceavl(root) == -2) {
        if (balanceavl(root->right) == -1) {
            return leftrotate(root);
        }


        //rl
        else if (balanceavl(root->right) == 1)  {
                root->right = rightrotate(root->right);
                return leftrotate(root);
            }
        }
    }

    return root;
}
Posted
Updated 29-Jan-13 3:39am
v2
Comments
CPallini 29-Jan-13 9:42am    
What kind of error do you get? Could you, please, be more precise? After all, we need some help from you...
mahla.r_1993 29-Jan-13 10:04am    
i get this error:

error C3861: 'successor': identifier not found
mahla.r_1993 29-Jan-13 9:46am    
i get this error:

error C3861: 'successor': identifier not found
mahla.r_1993 29-Jan-13 9:59am    
i get this from internet
what is wrong for this ? plz help me!
CHill60 29-Jan-13 10:07am    
Whereabouts on the internet? Looks like you didn't get all of the code you need

1 solution

You're missing the function node* successor(struct node *x), did you copy everything when you got this?

/Fredrik
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900