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))。当然，当你旋转根的 child 时，你必须更新到树根的链接。

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;
   }
   

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