C++樹AVL餘額

Question

我跑到了我的樹的餘額部分的問題。遞歸插入後調用checkBal。如果我嘗試添加5,2和4，它將檢查2的平衡，並繼續回到5，然後進入rightLeft的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

我弄了一會兒之後就搞定了。我的解決方案如下。

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

應該是，

rotateRight(locRoot->right); 

，但它仍然是一個錯誤的執行。 = p

對於左側和右側，您應該有不同的實現。
嘗試看wikipedia animation。