3

私は自分で赤黒木を書くことに取り組んでいます。しかし、ルートを回転させる回転をテストすると、参照が多少失われます。

ツリー構造：

          45             
        /    \
      40x      70        
     /  \     /
    7   41   50           
   / \
  6  39

回転ロジックは次のように述べています。「X（つまり40）を上げる方向に、45（ルート）を上にして回転します。」

つまり、これは右回転を意味し、結果は次のようになります。

     40x  
    /   \
   7     45
 / \     / \
 6  39  41  70
           /
          50

ノード45が祖父母で、7が親で、41が現在であると仮定します。（順序が意味をなさないことはわかっていますが、無視してください。これは、すでに1回回転したためです）

コード：

  //current is node 45
    //parent is node 7
    //grandparent is node 45 (root)

    //first detach cross node (i.e. 41)
    Node crossNode2 = grandparent.left.right;
    grandparent.left.right = null; //detach


                   45             
                /     \
              40x      70        
             /  \      /
            7   null   50           
           / \
          6  39

    grandparent.left = null;




                   45             
                 /    \
               null   70        
                      /
                    50           

    current.right = grandparent;

          40
        /    \
      7        45
     /  \     /  \
   6    39   null 70
                  /
                 50

    grandparent.left = crossNode2; //attach


         40  
        /   \
       7     45
     / \     / \
     6  39  41  70
               /
              50

しかし、どういうわけかこのコードは機能しません。私がテストしたとき：

preorder
45, 39, 70, 50
breadth-first
45, 39, 70, 50

したがって、結果は実際には次のようになります。

  45
 /  \
39  70
     /
    50

誰かが私のローテーションコードの何が問題になっているのかヒントを教えてもらえますか？

4

2 に答える 2

3

ノードQで右回転を実行する手順：

  1. P=Qの左の子とします。
  2. Qの左の子=Pの右の子
  3. 親の子としてPがQに置き換わります
  4. Pの右の子=Q

提供されたコードに太字のステップがありません。あなたの問題は、ルートノードを含む回転を特殊なケースとして扱っていることだと思います。明らかに、Qがルートで、その親がである場合、これを行うことはできませんnull。正しいノードがルートである「ヘッド」ノードを作成してみてください。これにより、ルートを含むローテーションが通常のアルゴリズムを使用して機能するようになります。

public static void rotateRight(Node node) {
    assert(!node.isLeaf() && !node.left.isLeaf());
    final Node child = node.left;
    node.setLeft(child.right);
    if (node.isRightChild())
         node.parent.setRight(child);
    else node.parent.setLeft(child);
    child.setRight(node);
}

それをノード化し、参照を更新し続けるだけでなく、setRight更新setLeftします。呼び出しはちょうどすることができます。parentrightleftnode.isRightNode()(node.parent.right == node)

于 2010-07-27T03:24:30.520 に答える
0

Gunslinger47の回答に基づいて、左回転バージョンもテストしました。コードは正常に機能します。（そうでない場合はお知らせください。）

私のウェブサイトにも記載されています:)

http://masatosan.com/btree.jsp

public static void rotateLeft(Node node) {
    assert(!node.isLeaf() && !node.right != null);
    final Node child = node.right;
    node.setRight(child.left);
    if(node.isLeftChild()) {
        node.parent.setLeft(child);
    }
    else {
        node.parent.setRight(child);
    }
    chlid.setLeft(node);
}
于 2010-07-27T18:40:45.277 に答える