48

私は、Sedgewick によって記述された 2 つのモード、Bottom-Up 2-3 または Top-Down 2-3-4 のいずれかで動作できる LLRB パッケージを実装しています(コード- 改善されたコードですが、2-ここに3 つのツリーがあります。RS のポインターに感謝します)。

Sedgewick は、2-3-4 モードについて多くの時間を費やしていますが、2-3 モードのツリー操作について非常に明確に説明しています。彼はまた、挿入中の色反転の順序を単純に変更するだけで、ツリーの動作がどのように変化するかを示しています (2-3-4 の場合は下方向に分割するか、2-3 の場合は上方向に分割します)。

private Node insert(Node h, Key key, Value value)
{
    if (h == null)
        return new Node(key, value);

    // Include this for 2-3-4 trees
    if (isRed(h.left) && isRed(h.right)) colorFlip(h);

    int cmp = key.compareTo(h.key);

    if (cmp == 0)     h.val = value;
    else if (cmp < 0) h.left = insert(h.left, key, value);
    else              h.right = insert(h.right, key, value);

    if (isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);

    // Include this for 2-3 trees
    if (isRed(h.left) && isRed(h.right)) colorFlip(h);

    return h;
}

ただし、彼は次のように 2-3-4 LLRB での削除についてごまかしています。

次のページのコードは、LLRB 2 ～ 3 ツリーの delete() の完全な実装です。これは、トップダウンの 2-3-4 ツリーへの挿入に使用されるアプローチの逆に基づいています。検索パスの途中で回転とカラー フリップを実行して、検索が 2 ノードで終わらないようにします。一番下のノードを削除できるようにします。メソッド fixUp() を使用して、insert() コードの再帰呼び出しに続くカラー フリップと回転のコードを共有します。fixUp() を使用すると、検索パスに沿って右寄りの赤いリンクとバランスの取れていない 4 つのノードを残すことができ、これらの条件がツリーの途中で修正されることが保証されます。(このアプローチは 2-3-4 ツリーでも効果的ですが、検索パスから外れた右側のノードが 4 ノードの場合は余分な回転が必要です。 )

彼の delete() 関数:

private Node delete(Node h, Key key)
{
    if (key.compareTo(h.key) < 0)
        {
            if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
            h.left = delete(h.left, key);
        }
    else
        {
            if (isRed(h.left))
                h = rotateRight(h);
            if (key.compareTo(h.key) == 0 && (h.right == null))
                return null;
            if (!isRed(h.right) && !isRed(h.right.left))
                h = moveRedRight(h);
            if (key.compareTo(h.key) == 0)
                {
                    h.val = get(h.right, min(h.right).key);
                    h.key = min(h.right).key;
                    h.right = deleteMin(h.right);
                }
            else h.right = delete(h.right, key);
        }
    return fixUp(h);
}

