赤黒ツリーに変換する場合、ある形式を別の形式よりも選択する理由はありますか?

Question

標準コンテナが適合しない場合に使用するリンク リスト/バイナリ ツリー メソッドのライブラリがあります。さまざまなタイプのノードがある場合、またはバイナリ ツリーからリストに変換し、再度その逆に変換する必要がある場合。赤黒ツリーの処理が含まれます。

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

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

• 左側のサブツリーの再帰

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

• 右側のサブツリーを再帰する

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

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

ここで重要なのは、リーフ レベルには赤いノードのみがあり、最大でちょうど半分のノードが赤いということです。

重要なのは、これは有効な赤黒ツリーを生成する簡単な方法ですが、これが唯一の選択肢ではないということです。完璧にバランスのとれた木ですべての葉が赤くなるのを避けるのは任意の選択でした。赤と黒のノードのレイヤーを交互に配置することもできます。あるいは、場合によっては、完全にバランスの取れたサブツリーを見つけて、(赤いノードが必要な場合) すべての葉ではなくサブツリーのルートを赤くすることで、赤いノードの数を劇的に減らすこともできます。

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

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

Answer 1

pysicistの方法を用いて、赤 - 黒ツリーを変更するの償却原価の標準分析では、ゼロまたは2つの赤い子供を持つ黒色のノードは、それらがどこ余分ツリー内の問題の場所を表すことを意味し、一方の正電位が割り当てられています作業が行われる必要があるかもしれません。正確に一つの赤色子赤ノードと黒のノードがゼロの電位が割り当てられます。

ですから、変更のコストを削減するために、すべての黒のノードに一つの赤の子供を与えます。

<時間>

の の理由のの1人の赤い子と黒のノードは恵まれている理由進数を冗長するための類推により、最良説明されています。私は最初の二進数に赤黒木に関連する方法を説明し、その後、私は一赤色子ノードが有用である理由を説明します。

ご存知のように、

、赤黒木は、ルートからリーフまでのすべての単純な経路が同じ長さを有するが、ノードが2、3、または4人の子供を持っている2-4木を表現する方法です。 2-4ツリーにノードを追加または削除するための最も単純なアルゴリズムは、の冗長2進数から1を加算または減算と同じアルゴリズムである。

冗長2進数は、i番目の数字は、単に標準のバイナリ数のように、2 ^I を表すが、i番目の桁が0、1、のの可能な数でありますまたは2 のの。与えられた数を書き込むための複数の方法があるので、彼らは、冗長と呼ばれています。 4 <サブ> 12月 100又は20又は12に書き込むことができます。

冗長2進数に1を追加するには、最下位桁をインクリメント。それが3である場合、ように1に設定し、次の最下位桁をインクリメントし、そして。それは0又は1を検出したときにアルゴリズムが停止します。

2-4木に葉を追加するには、その意図した親に子を追加します。親はどのように5人の子供を持っている場合は、二つのノードに分割し、それらをその親の子供を作ります。あなたが分割を必要としないノードに到達するまで続けます。それが二、三人の子供を持つノードに遭遇したときに、ルートへのパスが停止します。

、冗長2進数をインクリメントの償却原価を結合した物理学者の方法を使用し、各2桁に1の電位を割り当てます。それをO（1）の償却原価を与え、K桁リリースK-1電位に触れるインクリメントするxall。

分析は、標準的な2進数をインクリメントの償却原価と同様であるが、標準的な二進数はO（1）償却時間をインクリメントとデクリメントの両方をサポートすることができない。考える2 ^K - 1。それがk 1桁です。インクリメントはΘ（k）を要します。それは減少が続いている場合は、ペアはΘ（k）をコストとその古い状態に戻す番号をもたらします。

冗長2進数は、1桁増加と減少の両方のカスケード動作を停止に特別です。 2-4木の挿入および削除の両方のカスケード動作を停止その3ノードに特殊である。

赤黒木では、一つの赤の子を持つノードは、2-4ツリーで3ノードのちょうど表現です。これらのノードは、挿入に対する特別かつ堅牢であるか、そのサブツリーに削除されますので、アップデートの多くが表示されます赤黒木を構築するときに、あなたはそれを好む必要があります。

あなたが知っている場合は、

あなたは2つの黒い人の子供を持つノードを好む、挿入だけが表示されます。あなたが表示されます知っているだけで削除した場合、2人の赤い子供と一緒にノードを好むます。

Answer 2

短い答えは次のとおりです。 場合によります.

基本的に、有効なツリーであればどれでも十分です。ただし、次の点に関しては、 償却分析 - 長期的には最も最適化された動作をもたらす最も正しいツリーを選択することになる可能性が非常に高いです。

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

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