java - 如何在展开树中旋转节点？

Question

我的代码是

private Node rotateLeftChild(Node n)
{
    Node o = n.left;
    n.left = o.right;
    o.right = n;
    return o;
}

当我调用它在根部旋转这样的树时：

它删除了 4 和 1 并使 5 成为 7 的左根。我尝试将该方法设置为 void 方法，但这似乎也不起作用。我这样做是完全错误的吗？

score 2 · Accepted Answer

首先，对不起我的英语。

回答一个问题 - 为什么节点 4 消失很简单。7 有父节点（或 7 是根节点）。当您调用 rotateLeftChild 时，7 的父母仍然“认为”他的孩子是 7，而不是 4：

实拍图

所以，有树解决方案：

链接到父节点并更新它。在 leftRotation 的最后，进行赋值，n.Parent.Left = o 或 n.Parent.Right = o（分别为 if (n.Parent.Left == n) 或 (n.Parent.Right == n)）。当然，当您旋转根的子节点时，您必须更新指向树根的链接。

当您添加 | 插入 | 查找节点，将所有先前的（父）节点保存在堆栈中，然后在旋转后您必须更新指向其子节点的链接。或者像这样使用递归：

private Splay(Node parent, Node cur, Node n, bool canMoveUpTwice = false) {
    if (cur.Value > n.Value)
        Splay(cur, cur.Left, n, !canMoveUpTwice);
    else
        Splay(cur, cur.Right, n, !canMoveUpTwice);

    if (canMoveUpTwice)
        MoveUpTwice();
    else
        MoveUpOnce();

    if (parent.Left == cur)
        parent.Left = n;
    else
        parent.Right = n;

    if (Parent == null)
        tree.Root = n;
}

如何使用。添加节点后，您必须运行 Splay(root, newNode)。可以肯定的是，你会得到堆栈溢出。

您必须交换节点的值，然后认为节点已被交换。在旋转的标准实现中，我们有这样的图片：在使用交换的旋转中，我们得到这个（=x 表示“节点具有值 X”）：所以，我们有这个代码
```
private rotateLeftChild(Node q) {
    Node p = q.Left;

    Swap(q.Value, p.Value); 

    A = p.Left;
    B = p.Right;
    C = q.Right;

    q.Left  = A;
    q.Right = p;

    p.Left  = B;
    p.Right = C;
}
```

请注意：代码尚未经过测试。

java - 如何在展开树中旋转节点？

1 回答 1

Related