java - 如何旋转伸展树(Splay Tree)中的节点？

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的 parent 仍然“认为”他的 child 是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;
   }
   

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