3

標準のコンテナが適合しない場合に使用するための、リンクされたリスト/バイナリ ツリー メソッドのライブラリがあります。これには、赤黒ツリーの処理が含まれます。

メソッドの 1 つは、二重連結リストから完全にバランスのとれた単純なバイナリ ツリーに変換しますO(n)(アイテムの数が事前にわかっている場合)。このアルゴリズムは「フォールディング」として知られています。これは、Dr. Dobbs でかつて公開された二分木リバランス アルゴリズムの後半です。手順は基本的に...

  • ツリーのサイズを考慮して、左右のサブツリーのサイズを決定します

  • 左サブツリーの再帰

  • リストからノードをポップして、ルートとして使用します

  • 右のサブツリーの再帰

  • サブツリーをルートにリンクする

赤黒木を作成する同様の方法もあります。原則は同じですが、再帰はノードの高さを追跡します。高さがゼロのノードは赤で作成され、その他はすべて黒で作成されます。開始時の高さの計算は、ツリー サイズの最高セット ビットに基づいており、完全にバランスの取れた(2^n)-1サイズのツリーが黒いノードのみを持つように調整されます (再帰は高さ 1 までしか下がりません)。

ここでのポイントは、リーフ レベルに赤いノードしかなく、最大で正確に半分のノードが赤いということです。

問題は、これは有効な赤黒木を生成する簡単な方法ですが、唯一のオプションではありません。完全にバランスの取れたツリーですべての葉が赤くなるのを避けることは、恣意的な選択でした。赤と黒のノードを交互に重ねることができます。または、場合によっては、完全にバランスが取れているサブツリーを見つけて、(赤いノードが必要な場合) サブツリーのルートをすべての葉ではなく赤にすることで、赤いノードの数を劇的に減らすことができます。

問題は、有効な赤黒木の形式を別の形式よりも選択する実際的な理由があるかということです。

これは純粋な好奇心です - 実際的な理由がないことはわかっていますが、この選択が重要な専門的なアプリケーションを知っている人はいますか?

4

2 に答える 2

2

簡単な答えは：それは依存します。

基本的に、有効なツリーであれば十分です。ただし、償却分析の観点からは、長期的には最も最適化された動作を提供する最も正しいツリーを選択する可能性が非常に高くなります。

たとえば、常に有効なツリーを選択しているが、多くのバランシング操作が発生しやすいツリーを選択すると、償却パフォーマンスが低下します。明らかな例は、完全に黒いツリーです。これは完全に有効ですが、変更するとパフォーマンスが低下します。

これは通常、アプリケーション固有であるため、状況によって異なります。

于 2009-11-04T22:17:34.783 に答える
1

物理学者の方法を使用して赤黒ツリーを変更することの償却コストの標準的な分析では、0 または 2 つの赤の子を持つ黒ノードに 1 の正の可能性が割り当てられます。行われなければ。赤の子ノードが 1 つだけある赤のノードと黒のノードには、ポテンシャル 0 が割り当てられます。

したがって、変更のコストを削減するには、すべての黒いノードに 1 つの赤い子を与えます。

1 つの赤い子を持つ黒いノードが祝福される理由は、冗長な 2 進数との類似性によって最もよく説明されます。最初に赤黒木を 2 進数に関連付ける方法を説明し、次に 1 つの赤の子ノードが役立つ理由を説明します。

ご存知かもしれませんが、赤黒木は 2 ～ 4 本の木を表す方法であり、根から葉までのすべての単純なパスは同じ長さですが、ノードには 2、3、または 4 つの子があります。2-4 ツリーでノードを追加または削除するための最も単純なアルゴリズムは、冗長な 2 進数から 1 を追加または削除するのと同じアルゴリズムです。

冗長 2 進数は、標準の 2 進数と同様に i 桁目が 2 iを表す数ですが、i 桁目は 0、1、または 2のいずれかになります。特定の数値を記述する方法が複数あるため、それらは冗長と呼ばれます。4 decは、100 または 20 または 12 と書くことができます。

冗長な 2 進数に 1 を追加するには、最下位桁を増やします。3 の場合は 1 に設定し、次に最下位の桁をインクリメントします。アルゴリズムは、0 または 1 に遭遇すると停止します。

2-4 ツリーに葉を追加するには、意図した親に子を追加します。親に 5 つの子がある場合、それを 2 つのノードに分割し、それらを親の子にします。分割が不要なノードに到達するまで続行します。そのため、ルートへのパスは、2 つまたは 3 つの子を持つノードに遭遇すると停止します。

冗長な 2 進数をインクリメントする償却コストを制限するには、物理​​学者の方法を使用して、2 桁ごとに 1 のポテンシャルを割り当てます。k 桁に触れる xall をインクリメントすると、k-1 の可能性が解放され、償却コストが O(1) になります。

この分析は、標準の 2 進数をインクリメントする償却コストに似ていますが、標準の 2 進数は、O(1) の償却時間でインクリメントとデクリメントの両方をサポートすることはできません。2 k - 1 を考えてみてください。k 1 桁です。増分コスト Θ(k)。その後にデクリメントが続く場合、ペアのコストは Θ(k) になり、数値は元の状態に戻ります。

冗長バイナリは、1 桁がインクリメントとデクリメントの両方のカスケード操作を停止するという点で特別です。2 ～ 4 ツリーは、3 ノードが挿入と削除の両方のカスケード操作を停止するという点で特別です。

赤黒ツリーでは、1 つの赤の子を持つノードは、2-4 ツリーの 3 ノードを表すだけです。これらのノードは特別であり、サブツリーでの挿入または削除に対して堅牢であるため、多くの更新が見られる赤黒ツリーを構築する場合は、それらを優先する必要があります。

挿入のみが表示されることがわかっている場合は、2 つの黒人の子を持つノードを優先します。削除のみが表示されることがわかっている場合は、2 つの赤い子を持つノードを優先します。

于 2017-01-23T07:01:01.727 に答える