19

私はLeft-Lean-Red-Black tree、から学んでいますProf.Robert Sedgewick

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

とのことを理解するようになりましたがinsert、今では2週間で40時間ほど過ごしましたが、それでもLLRBの削除を取得できません。2-3 treeLLRB

誰かが本当に私deletionにのLLRBを説明できますか？

4

3 に答える 3

13

OK、私はこれを試してみます.SOの他の善良な人々が助けてくれるかもしれません. 赤いノードの 1 つの考え方が、

  1. ツリー内に不均衡/新しいノードがある場所、および
  2. どれだけアンバランスか。

これが、すべての新しいノードが赤くなっている理由です。ノードが (ローカルに) バランスが取れている場合、色が反転し、赤みが親に渡されるため、親は兄弟に対して不均衡に見える場合があります。

例として、大きいノードから小さいノードにノードを追加する状況を考えてみましょう。ノード Z から始めます。これは現在ルートであり、黒です。Z の左の子である赤のノード Y を追加します。Z の子として赤の X を追加しますが、2 つの連続する赤があるため、右に回転させて色を変更し、バランスのとれたすべての黒を作成します。 (不均衡なし/「新しいノード」!) Y をルートとするツリー [最初の描画]。次に、W と V をこの順序で追加します。最初は両方とも赤です [2 番目の図] が、すぐに V/X/W が右に回転し、色が反転するため、X だけが赤になります [3 番目の図]。これは重要です。X が赤色であることは、Y の左側のサブツリーが 2 つのノードによってバランスが取れていないことを示します。つまり、左側のサブツリーに 2 つの新しいノードがあることを示します。したがって、赤いリンクの高さは、バランスが取れていない可能性のある新しいノードの数です。

ここに画像の説明を入力

ノードを追加するとき、赤みが常に渡されることに注意してください。カラー フリップでは、2 つの赤の子が黒になり、親が赤く着色されます。基本的に削除が行うことは、このプロセスを逆にすることです。新しいノードが赤であるように、常に赤のノードも削除したいと考えています。ノードが赤くない場合は、最初に赤くします。これは、カラー フリップによって行うことができます (ちなみに、これが、3 ページ目のコードのカラー フリップが実際にはカラー ニュートラルである理由です)。したがって、削除したい子が黒の場合、親の色を反転することで赤にできます。これで、子は確実に赤くなります。

次に対処すべき問題は、削除を開始するときに、削除するターゲット ノードが赤かどうかわからないという事実です。1つの戦略は、最初に見つけることです。ただし、あなたの最初の参照を読んだところによると、そこで選択された戦略は、ツリーを下方向に検索しているときに、検索ノードの前に赤いノードを「押し込む」ことにより、削除されたノードを確実に赤くできるようにすることです。削除するノード。これにより、不要な赤いノードが作成される可能性がありfixUp()、ツリーを遡る途中で手順が解決されます。fixUp()おそらく、通常のLLRBT不変条件を維持します：「連続する赤いノードなし」および「正しい赤いノードなし」。

それが役立つかどうか、またはコードのより詳細な調査に入る必要があるかどうかはわかりません.

于 2013-03-17T03:30:35.973 に答える
0

次の戦略に従って、リーフにない LLRB ツリー内の任意のノードを削除します。

  1. LLRB ツリーを 2-3-4 ツリーに変換します (ツリー全体を変換する必要はなく、ツリーの一部のみを変換する必要があります)。
  2. ノード (削除するノード) の値をその後続ノードに置き換えます。
  3. 後続を削除します。
  4. ツリーを修正します (バランスを回復します。ページの本「アルゴリズム第 4 版」を参照してください435) 436。

葉の値の場合、この値を置き換えるために後継者を使用する必要はありませんが、この値を削除するには、現在のツリーを 2-3-4 ツリーに変換する必要があります。

20このプレゼンテーションのページのスライドhttps://algs4.cs.princeton.edu/lectures/keynote/33BalancedSearchTrees.pdfと、そのページにある書籍「Algorithms 4th edition」437が鍵です。これらは、LLRB ツリーが 2-3 ツリーにどのように変換されるかを示しています。442 ページhttps://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA442の書籍「Algorithms 4th edition」では、ツリーの変換アルゴリズムです。

たとえば54、プレゼンテーションのページhttps://www.cs.princeton.edu/~rs/talks/LLRB/08Dagstuhl/RedBlack.pdfを開きます。ノード H には子 D と L があります。ページのアルゴリズムに従って、442これら 3 つのノードを 2-3-4 ツリーの 4 ノードに変換します。次に、ノード D には子 B と F があり、これらのノードも 2-3-4 ツリーのノードに変換します。次に、ノード B には子 A と C があり、これらのノードも 2-3-4 ツリーのノードに変換します。最後に、A を削除する必要があります。削除後、バランスを回復する必要があります。ツリーを上に移動し、ツリーのバランスを復元します (ルールに従って、ページの「アルゴリズム第 4 版」の本を参照してください435) 436。ノード D (ページ上の同じツリー) を削除する必要がある場合54）。同じ変換が必要であり、ノード D の値をノード E の値に置き換え、ノード E を削除する必要があります (これは D の後継ノードであるため)。

于 2020-09-16T10:20:51.000 に答える