15

このページごとhttp://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx 「トップダウン削除」は、赤いノードを押し下げることによって積極的にツリーのバランスを取る赤黒ツリー ノード削除の実装です。ツリーを介して、削除されるリーフ ノードが確実に赤くなるようにします。葉ノードは必ず赤くなるため、ツリーの再バランスについて心配する必要はありません。赤い葉ノードを削除してもルールに違反することはなく、再調整するために追加の操作を実行する必要がないからです。バランスを取り、赤黒さを復元します。

「ボトムアップ削除」では、ツリーを下方向に通常のバイナリ検索を実行して削除するノードを見つけ、リーフ ノードを交換し (見つかったノードがリーフ ノードでない場合)、赤黒ツリー プロパティを復元します。赤黒のルール違反を修正しながら木を登ることによって。

トップダウン削除は再調整操作の数を最小限に抑えますか? トップダウンの削除が、ダウンの途中であまりにも多くの再カラーリングと再バランスを積極的に行う可能性はありますか?

このシナリオはどうですか: (x) は赤いノードを示します

               8
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

16 を削除したい場合、ボトムアップの削除ではリバランスは行われませんが、トップダウンの削除では、ノードの色が完全に変更されてから、色の変更操作が不要であることがわかります。

反復 1:

              (8)
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

反復 2:

               8
         _____/ \____
        /            \
      (4)            (12)
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

反復 3:

               8
         _____/ \____
        /            \
      (4)             12
     /   \          /    \
   2       6     (10)    (14)
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

次に反復 4 で、16 はすでに赤なので、押し下げる必要がないことがわかります。では、トップダウン削除は時間とスペースの効率が良いのでしょうか?

4

2 に答える 2

4

私が収集したものから：「トップダウン削除」は、操作中にパス内の同じノードを複数回トラバースすることを回避します。では、ルートから特定のノードへの単純なパスが与えられたとして、とにかくそのパスにあるノードに対して何かを行う場合は、途中でそれを実行してみませんか? パスの一部を複数回トラバースする必要がなくなります。したがって、これにより時間が節約されます。

同様の原則が、2-3-4 ツリー (a、b ツリーの特殊なサブケース) での複数の操作 (挿入を含む) に使用されます。

トップダウン削除は再調整操作の数を最小限に抑えますか?

平均的なケースでは、そうであると考えてください。再調整操作をほとんど行わずに、後で何かを挿入するのが潜在的に簡単になるからです。

トップダウンの削除が、ダウンの途中であまりにも多くの再カラーリングと再バランスを積極的に行う可能性はありますか?

たぶん、しかしそれはデータセットに依存します。ただし、前述のとおりです。これにより、再カラーリングと再バランスの回数を全体的に減らすことができます。

于 2008-12-13T20:01:19.407 に答える
3

トップダウンはボトムアップよりスペース効率が良いですか?

一言で言えば、そうです。永遠に混乱しているで提示されたトップダウン アルゴリズムは、ノード上に親ポインターを必要としません。ボトムアップ アルゴリズムでは、時間と空間の間のトレードオフが提示されます。親ポインターは、挿入と削除の後にバランスを再調整するときに、一部の短絡を許容します。

たとえば、OpenJdk-7 のRed-black ツリーの実装には親ポインターがあり、削除後に再バランスが必要かどうかを選択できます (シナリオなど)。

トップダウンはボトムアップよりも時間効率が良いですか?

一般に、はい: トップダウン アプローチでは操作ごとに 1 回だけツリーをトラバースする必要がありますが、ボトム アプローチでは操作ごとにツリーを 2 回トラバースする必要があります。先に述べたように、ボトムアップ アプローチでは、親ポインタを使用することで時間を短縮できます。しかし、毎回ツリー全体をトラバーサルするわけではありません。

どちらの実装でも、ツリー全体を反復処理するために必要な時間またはスペースを改善するために、スレッド化を利用することを選択する場合があります。これには、ノードごとに 1 つまたは 2 つのフラグのオーバーヘッドが必要です。これは、親ポインターを使用して実現することもできますが、効率的ではありません。注意:スレッド化のリンクでは、スレッド化は親ポインターほど効率的ではないと書かれていますが、これはボトムアップ ツリー (この本でカバーされています) にのみ適用されます。

事例証拠

大学に戻って、私たちは永遠に混乱したトップダウンの赤黒ツリーを C++ で実装し、std::map の STL (ボトムアップ) 実装と比較しました。私たちのトップダウン アプローチは間違いなく高速でした。つまり、すべての変更操作で簡単に 2 倍高速でした。検索も高速になりましたが、ツリーのバランスが取れているためか、コードが複雑でないためかはわかりません。

悲しいことに、コードも記事もありません。

于 2011-11-05T23:41:06.433 に答える