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

Question

我的代码是

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

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

             7
            / \
           4   8
          / \   
         1   5

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

Answer 1

首先，对不起我的英语。

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

所以，有树解决方案：

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

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

   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)。可以肯定的是，你会得到堆栈溢出。

3. 您必须交换节点的值，然后认为节点已被交换。在旋转的标准实现中，我们有这样的图片： 在使用交换的旋转中，我们得到这个（=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;
   }
   

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