AVL Tree left and right rotation C

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;
}