C++ tree AVL balance

Question

I've run in to an issue with the balance part of my tree. I have checkBal called after a recursive insertion. If I try to add 5, 2 and 4 it checks the balance of 2 and continues back up to 5 then goes into rotateLeft part of the right rotate which is correct. But the rotateLeft function errors on the second line.

What is wrong with this implementation? I've searched all over and compared what I did to the way people talk about how it's done. I finally got everything working. I was forgetting to set N to K at the end.

//==============================================================================
//===== Set Balance ============================================================
sNode<T>* checkBal(sNode<T> *locRoot)
{
    // Make sure to check the children are balanced as well.
    if (locRoot->left != NULL)
        locRoot->left = checkBal(locRoot->left);
    if (locRoot->right != NULL)
        locRoot->right = checkBal(locRoot->right);

    if(getHeight(locRoot->left) - getHeight(locRoot->right) > 1)
    {
        if(getHeight(locRoot->left->right) > getHeight(locRoot->left->left))
            locRoot->left = rotateRight(locRoot->left);
        locRoot = rotateLeft(locRoot);
    }
    else if(getHeight(locRoot->right) - getHeight(locRoot->left) > 1)
    {
        if(getHeight(locRoot->right->left) > getHeight(locRoot->right->right))
            locRoot->right = rotateLeft(locRoot->right);
        locRoot = rotateRight(locRoot);
    }
    updateHeights(locRoot);
    return locRoot;
}
    /*
        Extream cases of balancing a tree requires a double rotation
            A
             \
              D
             /
            B

        'A' is the current root
        If right->left (grandchild) is larger then the right->right (grandchild)
        First Right rotate the child then left rotate the parent


        left > right by 2 or more
            left.left < left.right  (Double Right Rotation)
            left.left >= left.right (Single Right Rotation)
        right > left by 2 or more
            right.right < right.left (Double Left Rotation)
            right.right >= right.left (Single Left Rotation)
    */

sNode<T>* rotateRight(sNode<T> *N) const
{
/*
      N           K
     / \         / \
   (a)  K  =>   N  (c)
       / \     / \
     (b) (c) (a) (b)
*/
    // K is going to be our new Parent
    // Move (c) from K->right to N->left
    // Set K->right to be N
    // Return the new parent node to update the one above.
    sNode<T> *K = N->right;
    N->right = K->left;        
    K->left = N;
    return N = K;
}

Answer 1

I got it working after messing around with it a little while. My solution is below.

//==============================================================================
//===== AVL Balance ============================================================
sNode<T>* checkBal(sNode<T> *locRoot)
{
    // Go all the way down to the leaf nodes.
    if (locRoot->left != NULL)
        locRoot->left = checkBal(locRoot->left);
    if (locRoot->right != NULL)
        locRoot->right = checkBal(locRoot->right);

    // Before we do anything lets update the parent/child heights
    updateHeights(locRoot);

    if(getHeight(locRoot->left) - getHeight(locRoot->right) > 1)
    {
        // If it needs a double left rotate first rotate the left child right
        if(getHeight(locRoot->left->right) > getHeight(locRoot->left->left))
            locRoot->left = rotateRight(locRoot->left);
        locRoot = rotateLeft(locRoot);
    }
    else if(getHeight(locRoot->right) - getHeight(locRoot->left) > 1)
    {
        // If it needs a double right rotate first rotate the right child left
        if(getHeight(locRoot->right->left) > getHeight(locRoot->right->right))
            locRoot->right = rotateLeft(locRoot->right);
        locRoot = rotateRight(locRoot);
    }
    // Update the new heights
    updateHeights(locRoot);
    return locRoot;
}
    /*
        Extream cases of balancing a tree requires a double rotation
            A
             \
              D
             /
            B

        'A' is the current root
        If right->left (grandchild) is larger then the right->right (grandchild)
        First Right rotate the child then left rotate the parent


        left > right by 2 or more
            left.left < left.right  (Double Right Rotation)
            left.left >= left.right (Single Right Rotation)
        right > left by 2 or more
            right.right < right.left (Double Left Rotation)
            right.right >= right.left (Single Left Rotation)
    */

sNode<T>* rotateRight(sNode<T> *N) const
{
/*
      N           K
     / \         / \
   (a)  K  =>   N  (c)
       / \     / \
     (b) (c) (a) (b)
*/
    // K is going to be our new Parent
    // Move (c) from K->right to N->left
    // Set K->right to be N
    // Return the new parent node to update the one above.
    sNode<T> *K = N->right;
    N->right = K->left;        
    K->left = N;
    return N = K;
}

sNode<T>* rotateLeft(sNode<T> *N) const
{
/*
         N            K
    / \          / \
       K  (a)  =>  (b)  N
      / \              / \
    (b) (c)          (c) (a)
*/
    sNode<T> *K = N->left;
    N->left = K->right;        
    K->right = N;
    return N = K;
}

Answer 2

rotateRight(locRoot->left);

should be,

rotateRight(locRoot->right);

but it's still a wrong implementation. =p

You should have a different implementation for left side of root and for right side.
Try to look wikipedia animation.