私の実装では、2 ～ 3 ツリーのすべてのツリー操作に対して LLRB 2 ～ 3 の不変条件が正​​しく維持されますが、2 ～ 3 ～ 4 ツリーの右側削除のサブクラスでは失敗します (これらの削除の失敗により、右寄りの赤いノードが発生しますが、雪だるま式にツリーの不均衡と最後に null ポインターの逆参照)。LLRB ツリーを説明し、いずれかのモードでツリーを構築するためのオプションを含むコード例の調査から、2-3-4 LLRB からの削除を正しく実装していないようです (つまり、Sedgewick の java上とここ）。

「検索パスから離れた右側のノードが 4 ノードの場合に余分なローテーションを行う」という彼の意味を正確に理解するのに苦労しています。おそらくこれは左回転ですが、いつ、どこで？

fixUp() を呼び出す前、または fixUp 関数の最後に、4 ノードの同等物 (すなわち RR ノード) または右寄りの 3 ノード同等物 (BR ノード) を通過して左に回転すると、同じ不変の矛盾が発生します。 .

これは、私が見つけた最小の失敗例のツリー状態です (0 からそれぞれの最大値までの要素を順次挿入することによって生成されます)。

ツリーの最初のペアは、要素 15 の削除前の不変適合状態から、削除後の明らかに壊れた状態への遷移を示しています。

0..15 を含む 2-3-4 LLRB

項目15削除後の状態

2 番目は基本的に上記と同じですが、0..16 のうち 16 が削除されています (15 を削除すると同じトポロジになります)。不変矛盾がルートノードを越えることに注意してください。

0..16 を含む 2-3-4 LLRB

項目16削除後の状態

重要なのは、ツリーを下ってターゲット ノードに移動する際に生成された違反を元に戻す方法を理解することです。次の 2 つのツリーは、上の最初のツリーがそれぞれ左右に移動した後 (削除せず、fixUp() で元に戻す前) にどのように見えるかを示しています。

fixUp なしで「-1」を削除しようとした後: fixUp なしで「-1」を削除しようとした後

fixUp なしで '16' を削除しようとした後: fixUp なしで '16' を削除しようとした後

ノードに赤い右の子しかない場合にウォークを左に回転しようとすることは解決策の一部であるように見えますが、2 つの赤い右の子が連続して正しく処理されず、両方の子が赤の場合に FlipColor を前に付けます。状況はさらに改善されるように見えますが、依然としていくつかの不変条件に違反したままです。

右の子の右の子が赤で、兄弟が黒かどうかをさらに確認し、これが真の場合は左に回転すると、1 回だけ失敗しますが、この時点では、新しいエピサイクルではなく、新しい理論が必要なように感じます.

何か案は？

参考までに、私の実装はこちらから入手できます(いいえ、Java ではありません)。

ファローアップ：

私がこれに興味を持った理由の 1 つは、2-3-4 LLRB ツリーよりも 2-3 LLRB ツリーの方が効率的であるという多くの主張を確認するためでした。私のベンチマークでは、挿入と削除でこれが確認されています (2 ～ 3 の方が約 9% 高速です)。

次の時間は代表的なものであり、実行全体で一貫しています。

BU23:
BenchmarkInsert        1000000        1546 ns/op
BenchmarkDelete        1000000        1974 ns/op
BenchmarkGet           5000000         770 ns/op

TD234:
BenchmarkInsert        1000000        1689 ns/op
BenchmarkDelete        1000000        2133 ns/op
BenchmarkGet           5000000         753 ns/op

1 列目はベンチ名、2 列目は操作数、3 列目は結果です。i5M 2.27 のベンチマーク。

2 ～ 3 本の木と 2 ～ 3 ～ 4 本の木の枝の長さを見てきましたが、検索の違いを説明するものはほとんどありません (ルートからノードまでの平均距離と、それぞれ 10000 個のランダムな挿入を持つ 1000 本の木の SD):

Means:
TD234 leafs  BU23 leafs 
 12.88940     12.84681 
TD234 all    BU23 all 
 11.79274     11.79163 

StdDev:
TD234 leafs  BU23 leafs 
 1.222458     1.257344 
TD234 all    BU23 all 
 1.874335     1.885204
4

1 に答える 1

10

更新および検証済み

これをテストする上で重要なのは、実装が存在しないノードまたは以前に削除されたノードの削除をサポートしていないことです。私の作業ソリューションが「壊れた」理由を理解するのに時間がかかりすぎました。これは、キーの予備検索を実行し、キーがツリーにまったくない場合は false を返すことで修正できます。その解決策は、下部のリンクされたコードで採用されています。

Sedgewick が公開されている 2-3-4 削除の削除を書いたようには見えません。彼の結果は、特に 2 ～ 3 本の木を扱っています (彼は 2 ～ 3 ～ 4 本の木について簡単に言及しているだけで、その平均経路の長さ (したがって検索コスト) は他の赤黒木と区別がつかないためです)。 2-3ケース）。他の誰も簡単に見つけられるようには見えないので、問題をデバッグした後に私が見つけたものは次のとおりです。

まず、Sedgewick のコードを使用して、古いビットを修正します。ここのスライド(31 ページ) では、彼のコードは、バランスではなく、2 つの左側の赤を連続して配置することによって行われた 4 つのノードの古い表現をまだ使用していることがわかります。2-3-4 削除ルーチンを作成するための最初のビットは、これを修正して、後で修正を検証するのに役立つサニティ チェックを実行できるようにすることです。

private boolean is234(Node x)
{         
   if (x == null)
      return true;
   // Note the TD234 check is here because we also want this method to verify 2-3 trees
   if (isRed(x.right))
      return species == TD234 && isRed(x.left);

   if (!isRed(x.right))
      return true;

   return is234(x.left) && is234(x.right);
}

これを取得すると、いくつかのことがわかります。1 つ目は、論文から、2-3-4 ツリーを使用する場合、途中で 4 つのノードが壊れてはならないことがわかります。2 つ目は、検索パスに右 4 ノードの特殊なケースがあります。言及されていない 3 番目の特別なケースがあります。それは、ツリーに戻るときに、h.right.left赤くなった場所に行き着く可能性があり、左に回転するだけで無効になる可能性があることです。これは、論文の 4 ページの挿入で説明されているケースのミラーです。

必要な 4 ノードのローテーション修正は次のとおりです。

    private Node moveRedLeft(Node h)
    {  // Assuming that h is red and both h.left and h.left.left
       // are black, make h.left or one of its children red.
       colorFlip(h);
       if (isRed(h.right.left))
       { 
          h.right = rotateRight(h.right);

          h = rotateLeft(h);
          colorFlip(h);

          if (isRed(h.right.right) )
             h.right = rotateLeft(h.right);
       }
      return h;
    }

これにより、2-3-4 の分割が削除され、3 番目の特殊なケースの修正が追加されます。

private Node fixUp(Node h)
{
   if (isRed(h.right))
   {      
      if (species == TD234 && isRed(h.right.left))
         h.right = rotateRight(h.right);
      h = rotateLeft(h);
   }

   if (isRed(h.left) && isRed(h.left.left))
      h = rotateRight(h);

   if (species == BU23 && isRed(h.left) && isRed(h.right))
      colorFlip(h);

   return setN(h);
}

最後に、これをテストして動作することを確認する必要があります。それらは最も効率的である必要はありませんが、これのデバッグ中にわかったように、予想されるツリーの動作で実際に動作する必要があります (つまり、重複データを挿入/削除しないでください)! テストヘルパーメソッドでこれを行いました。コメントされた行は、デバッグ中にそこにありました。ツリーを壊して、明らかな不均衡がないかチェックしました。100000 ノードでこの方法を試しましたが、問題なく動作しました。

   public static boolean Test()
   {
      return Test(System.nanoTime());
   }
   public static boolean Test(long seed)
   {
      StdOut.println("Seeding test with: " + seed);
      Random r = new Random(seed);
      RedBlackBST<Integer, Integer> llrb = new RedBlackBST<Integer,Integer>(TD234);
      ArrayList<Integer> treeValues = new ArrayList<Integer>();
      for (int i = 0; i < 1000; i++)
      {
         int val = r.nextInt();
         if (!treeValues.contains(val))
         {
            treeValues.add(val);
            llrb.put(val, val);
         }
         else
            i--;
      }
      for (int i = 0; i < treeValues.size(); i++)
      {
         llrb.delete(treeValues.get(i));
         if (!llrb.check())
         {
            return false;
         }
//         StdDraw.clear(Color.GRAY);
//         llrb.draw(.95, .0025, .008);
      }
      return true;
   }

完全なソースはここにあります。

于 2012-07-09T07:58:28.603 に答える