avl tree - C++ AVLTree Rotation

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) 按预期移动。

在对样本数据进行旋转之前，预计应将不平衡树排列为3节点指向root。 然后root->right指向5，root->right->right指向10。 root->right->left应该是nullptr的，root->left也应该是nullptr的。

如果不是这种情况，那么要么AVL插入算法实现不正确，要么设计要求与预期不同(例如维基百科上的AVL树，C++中的数据结构和算法分析(第3版([精装]由Mark Allen Weiss撰写，AVL树教程由Julienne Walker撰写(。

关于平衡树的运动，最终结果是root指向5，root->left指向3，root->right指向10，root传入指针的右指针将设置为指向本地pB指针的左指针(见下文(， pB 的左指针将指向传入的指针root，root将设置为指向局部变量pB(在本例中最初设置为root->right指针(。

使用上面的示例数据，修改函数的主体。 请注意，这与上面原始帖子中返回 Node 副本的 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;
}