C++树AVL平衡

Question

我的树的平衡部分遇到了问题。我在递归插入后调用了 checkBal。如果我尝试添加 5、2 和 4，它会检查 2 的余额并继续返回到 5，然后进入右旋转的 rotateLeft 部分，这是正确的。但是第二行的 rotateLeft 函数出错。

这个实现有什么问题？我到处搜索并将我所做的与人们谈论它是如何完成的方式进行比较。我终于让一切正常了。我忘记在最后将 N 设置为 K。

//==============================================================================
//===== 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

rotateRight(locRoot->left);

应该是，

rotateRight(locRoot->right);

但它仍然是一个错误的实现。 =p

根的左侧和右侧应该有不同的实现。
试试看wikipedia animation .