C++ AVLTree旋轉

Question

我想用我的AVLTree做一個LeftRotation。我會插入3,5和10，所以它變成了一棵退化的樹。當我遍歷它會給我3, 5, 10，但是當我做輪換時，我只是得到5, 10而不是預期的5, 3, 10。

這與設置a爲b的left分支有關。我會穿過它，我的樹的根將是5，左邊是3，右邊是10，但是當我去遍歷它時顯示左邊爲null。

這裏是我的輪換代碼：

void AVLTree::RotateLeft(Node *root) 
{ 
    Node a = *root; 
    Node b = *root->GetRight(); 
    *root = b; 
    a.SetRight(b.GetLeft()); 
    b.SetLeft(&a); //This is where the problem occurs 
} 

而且我Traversal代碼：

void AVLTree::Traverse(Node *node) 
{ 
    cout << node->GetValue() << ", "; 
    if (node->GetLeft() != nullptr) 
     Traverse(node->GetLeft()); 
    if (node->GetRight() != nullptr) 
     Traverse(node->GetRight()); 
} 

提前感謝！

編輯：更改全部0的爲nullptr，感謝您的更正！

Answer 1

如何將root移動到指向新位置時出現問題。如果對此有疑問，請考慮以下兩條陳述。請注意，上述原始代碼中的變量命名約定用於保持一致性。

*root = b; // (1) 
root = &b; // (2) 

在(1)，根指針的內容被修改，以包含存儲在b變量的值。 root的地址沒有以任何方式修改。在(1)完成之後，地址root之前的(1)執行保持不變。

在(2),root現在指向b變量的地址。因爲root指向的地址已被修改，所以root指針的內容現在等於b變量中的值。

我強烈建議逐行通過void AVLTree::RotateLeft(Node *root)函數，並檢查所有變量的地址和內容以查看第一手資料。我對樣本整數數據執行了上述操作的模擬，並且使用(2)按預期移動了指針。

在樣本數據發生旋轉之前，預計應該安排不平衡樹，使節點指向root。然後root->right指向5，並且root->right->right指向10。 root->right->left應該是nullptr，並且root->left也應該是nullptr。

如果這不是這種情況，那麼無論是AVL插入算法被不正確地執行或設計要求是不同的比預期的（例如，維基百科上AVL tree，Data Structures and Algorithm Analysis in C++ (3rd Edition) [Hardcover]由Mark艾倫韋斯AVL Tree Tutorial on Eternally Confuzzled通過茱莉安沃克）。

關於平衡的樹，這裏的最終結果是root點5的root->left點3和root->right點10，在root指針傳遞正確的指針的移動將被設置爲指向左側指針本地pB指針（見下文），指針pB的左指針將指向傳入的root指針，而root將被設置爲指向本地變量pB（最初在本例中設置爲root->right指針）。

使用上面的示例數據，函數的主體被修改。請注意，這與GetRight()和GetLeft()似乎在上述原始帖子中返回節點副本的方式不一致。下面修改的功能體與上面引用的Mark Allen Weiss實現的single AVL rotation with right child一致。由於原始文章沒有高度變量，下面的代碼也沒有。

// 
// The `root` variable is passed as a pointer by reference 
// 
void AVLTree::RotateLeft(Node* & root) 
{ 
    // 
    // This works as long as the GetRight() method returns a pointer, not a Node copy 
    // 
    Node *pB = root->GetRight(); 

    // 
    // In the example values for three nodes, the root->right will become nullptr 
    // 
    root->SetRight(pB->GetLeft()); 

    // 
    // In the example values, the pB->left will point to the node with value of 3 
    // 
    pB->SetLeft(root); 

    // 
    // Move root to point to where pB does (root->right) 
    // 
    root = pB; 
}