c++avl-treetree-balancing

C++ tree AVL balance


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

Solution

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