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の親はまだ彼の子供が4ではなく7であると「考えている」：

したがって、ツリーソリューションがあります：

1. 親ノードへのリンクを作成し、更新します。leftRotation の最後で、割り当て n.Parent.Left = o または n.Parent.Right = o (それぞれ (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;
   }
   

注意: コードはテストされていません。