AVL Tree left and right rotation C

Question

I need to implement a left and right rotation on AVL tree.

The struct is :

typedef struct tree mynode;   // 
struct tree{                    // tree node struct
int value;
int key;
char color;
struct tree *left;
struct tree *right;
};

My problem is that when, after the right rotation, I try to access to node->left the program crashes with a segmentation fault. I think the rotation is good, but I feel like if it doesn't save the pointer...I mean I do the rotation but it isn't saved on the left sub-tree. Right rotation :

mynode* rightRotate(mynode* root)
{
    mynode*tmp=(mynode*) malloc(sizeof(mynode));
    tmp->value=root->value;
    tmp->key=root->left->key;
    tmp->left=NULL;
    tmp->right=NULL;
    root->value=root->left->value;

    if(root->right==NULL)
      tmp->right=NULL;
    else if (root->right!=NULL)
      tmp->right=root->right;
    else printf("Error with right Rot\n");
    if (root->left->right==NULL)
      tmp->left=NULL;
    else if  (root->left->right!=NULL)
      tmp->left=root->left->right;
    else printf("Error with right Rot\n");
    root->right=tmp;

    mynode*tmp2;
    tmp2=root->left;
    root->left=root->left->left;
    free(tmp2); //freed old node
    printf("Rotation completed\n");
    return root;
}

I use the function below just to check the first 3 insertions, I want a tree with both sub-tree that's why it checks if left or right are NULL.

Right rotate is called by :

mynode* checkRotate(mynode*root)
{
    if(root->left==NULL) 
    {
        printf("Left rotate\n");
        root=leftRotate(root);
        return root; //to ensure parent-parent exists
    }
    else if (root->right==NULL) 
    {
        printf("Right rotate\n");
        root=rightRotate(root);
        return root; //to ensure parent-parent exists
    }
    else return NULL;
    return root;
}

That is called by :

...some code...
root=checkRotate(root);
right->left->color=RED;//crashes here
...some code...

And obviously left rotate has the same problem while checking the right sub-tree instead the left one.

EDIT : New right rotate :

void rightRotate(mynode*root,mynode*son)
{
    if (son==NULL)
    {
        printf("Cannot rotate, son is null\n");
        return;
    }
    else 
    {
        if(son->left==NULL) 
        {
            printf("No left child, returning\n");
            return;
        }
        else 
        {
            mynode* F = son;
            mynode* D = son->left;
            if(son->left->right==NULL)
                son->left=NULL;
            else if (son->left != NULL)
                son->left = son->left->right;
            else {
                printf("Weird in right rotate\n");
            }
            D->right=son;
            if(root->right==son)
            {
                root->right=D;
                return ;
            }
            else if (root->left==son)
            {
                root->left=D;
                return ;
            }
            else 
            {
                printf("Error while setting new son in right balance\n");
                return ;
            }
            printf("Generic error in right balance\n");
            return;
        }
    }
}

Answer 1

Here's a picture that shows the changes needed for a right rotation:

The rotation is accomplished by replacing the red connections with the green connections.

The connection at the top could be from higher node in the tree (F is either the left child or the right child of that node). Or it is the connection from the tree's root pointer (if F is the root node). To keep things simple, the first parameter to rightRotate should be a pointer to a pointer to a node. That way, it doesn't matter what pointer points to F, the code just updates that pointer to point to D.

In the code below, the first line verifies that the arguments are valid. The first argument (which points to the pointer that points to F) must not be NULL. Also, both F and D must exist.

An assert is used to check the parameters to simplify debugging. Invalid parameters indicate a problem in the calling code. The assert will cause a debugger to stop at that line (if the parameters are invalid). Going up one level in the call stack allows the calling code to be examined.

Note that node E is optional, i.e. D might not have a right child. If E doesn't exist then D->right is NULL, and the code will set F->left to NULL. No special handling is needed for E.

Here's what the code looks like:

void rightRotate(mynode **parentPtr, mynode *child)
{
    // make sure the arguments are valid for a right rotation
    assert(parentPtr != NULL && child != NULL && child->left != NULL);

    // save the three node addresses involved in the rotation
    mynode *F = child;
    mynode *D = F->left;
    mynode *E = D->right;

    // perform the rotation
    *parentPtr = D;
    D->right = F;
    F->left = E;
}