赤黒の木

赤黒の木
赤黒の木
タイプ	木
発明した	1978
発明者	レオニダス・J・ギバスとロバート・セジウィック
ビッグオー記法による計算量の表し方
空間
空間の複雑さ
空間
時間計算量
関数
検索
入れる
消去

コンピュータサイエンスにおいて、赤黒木は、順序付けられた情報の高速な格納と取得で知られる自己平衡二分探索木データ構造です。赤黒木のノードは、通常赤と黒で描かれる追加の「色」ビットを保持しており、これにより木が常にほぼ平衡していることが保証されます。^{[ 1 ]}

ツリーが変更されると、新しいツリーは再配置され、「再塗装」されて、最悪の場合にツリーのバランスが崩れる度合いを制限する色付け特性が復元されます。これらの特性は、再配置と再塗装を効率的に実行できるように設計されています。

（再）バランス調整は完璧ではないが、検索を保証する $O(\log n)$ 時間、 $n$ はツリー内のエントリ数です。挿入と削除の操作、ツリーの再配置と色の変更も実行されます。 $O(\log n)$ 時間。^{[ 2 ]}^{[ 3 ]}

各ノードの色を追跡するには、ノードごとに1ビットの情報しか必要ありません。これは、色は2色しかないためです（一部のプログラミング言語に存在するメモリアライメントにより、実際のメモリ使用量は異なる場合があります）。このツリーには、赤黒木であることを示すその他のデータは含まれていないため、メモリ使用量は従来の（色付けされていない）二分探索木とほぼ同じです。場合によっては、追加された1ビットの情報をメモリコストを追加することなく保存できます。

歴史

1972年、ルドルフ・バイヤー^{[ 4 ]}は、Bツリーの4次ケースであるデータ構造を発明しました。これらのツリーは、ルートからリーフまでのすべてのパスを同じ数のノードで保持し、完全にバランスの取れたツリーを作成します。ただし、これらは二分探索木ではありませんでした。バイヤーは論文の中でこれらを「対称二分Bツリー」と呼び、後に2-3-4ツリーまたは2-3ツリーとして普及しました。^{[ 5 ]}

1978年の論文「バランスのとれたツリーのための二色フレームワーク」^{[ 6 ]}で、レオニダス・J・ギバスとロバート・セジウィックは、対称二分Bツリーから赤黒ツリーを導出した。^{[ 7 ]} 「赤」という色は、著者らがゼロックスPARCで働いていたときに利用できたカラーレーザープリンターで生成される色の中で最も見栄えの良い色だったため選ばれた。^{[ 8 ]}ギバスの別の回答では、ツリーを描くために利用できる赤と黒のペンがあったためだと述べている。^{[ 9 ]}

1993年、アルネ・アンダーソンは挿入と削除の操作を簡素化するために右傾斜ツリーの概念を導入した。^{[ 10 ]}

1999年、クリス・オカサキは挿入操作を純粋関数型にする方法を示した。そのバランス関数は、4つの不均衡なケースと1つのデフォルトの均衡ケースのみを処理する必要があった。^{[ 11 ]}

元のアルゴリズムでは 8 つの不均衡なケースが使用されていましたが、Cormen ら (2001) はそれを 6 つの不均衡なケースに減らしました。^{[ 1 ]} Sedgewick は、挿入操作をJavaの 46 行だけで実装できることを示しました。^{[ 12 ]}^{[ 13 ]} 2008 年に、Sedgewick は、挿入および削除操作を簡素化する Andersson のアイデアを活用して、左寄りの赤黒木を提案しました。Sedgewick は当初、2 つの子が赤であるノードを許可し、彼の木を 2-3-4 木に似せていましたが、後にこの制限が追加され、新しい木は 2-3 木に似せられるようになりました。Sedgewick は挿入アルゴリズムをわずか 33 行で実装し、元の 46 行のコードを大幅に短縮しました。^{[ 14 ]}^{[ 15 ]}

用語

ノードの黒深度は、ルートからそのノードまでの黒ノードの数（つまり、黒祖先の数）として定義されます。赤黒木の黒高は、ルートから葉までの任意のパスにある黒ノードの数であり、要件 4により一定です（または、任意の葉ノードの黒深度として定義することもできます）。^{[ 16 ]}^{： 154-165} ノードの黒高は、そのノードをルートとする部分木の黒高です。この記事では、ヌルノードの黒高は 0 に設定する必要があります。これは、例の図が示すように、その部分木が空であり、その木の高さも 0 であるためです。

不動産

二分探索木に課せられる要件に加えて、赤黒木は以下を満たさなければならない。 ^[¹⁷^]

すべてのノードは赤か黒のいずれかです。
すべてのヌルノードは黒とみなされます。
赤いノードには赤い子ノードがありません。
あるノードからそのリーフノード（つまり、任意の子孫のヌルノード）へのすべてのパスは、同じ数のブラックノードを経由する。
（結論）ノードNにちょうど1つの子ノードがある場合、その子ノードは赤色でなければなりません。子ノードが黒色の場合、その葉ノードはNのヌルノード（ルール2では黒色とみなされる）とは異なる黒色の深さに位置し、要件4に違反します。

Cormen ら^{[ 17 ]}は「ルートが黒であること」を 5 番目の要件として主張していますが、Mehlhorn と Sanders ^{[ 16 ]}や Sedgewick と Wayne ^{[ 15 ]}^{はそう主張していません。 : 432–447}ルートは常に赤から黒に変更できるため、このルールは解析にほとんど影響を与えません。また、再帰アルゴリズムと証明をわずかに妨げるため、この記事でもこのルールは省略しています。

例えば、黒ノードのみで構成される完全二分木はすべて赤黒木である。

検索やツリー走査などの読み取り専用操作は、いずれの要件にも影響を与えません。対照的に、変更操作の挿入と削除は要件1と2を容易に維持しますが、他の要件に関しては、要件3の違反（赤違反、または要件4の違反と呼ばれる黒人に対する暴力。

この要件は、赤黒木の重要な特性、すなわち根から最も遠い葉までのパスの長さが根から最も近い葉までのパスの長さの2倍以下であることを強制します。その結果、木は高さバランスが取れます。値の挿入、削除、検索などの操作には、高さに比例する最悪の場合の時間が必要となるため、 $h$ 木の高さの上限により、赤黒木は最悪の場合、つまり木の数の対数で効率的になります。 $n$ エントリ、つまり $h\in O(\log n)$ （これは、 AVL ツリーやB ツリーなど、すべての自己平衡木に共通する性質ですが、通常の二分探索木には当てはまりません。）数学的な証明については、「境界の証明」のセクションを参照してください。

赤黒木は、すべての二分探索木と同様に、要素への非常に効率的な逐次アクセス（例えば、左-根-右の順での順走査）を可能にします。しかし、根から葉への走査による漸近的に最適な直接アクセスもサポートしており、結果として、 $O(\log n)$ 検索時間。

2-3-4ツリーとの類似性

赤黒木は、次数4のB木である2-3-4木と構造が似ています。 ^[¹⁸^] 2-3-4木では、各ノードは1～3個の値を持ち、2～4個の子を持つことができます。これらの2-3-4ノードは、図1に示すように、赤黒木の黒ノードと赤子グループに対応します。3ノードには2つの同等の表現があるため、これは1対1の対応ではありません。赤子は左または右のどちらかに位置する可能性があります。左寄りの赤黒木バリアントは、左子表現のみを許可することで、この関係を正確に1対1にします。すべての2-3-4ノードには対応する黒ノードがあるため、赤黒木の不変量4は、2-3-4木の葉がすべて同じレベルにあると言うことと同等です。

構造的な類似性にもかかわらず、赤黒木に対する操作はB木よりも経済的である。B木は可変長のベクトルの管理を必要とするが、赤黒木は単純な二分木である。^{[ 19 ]}

アプリケーションと関連するデータ構造

赤黒木は、挿入時間、削除時間、検索時間に関して最悪ケース保証を提供します。このため、リアルタイムアプリケーションなどの時間制約のあるアプリケーションで価値があるだけでなく、最悪ケース保証を提供する他のデータ構造の構成要素としても価値があります。たとえば、計算幾何学で使用される多くのデータ構造は赤黒木に基づいており、Linuxカーネルの完全公平スケジューラとepoll システムコールは赤黒木を使用しています。^[²⁰^]^[²¹^] AVL木は、これをサポートする別の構造です。 $O(\log n)$ 検索、挿入、削除。AVL ツリーは赤黒色にすることができ、したがって赤黒ツリーのサブセットです。AVL の最悪ケースの高さは赤黒ツリーの最悪ケースの高さの 0.720 倍なので、AVL ツリーはより厳密にバランスが取れています。Ben Pfaff による 79 回の実行で現実的なテストケースを使用したパフォーマンス測定では、AVL と RB の比率は 0.677 ～ 1.077、中央値は 0.947、幾何平均は0.910 であることがわかりました。^{[ 22 ]} WAVL ツリーのパフォーマンスは、AVL ツリーと赤黒ツリーの中間に位置します。

赤黒木は関数型プログラミングにおいても特に有用であり、最も一般的な永続データ構造の1つとして、変異後も以前のバージョンを保持できる連想配列やセットの構築に使用されます。赤黒木の永続バージョンには $O(\log n)$ 時間に加えて、挿入または削除ごとにスペースが必要になります。

2-3-4木には必ず、同じ順序のデータ要素を持つ対応する赤黒木が存在します。2-3-4木における挿入と削除の操作は、赤黒木における色反転と回転に相当します。このため、2-3-4木は赤黒木の背後にある論理を理解する上で重要なツールとなります。実際、2-3-4木は実用上あまり使われないにもかかわらず、多くの入門アルゴリズムの教科書では、赤黒木の直前に2-3-4木を紹介しています。

2008 年、セジウィックは、実装における以前は指定されていなかった自由度を排除することにより、左傾斜赤黒木^{[ 23 ]}と呼ばれる、より単純なバージョンの赤黒木を導入しました。LLRB は、挿入および削除時を除き、すべての赤いリンクが左に傾かなければならないという追加の不変条件を維持します。赤黒木は、任意の操作シーケンスに対して、2-3 木^{[ 24 ]}または 2-3-4 木^{[ 23 ]}のいずれかに等長にすることができます。2-3-4 木の等長性は、1978 年にセジウィックによって記述されました。^{[ 6 ]} 2-3-4 木では、等長性は、2 つの子ノードの赤色が子ノードから親ノードに移動することに対応する分割に対応する「色の反転」によって解決されます。

高速検索に最適化されたツリーの一種であるタンゴツリーの元の説明では、データ構造の一部として赤黒木が具体的に使用されています。^{[ 25 ]}

Java 8以降、 HashMapは変更され、ハッシュコードが衝突する異なる要素を格納するためにLinkedListを使用する代わりに、赤黒木が使用されるようになりました。これにより、そのような要素を検索する時間計算量が改善されます。 $O(m)$ に $O(\log m)$ どこ $m$ はハッシュが衝突する要素の数です。^{[ 26 ]}

実装

赤黒木に対する検索やツリー走査などの読み取り専用操作は、二分探索木で使用される操作と何ら変わりません。なぜなら、すべての赤黒木は単純な二分探索木の特殊なケースだからです。ただし、挿入や削除の直後の結果は、赤黒木の特性を損なう可能性があります。その特性を回復させる操作は再平衡化と呼ばれ、赤黒木が自己平衡化するようにします。再調整（つまり色の変更）の最悪ケースの時間計算量は $O(\log n)$ そして平均 $O(1)$ , ^{[ 27 ]}^{: 310}^{[ 16 ]}^{: 158}ただし、これらは実際には非常に高速です。さらに、再バランスには 3 つのツリー回転(挿入の場合は 2 つ)を超えることはありません^{[ 28 ]}。

これはC言語における挿入と削除の実装例です。以下にrotate_subtree、挿入と削除の例で使用されるデータ構造とヘルパー関数を示します。

typedef enum Color : char {黒、赤}色;typedef enum Direction : char {左、右}方向;// 赤黒木のノードtypedef struct Node {struct Node * parent ; // ルートノードの場合は nullユニオン{// 共用体なので、->left/->right または ->child[0]/->child[1] を使用できます構造体{struct Node * left ;struct Node * right ;};struct Node * child [ 2 ];};色色;整数キー;}ノード;typedef struct {struct Node * root ;}木;static Direction direction ( const Node * N ) {return N == N -> parent -> right ? RIGHT : LEFT ;}Node * rotate_subtree ( Tree * tree , Node * sub , Direction dir ) {ノード* sub_parent = sub -> parent ;Node * new_root = sub -> child [ 1 - dir ]; // 1 - dir は逆方向Node * new_child = new_root -> child [ dir ];sub -> child [ 1 - dir ] = new_child ;if ( new_child ) {new_child -> parent = sub ;}new_root -> child [ dir ] = sub ;new_root -> parent = sub_parent ;sub -> parent = new_root ;if ( sub_parent ) {sub_parent -> child [ sub == sub_parent -> right ] = new_root ;}それ以外{tree -> root = new_root ;}return new_root ;}

サンプルコードに関する注記、および挿入・削除の図

この提案では、挿入と削除の両方（ごく単純なケースは除く）を、ノード、エッジ、色の6つの組み合わせ（ケース）に分類しています。挿入と削除の両方について、ルートとループに黒レベルを1つ近づけるケースが正確に1つ含まれており、残りの5つのケースはツリーのバランスを独自に調整します。より複雑なケースは図に示されています。

は赤色のノードと（NULLでない）黒色のノード（黒色の高さが1以上）を表し、NULLでないノードの赤色または黒色を表しますが、同じ図全体で同じ色です。NULLノードは図には表示されません。
変数Nは現在のノードを表し、図中ではNまたはNと表記されます。
図には 3 つの列と 2 ～ 4 つのアクションが含まれています。左の列は最初の反復、右の列はより高い反復、中央の列はケースをさまざまなアクションに分割したものを示しています。^{[ 29 ]}

アクション「entry」は、あるケースを定義し、多くの場合いくつかの要件に違反するノードの配置と色を示します。現在のノードNは青い枠で囲まれ、他のノードはNとの関係に応じてラベル付けされています。
回転が有用であると判断された場合、それは次のアクションに示され、「回転」というラベルが付けられます。
色の変更が有用であると考えられる場合は、次のアクションでそれが示され、「色」とラベル付けされています。^{[ 30 ]}
修復が必要な場合、ケースは他のケースのコードを使用し、現在のノードNの再割り当て後にこれを実行します。再割り当てされたノード N には再び青いリングが付き、他のノードもそれに対して再割り当てが必要になる場合があります。このアクションは「再割り当て」とラベル付けされています。挿入と削除の両方について、ルートに 1 つの黒いレベルを反復するケースが (正確に) 1 つあります。その後、再割り当てされたコンスタレーションは、それぞれのループ不変条件を満たします。

番号が振られている可能性のある三角形の上に黒い円が描かれている場合、それは赤黒部分木（要件3に従って親に接続されている）を表し、その黒の高さは反復レベルから1を引いた値、つまり最初の反復では0になります。そのルートは赤または黒のいずれかです。番号が振られている可能性のある三角形は、黒の高さが1少ない赤黒部分木を表し、つまり2回目の反復では親の黒の高さは0になります。

述べる

簡略化のため、サンプルコードでは論理和を使用します。

U == NULL || U->color == BLACK // considered black

そして接続詞：

U != NULL && U->color == RED // not considered black

したがって、の場合、両方のステートメントは全体として評価されないことに留意する必要がありますU == NULL。この場合、どちらの場合もU->colorは変更されません（短絡評価を参照）。（このコメントは要件2considered blackに準拠しています。）

if提案^{[ 29 ]}が実現すれば、関連する声明の発生頻度ははるかに少なくなるはずです。

挿入

挿入は、新しい (NULL ではない) ノード、たとえばN を、順序付けされた先行ノードのキーが新しいノードのキーよりも小さく、さらにその新しいノードのキーが順序付けされた後続ノードのキーよりも小さい NULL ノードの二分探索木内の位置に配置することから始まります。 (多くの場合、この配置は挿入操作の直前の木内での検索の結果であり、ノードと方向で構成されます。) 新しく挿入されたノードは一時的に赤色に着色され、すべてのパスに以前と同じ数の黒いノードが含まれるようになります。しかし、その親、たとえばPも赤色の場合、この操作によって赤色違反が発生します。PdirP->child[dir] == NULL

// 親は省略可能ですvoid insert ( Tree * tree , Node * node , Node * parent , Direction dir ) {ノード->色=赤;ノード->親=親;if ( ! parent ) {ツリー->ルート=ノード;戻る;}親->子[ dir ] =ノード;// ツリーのバランスを再調整するする{// ケース1if ( parent -> color == BLACK ) {戻る;}ノード* grandparent = parent -> parent ;if ( ! grandparent ) {// ケース4親->色=黒;戻る;}dir = direction ( parent );ノード* uncle = grandparent -> child [ 1 - dir ];if ( ! uncle || uncle -> color == BLACK ) {if ( node == parent -> child [ 1 - dir ]) {// ケース5rotate_subtree ( tree , parent , dir );ノード=親;親=祖父母->子[ dir ];}// ケース6rotate_subtree ( tree , grandparent , 1 - dir );親->色=黒;祖父母->色=赤;戻る;}// ケース2親->色=黒;叔父->色=黒;祖父母->色=赤;ノード=祖父母;} while (( parent = node -> parent ));// ケース3戻る;}

挿入操作の再バランスループには、以下の不変条件があります。

ノードとは、現在のノードであり、最初は挿入ノードです。
各反復処理の開始時には、ノードは赤色で表示されます。
要件 3 は、すべてのペア node ← parent に対して満たされますが、parentも赤色の場合( nodeでの赤色違反)は例外となる可能性があります。
その他のすべての特性（要件4を含む）は、ツリー全体で満たされています。

挿入図に関する注記

図では、PはNの親、Gは祖父母、Uは叔父を表します。表では、「—」は根を表します。
図では、親ノードP は親ノードGの左の子として示されていますが、P はどちら側にも存在できます。サンプルコードでは、side 変数を使用して両方の可能性に対応していますdir。
図は、 Pも赤色になる場合、つまり赤色違反の場合を示しています。
x列は子の方向の変化を示しており、o（「外側」）はPとNが両方とも左の子、または両方とも右の子であることを意味し、i（「内側」）は子の方向がPからNに変わることを意味します。
前の列グループはケースを定義しており、その名前は列ケースで指定されています。これにより、空欄のままにされたセル内の値は無視されます。したがって、ケースI2では、サンプルコードはNの子の方向の 2 つの可能性を両方ともカバーしていますが、対応する図には 1 つしか表示されていません。
概要の各行は、考えられるすべてのRB事例が容易に理解できるように順序付けられています。
列の回転は、回転が再均衡に寄与するかどうかを示します。
列割り当ては、次のステップに進む前にNが割り当てられていることを示しています。これにより、他のノードP、G、Uも再割り当てされる可能性があります。
ケースによって何かが変更された場合は、その変更内容が列グループに表示されます。
次の列に記号が表示されている場合は、このステップで再調整が完了したことを示します。次の列でちょうど1つのケースが特定された場合は、そのケースが次のケースとして表示されます。そうでない場合は、疑問符が表示されます。
ケース2では、リバランスの問題が深刻化する。 $\Delta h=2$ ツリーレベル、またはツリー内で 1 つの黒いレベル上、つまり祖父G が新しい現在のノードNになります。したがって、最大で ${\tfrac {h}{2}}$ ツリーを修復するための反復ステップ ( $h$ はツリーの高さ)。エスカレーションの確率は各ステップで指数関数的に減少するため、リバランスの総コストは平均的に一定であり、実際には償却定数です。
ループの外側では、ケースI6とI5+I6で回転が発生します。したがって、合計で最大2回の回転が発生します。

ケース1を挿入

現在のノードの親Pは黒なので、要件 3が満たされます。ループ不変条件に従って、要件 4 も満たされます。

ケース2を挿入

最初の反復

より高い反復回数

ケース2を挿入

親ノードPと叔父ノードUの両方が赤色の場合、両方を黒色に塗り替えることができ、要件 4 を維持するために祖父母ノードG が赤色になります。親ノードまたは叔父ノードを通るパスはすべて祖父母ノードを通る必要があるため、これらのパス上の黒ノードの数は変わりません。ただし、祖父母ノード G に赤色の親ノードがある場合、祖父母ノードGは要件 3 に違反する可能性があります。G をNに再ラベル付けすると、ループ不変条件が満たされるため、1 つの黒レベル (= 2 つのツリーレベル) 上で再バランスを反復できます。

ケース3を挿入

挿入ケース2が実行されました ${\tfrac {h-1}{2}}$ 回実行され、木の高さは 1 増えて $h$ になりました。現在のノードNは木の (赤い) 根であり、すべての RB 特性が満たされています。

ケース4を挿入

親ノードPは赤色で、ルートノードです。ノードNも赤色なので、要件3は満たされません。しかし、 Pの色を変更すると、ツリーはRB型になります。ツリーの黒い部分の高さは1増加します。

ケース5を挿入

最初の反復

より高い反復回数

ケース5を挿入

親ノードPは赤色ですが、叔父ノードUは黒色です。最終的な目標は、親ノードP を祖父母の位置に回転することですが、NがGの「内部」孫(つまり、NがGの右子の左子またはGの左子の右子である場合) には、これは機能しません。Pでのdir-回転は、現在のノードNとその親ノードPの役割を入れ替えます。回転により、Nを通るパス (図の2とラベル付けされたサブツリー内のパス) が追加され、 Pを通るパス( 4とラベル付けされたサブツリー内のパス) が削除されます。しかし、 PとN の両方が赤色なので、要件 4は維持されます。要件 3 はケース 6 で復元されます。

最初の反復

より高い反復回数

ケース6を挿入

現在のノードN は、 Gの「外側」の孫(左の子の左または右の子の右) であることが確実です。次に、 Gで(1-dir)-回転を行い、 Gの代わりにPを配置して、 P をNとGの親にします。要件 3が違反されたため、 Gは黒色で、以前の子であるPは赤色です。PとGの色を入れ替えると、結果として得られる木は要件 3 を満たします。要件 4も満たされたままです。これは、黒色のGを通っていたすべてのパスが、黒色のPを通るようになったためです。

このアルゴリズムは補助データ構造を使用せずに入力を変換し、補助変数用に少量の追加ストレージ領域しか使用しないため、インプレース変換です。

除去

単純なケース

削除対象のノードに2つの子ノード（NULL以外）がある場合、そのノードの値を順序通りの後継ノード（右サブツリーの左端の子ノード）の値と交換し、代わりに後継ノードを削除できます。後継ノードは左端の子ノードであるため、右端の子ノード（NULL以外）を持つか、子ノードを全く持たないかのどちらかになります。
削除されたノードに子ノードが1つしかない場合（NULL以外）。この場合、ノードをその子ノードに置き換え、黒色で表示します。
- 結論5によれば、単一の子ノード（NULL以外）は赤色でなければならず、要件3によれば、削除されたノードは黒色でなければならない。
削除されたノードに子ノードがなく（両方ともNULL）、かつそれがルートノードである場合、そのノードをNULLに置き換えます。ツリーは空になります。
削除されたノードに子ノードがなく（両方ともNULL）、赤色の場合は、リーフノードを削除するだけです。
削除されたノードに子ノードがなく（両方ともNULL）、かつ黒色の場合、そのノードを削除すると不均衡が生じ、次のセクションで説明するように再均衡が必要になります。

黒くなった根以外の葉の除去

複雑なケースは、Nがルートではなく、黒色で表示され、適切な子を持たない場合（⇔ NULLの子のみを持つ場合）です。最初のイテレーションでは、NはNULLに置き換えられます。

void remove ( Tree * tree , Node * node ) {ノード*親=ノード->親;ノード*兄弟;ノード* close_nephew ;ノード*遠い甥;方向dir = direction ( node );親->子[ dir ] = NULL ;start_balanceへ移動;する{dir = direction ( node );開始残高：兄弟=親->子[ 1 - dir ];distant_nephew = sibling -> child [ 1 - dir ];close_nephew = sibling -> child [ dir ];if ( sibling -> color == RED ) {// ケース3rotate_subtree ( tree , parent , dir );親要素->色=赤;兄弟->色=黒;兄弟姉妹=近しい甥;distant_nephew = sibling -> child [ 1 - dir ];if ( distant_nephew && distant_nephew -> color == RED ) {case_6へ移動;}close_nephew = sibling -> child [ dir ];if ( close_nephew && close_nephew -> color == RED ) {case_5へ移動;}// ケース4兄弟->色=赤;親->色=黒;戻る;}if ( distant_nephew && distant_nephew -> color == RED ) {case_6へ移動;}if ( close_nephew && close_nephew -> color == RED ) {case_5へ移動;}if ( parent -> color == RED ) {// ケース4兄弟->色=赤;親->色=黒;戻る;}// ケース2兄弟->色=赤;ノード=親;} while ( parent = node -> parent );// ケース1戻る;ケース5 ：rotate_subtree ( tree , sibling , 1 - dir );兄弟->色=赤;close_nephew -> color = BLACK ;遠い甥=兄弟姉妹;兄弟姉妹=近しい甥;ケース6 ：rotate_subtree ( tree , parent , dir );兄弟->色=親->色;親->色=黒;distant_nephew -> color = BLACK ;戻る;}

削除操作の再バランスループには、次の不変条件があります。

各反復の開始時、Nの黒の高さは反復回数から 1 を引いた値に等しくなります。つまり、最初の反復では黒の高さはゼロであり、それ以降の反復ではNは真の黒ノードになります。
Nを通る経路上の黒ノードの数は削除前より 1 つ少ないが、他のすべての経路上の黒ノードの数は変化しないため、他の経路が存在する場合、 Pで黒ノード違反が発生する。
その他のすべての特性（要件3を含む）は、ツリー全体で満たされています。

削除図に関する注記

以下の図では、PはNの親、SはNの兄弟、C (近い甥を意味する) はSのNと同じ方向の子、D (遠い甥を意味する)はSのもう一方の子を表します ( Sは最初の反復では NULL ノードにはなれません。なぜなら、S は削除前のNの黒の高さが 1 である必要があるからです。ただし、 CとDは NULL ノードにすることができます)。
図では、現在のノードNは親ノードPの左の子として示されていますが、 N はどちら側にも存在できます。コードサンプルでは、side 変数を使用して両方の可能性をカバーしていますdir。
削除の開始時（最初の反復）には、Nは削除対象のノードを置き換える NULL ノードです。親ノード内での位置だけが重要なので、削除図の左列では(現在のノードNは NULL ノードで左の子であることを意味します) で表されます。操作が進むにつれて、適切なノード (黒色の高さ≥ 1) も現在のノードになることがあります (例: ケース2を参照)。
削除図中の黒い丸印（と）の数を数えると、 Nを通る経路は他の経路よりも丸印が 1 つ少ないことがわかります。これは、 Pにおいて黒点違反が存在する場合を意味します。
前の列グループの色分けによって、列ケースで指定された名前のケースが定義されます。これにより、空欄のセルに入力された値は無視されます。
概要の各行は、考えられるすべてのRB事例が容易に理解できるように順序付けられています。
列の回転は、回転が再均衡に寄与するかどうかを示します。
列割り当ては、次の反復ステップに入る前にNが割り当てられていることを示しています。これにより、他のノードP、C、S、Dも再割り当てされる可能性があります。
ケースによって何かが変更された場合は、その変更内容が列グループに表示されます。
次の列に記号が表示されている場合は、このステップで再調整が完了したことを示します。次の列でちょうど1つのケースが特定された場合は、そのケースが次のケースとして表示されます。そうでない場合は、疑問符が表示されます。
ループは、リバランスの問題が深刻化する箇所である。 $\Delta h=1$ 親ノードP が新しい現在のノードNになるため、ツリー内でレベルが上がります。したがって、ツリーを修復するには最大で $h回の反復が必要です ($ $h$ はツリーの高さです)。エスカレーションの確率は反復ごとに指数関数的に減少するため、リバランスの総コストは平均的に一定であり、実際には償却定数です。 (余談ですが、Mehlhorn と Sanders は次のように指摘しています。「AVL ツリーは一定の償却更新コストをサポートしていません。」^{[ 16 ]}^{: 165、158}これは削除後のリバランスには当てはまりますが、AVL 挿入には当てはまりません^。^[³²^] )
ループ本体からは、ケース 3、6、5、4、1 への分岐があります。セクション「ケース3を削除」自体には、ケース 6、5、4 への 3つの異なる分岐があります。
回転はケース6、5 + 6、3 + 5+6で発生しますが、これらはすべてループの外側です。したがって、回転は合計で最大3回発生します。

ケース1を削除

現在のノードNが新しいルートです。各パスから黒ノードが1つ削除されたため、RB特性は維持されます。木の黒ノードの高さは1減少します。

ケース2を削除

→記号の説明

最初の反復

より高い反復回数

ケースD2を削除

P、S、およびSの子は黒です。Sを赤に塗ると、 Sを通過するすべてのパス（ Nを通過しないパスと正確に一致する）の黒ノードが1つ減ります。これで、 Pを根とするサブツリー内のすべてのパスの黒ノードの数は同じになりますが、 Pを通過しないパスより1つ少ないため、要件4はまだ満たされない可能性があります。PをNに再ラベル付けすると、ループ不変条件が満たされるため、1つ上の黒レベル（= 1ツリーレベル）で再バランスを反復できます。

ケース3を削除

最初の反復

より高い反復回数

ケースD3を削除

兄弟ノードSは赤色なので、Pと甥ノードCおよびDは黒色でなければなりません。PでAdir回転を行うと、SはNの祖父母になります。その後、 PとSの色を反転させた後も、 Nを通る経路は黒色のノードが1つ不足しています。しかし、Nには赤色の親ノードPと、再割り当て後の黒色の兄弟ノードSが存在するため、ケース4、5、または6の変換によってRB形状を復元することができます。

ケース4を削除

最初の反復

より高い反復回数

ケースD4を削除

兄弟SとSの子供は黒色だが、Pは赤色である。SとPの色を交換しても、Sを通る経路上の黒色のノード数には影響しないが、 Nを通る経路上の黒色のノード数は1つ増え、それらの経路で削除された黒色のノードを補うことになる。

ケース5を削除

最初の反復

より高い反復回数

ケースD5を削除

兄弟Sは黒、Sの近しい子Cは赤、Sの遠い子Dは黒です。Sで(1-dir)-回転を行うと、甥C がSの親となり、Nの新しい兄弟になります。SとCの色は交換されます。すべてのパスには依然として同じ数の黒いノードがありますが、N には遠い子が赤である黒い兄弟がいるので、この配置はケース D6 に適合します。Nもその親Pもこの変換の影響を受けず、P は赤または黒になる可能性があります (図中)。

ケース6を削除

最初の反復

より高い反復回数

ケースD6を削除

兄弟Sは黒で、Sの遠い子Dは赤です。Pでdir-回転を行うと、兄弟SはPとSの遠い子Dの親になります。PとSの色が交換され、Dは黒になります。サブツリー全体は、ルートSで依然として同じ色、つまり赤または黒 (図中) を持ち、これは変換前と変換後で同じ色を指します。このようにして要件 3が維持されます。サブツリー内のNを通らないパス(つまり、図中のDとノード3を通らないパス) は、以前と同じ数の黒いノードを通りますが、Nには新たに 1 つの黒い祖先が加わります。P が黒になったか、 P が黒でS が黒い祖父母として追加されたかのいずれかです。したがって、 Nを通すパスは新たに 1 つの黒いノードを通り、要件 4が回復され、ツリー全体が RB 型になります。

このアルゴリズムは補助データ構造を使用せずに入力を変換し、補助変数用に少量の追加ストレージ領域しか使用しないため、インプレース変換です。

境界の証明

のために $h\in \mathbb {N}$ 高さのある赤黒い木があります $h$ と

ノード（ $\lfloor \,\rfloor$ は床関数であり、この木の高さでノード数が少ない赤黒木は存在しないため、最小です。その黒の高さは $\lceil h/2\rceil$ （黒い根付き）または奇数の場合 $h$ （それから赤い根で） $(h-1)/2~.$

証拠

ある高さの赤黒木が最小数のノードを持つためには、最小の黒の高さで最大の木の高さを達成するために、最大の数の赤ノードを持つ最長のパスがちょうど1つ存在しなければならない。このパスの他に、他のすべてのノードは黒でなければならない。^{[ 15 ]}^{： 444 証明の概略}この木からノードを取り除くと、高さが失われるか、何らかのRB特性が失われる。

高さのRBツリー $h=1$ 赤根の場合、その影響は最小限です。これは、

m_{1}=2^{\lfloor (1+1)/2\rfloor }\!+\!2^{\lfloor 1/2\rfloor }\!\!-\!\!2=2^{1}\!+\!2^{0}\!\!-\!\!2=1~.

高さが最小のRBツリー（図2のRB _{h ）} $h>1$ 根には、高さの異なる2つの子サブツリーが存在する。高さの高い子サブツリーは最小RBツリーRB _{h –1}でもあり、その高さを定義する最長パスも含まれている。 $h\!\!-\!\!1$ ;それは $m_{h-1}$ ノードと黒の高さ $\lfloor (h\!\!-\!\!1)/2\rfloor =:s.$ もう一方のサブツリーは、(黒)の高さの完全二分木です。 $s$ 持っている $2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1$ 黒ノードのみで、赤ノードは存在しない。ノードの数は帰納法によって求められる。

関数のグラフ $m_{h}$ 凸であり、ブレークポイントを持つ区分的線形である。 $(h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)$ どこ $k\in \mathbb {N} .$ 関数は以下のように表にまとめられています。 $m_{h}=$ A027383( h –1) $h\geq 1$ （ OEISの配列A027383）。

関数を解く $h$

不平等 $9>8=2^{3}$ につながる $3>2^{3/2}$ 奇数の場合 $h$ につながる

m_{h}=3\cdot 2^{(h-1)/2}-2={\bigl (}3\cdot 2^{-3/2}{\bigr )}\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2

。

偶数の場合も奇数の場合も、 $h$ 区間内

と $n$ ノードの数である。^{[ 33 ]}

結論

赤黒の木 $n$ ノード（キー）はツリーの高さを持つ $h\in O(\log n).$

セット操作と一括操作

単一要素の挿入、削除、および検索操作に加えて、赤黒木には、和集合、積集合、差集合など、いくつかの集合操作が定義されています。これらの集合関数に基づいて、挿入または削除の高速一括操作を実装できます。これらの集合操作は、分割と結合という2 つのヘルパー操作に依存しています。新しい操作により、赤黒木の実装はより効率的で高度に並列化できます。^{[ 34 ]}この実装の時間計算量を達成するには、ルートが赤または黒のどちらかである必要があり、すべてのノードが独自の黒の高さを保持する必要があります。

Join : 関数Joinは、2 つの赤黒木 $t 1$ と $t 2$ およびキー $k$ に対して実行されます。ここで、 $t 1 < k < t 2$ 、つまり $t 1$ $のすべてのキーはk$ より小さく、 $t 2$ $のすべてのキーはk$ より大きいという条件が満たされます。この関数は、 $t 1$ と $t 2$ $のすべての要素をk$ として含む木を返します。

2つのツリーの

黒の高さが同じ場合、Joinは左サブツリー

t1

、ルート

k

、右サブツリー

t2

を持つ新しいノードを作成します。t1と

t2

の

両方に黒ルートがある場合は、

kを

赤

に設定します。そうでない場合は、

k

を

黒

に設定します。

黒の高さが異なる場合、

t 1 の黒の高さが

t 2

より大きいと仮定します(もう 1 つのケースは対称です)。Joinは、

t 1

の右スパインをたどり、

t

2

とバランスのとれた黒ノード

c

に到達します。この時点で、左の子

c

、ルート

k

(赤に設定)、右の子

t

2

を持つ新しいノードが作成され、c を置き換えます。新しいノードは、最大で 3 つの赤ノードが連続して出現する可能性があるため、赤黒不変を無効にする可能性があります。これは、二重回転で修正できます。二重赤の問題がルートに伝播する場合は、ルートを黒に設定して特性を復元します。この関数のコストは、2 つの入力ツリー間の黒の高さの差です。

分割: 赤黒木を、キー $xより小さい木とキー$ $x$ より大きい木の 2 つの小さな木に分割するには、まず、赤黒木に $x を$ 挿入してルートからパスを描画します。この挿入後、 $x$ より小さいすべての値はパスの左側に、 $x$ より大きいすべての値は右側に配置されます。結合を適用すると、左側のすべてのサブツリーが、パス上のキーを中間ノードとして使用して下から上にマージされ、左側の木が形成されます。右側は対称になります。

一部のアプリケーションでは、Split は

x が

ツリーに存在するかどうかを示すブール値も返します。Split のコストは

O(\log n),

木の高さの順序。このアルゴリズムは実際には赤黒木の特別な特性とは何の関係もなく、AVL 木などの結合操作を持つ任意の木で使用できます。

結合アルゴリズムは以下のとおりです。

function joinRightRB(T _L , k, T _R ): if (T _L .color=black) and (T _L .blackHeight=T _R .blackHeight): return Node(T _L ,⟨k,red⟩,T _R ) T'=Node(T _L .left,⟨T _L .key,T _L .color⟩,joinRightRB(T _L .right,k,T _R )) if (T _L .color=black) and (T'.right.color=T'.right.right.color=red): T'.right.right.color=black; return rotateLeft(T') return T' /* T ' ' [recte T'] */ function joinLeftRB(T _L , k, T _R ): /* joinRightRB と対称的 */ function join(T _L , k, T _R ): if T _L .blackHeight>T _R .blackHeight: T'=joinRightRB(T _L ,k,T _R ) if (T'.color=red) and (T'.right.color=red): T'.color=black T _R .blackHeight > T _L .blackHeightの場合、 T' を返します。 /* 対称 */ if (T _L .color=black) and (T _R .color=black): return Node(T _L ,⟨k,red⟩,T _R ) return Node(T _L ,⟨k,black⟩,T _R )

分割アルゴリズムは以下のとおりです。

function split(T, k): if (T = NULL) return (NULL, false, NULL) if (k = T.key) return (T.left, true, T.right) if (k < T.key): (L',b,R') = split(T.left, k) return (L',b,join(R',T.key,T.right)) (L',b,R') = split(T.right, k) return (join(T.left,T.key,L'),b,R')

集合 $A$ と $B$ を表す2 つの赤黒木 $t 1$ と $t 2の和集合は、$ $A$ $\cup$ $B$ を表す赤黒木 $t$ です。次の再帰関数はこの和集合を計算します。

function union(t ₁ , t ₂ ): if t ₁ = NULL return t ₂if t ₂ = NULL return t ₁ (L ₁ ,b,R ₁ )=split(t ₁ ,t ₂ .key) proc1=開始: T _L = union(L ₁ ,t ₂ .left) proc2=開始: T _R = union(R ₁ ,t ₂ .right) wait all proc1,proc2 return join(T _L , t ₂ .key, T _R )

ここでは、split関数は2つのツリーを返すものと想定されています。1つは入力キーを除いたキーを保持するツリー、もう1つは入力キーより大きいキーを保持するツリーです。（このアルゴリズムは非破壊的ですが、インプレース破壊バージョンも存在します。）

交差または差のアルゴリズムは似ていますが、Joinと同じだが中間キーがないJoin2ヘルパールーチンが必要です。和集合、交差、差の新しい関数に基づいて、1 つのキーまたは複数のキーを赤黒木に挿入または削除できます。SplitはJoinを呼び出しますが、赤黒木のバランス基準を直接処理しないため、このような実装は通常「結合ベース」の実装と呼ばれます。

和集合、交差集合、差集合のそれぞれの複雑さは $O\left(m\log \left({n \over m}+1\right)\right)$ 2本の赤黒木のサイズ $m$ そして $n(\geq m)$ この複雑さは、比較回数の観点から最適です。さらに重要なのは、和集合、積集合、差集合の再帰呼び出しは互いに独立しているため、並列深度で並列実行できることです。 $O(\log m\log n)$ [ ³⁴^]^の場合 $m=1$ 結合ベースの実装では、より大きなツリーのルートを使用してより小さなツリーを分割する場合、単一要素の挿入と削除と同じ計算上の有向非巡回グラフ（DAG）になります。

並列アルゴリズム

項目のソート済みリストから赤黒木を構築するための並列アルゴリズムは定数時間で実行できます。 $O(\log \log n)$ 時間は、コンピュータのモデルによって異なりますが、利用可能なプロセッサの数が漸近的に数に比例する場合 $n$ アイテムのうち $n\to \infty$ 高速な検索、挿入、削除の並列アルゴリズムも知られている。^{[ 35 ]}

赤黒木のための結合ベースのアルゴリズムは、和集合、積集合、構築、フィルタリング、マップリデュースなど、一括操作に対して並列処理が可能です。

並列一括処理

挿入、削除、更新といった基本的な操作は、複数の要素をまとめて処理する操作を定義することで並列化できます。また、複数の基本操作を組み合わせて一括処理することも可能です。例えば、一括処理では、ツリーに挿入する要素と削除する要素の両方をまとめて処理できます。

一括操作のアルゴリズムは、赤黒木だけでなく、2-3木、2-3-4木、(a,b)木などの他のソート済みシーケンスデータ構造にも適用できます。以下では、一括挿入のためのさまざまなアルゴリズムについて説明しますが、同じアルゴリズムは削除や更新にも適用できます。一括挿入とは、シーケンスの各要素を挿入する操作です。 $I$ 木の中に $T$ 。

参加ベース

このアプローチは、効率的な結合および分割操作をサポートするすべてのソート済みシーケンスデータ構造に適用できます。^{[ 36 ]} 基本的な考え方は、 $I$ と $T$ を複数の部分に分割し、これらの部分に対して並列に挿入を実行することです。

まず、挿入する要素の大部分 $をソートする必要があります。$
その後、アルゴリズムは $I$ を分割します。 $k\in \mathbb {N} ^{+}$ 部品 $\langle I_{1},\cdots ,I_{k}\rangle$ ほぼ同じ大きさ。
次に、木Tをk個の部分に分割する必要があります。 $\langle T_{1},\cdots ,T_{k}\rangle$ $\langle T_{1},\cdots ,T_{k}\rangle$ ある意味では、範囲が $I_{m}$ $I_{m}$ そして $T_{n}$ $T_{n}$ 対応する部分のみの重なり（ $m=n$ $m=n$ ）言い換えれば、順序のおかげで、 $j\in \mathbb {N} ^{+}|\,1\leq j<k$ $j\in \mathbb {N} ^{+}|\,1\leq j<k$ 以下の制約が成り立つ：
1. ${\text{last}}(I_{j})<{\text{first}}(T_{j+1})$
2. ${\text{last}}(T_{j})<{\text{first}}(I_{j+1})$
アルゴリズムは各要素を挿入します $I_{j}$ の中へ $T_{j}$ 順次実行されます。このステップはすべての $j$ に対して実行する必要があります。これは最大 $k 個の$ プロセッサを並列に使用して実行できます。
最後に、得られた複数のツリーを結合して、全体の操作の最終結果を形成します。

$ステップ3で私が$ 設定した分割の制約により、ステップ5でツリーを再び結合し、結果として得られるシーケンスがソートされることが保証されます。

初期ツリー
IとTを分割する
分割されたT字型に挿入する
T に参加

この擬似コードは、一括挿入のための結合ベースアルゴリズムの単純な分割統治実装を示しています。どちらの再帰呼び出しも並列実行可能です。ここで使用されている結合操作は、この記事で説明されているバージョンとは異なり、代わりに2番目のパラメータkが欠落しているjoin2が使用されています。

bulkInsert (T, I, k): I.sort() bulklInsertRec(T, I, k) bulkInsertRec (T, I, k): if k = 1: forall e in I: T.insert(e) else m := ⌊size(I) / 2⌋ (T ₁ , _, T ₂ ) := split(T, I[m]) bulkInsertRec(T ₁ , I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T ₂ , I[m + 1 .. size(I) - 1], ⌊k / 2⌋) T ← join2(T ₁ , T ₂ )

実行時間

ソート $I$ は、この分析では考慮されていません。

これは、分割と結合に並列アルゴリズムを使用することで改善できます。この場合の実行時間は $\in O\left(\log |T|+{\frac {|I|}{k}}\log |T|\right)$ [ ³⁷^]

仕事

パイプライン

バルク操作を並列化するもう1つの方法は、パイプライン方式を使用することです。^{[ 38 ]} これは、基本操作の処理タスクを一連のサブタスクに分割することによって実現できます。複数の基本操作の場合、各サブタスクを個別のプロセッサに割り当てることで、サブタスクを並列に処理できます。

まず、挿入する要素の大部分 $をソートする必要があります。$
アルゴリズムは、 $I$ の各要素に対して、 $T$ 内の対応する挿入位置を特定する。これは各要素に対して並列に実行できる。 $\in I$ $Tは$ このプロセスでは突然変異しないため、各要素の挿入位置に応じて部分配列 $S$ に分割する必要があります $。$ 例えば $s_{n,{\mathit {left}}}$ $は、ノードn$ の左側に挿入される要素を含む $I$ の部分列です。
中央の要素 $m_{n,{\mathit {dir}}}$ すべての部分列の $s_{n,{\mathit {dir}}}$ $T$ に新しいノードとして挿入されます $n'$ これはそれぞれについて並行して実行できます $m_{n,{\mathit {dir}}}$ 定義により、各挿入位置は $m_{n,{\mathit {dir}}}$ ユニークです。 $s_{n,{\mathit {dir}}}$ 左または右に要素が含まれています $m_{n,{\mathit {dir}}}$ それらは新しい部分列 $S$ に含まれることになる。 $s_{n',{\mathit {left}}}$ または $s_{n',{\mathit {right}}}$ 。
Tには、ルートからリーフまでのパスの終端に最大 2 つの連続する赤いノードが含まれる可能性があり、これを修復する必要があります。修復中は、要素の挿入位置が $\in S$ $\in S$ 対応するノードが回転の影響を受ける場合は、更新する必要があります。
- 2つのノードが異なる最も近い黒い祖先を持つ場合、それらは並列に修復できます。同じ最も近い黒い祖先を持つノードは最大で4つであるため、最下位レベルのノードは一定数の並列ステップで修復できます。
- $この手順は、 T$ が完全に修復されるまで、上記の黒レベルに順次適用されます。
ステップ3～5は、Sが空になるまで新しい部分列に対して繰り返されます。この時点で、すべての要素 $\in I$ $\in I$ が挿入されました。これらの手順の各適用はステージと呼ばれます。Sの部分列の長さは $\in O(|I|)$ $\in O(|I|)$ そして各段階でサブシーケンスが半分にカットされ、段階の数は $\in O(\log |I|)$ $\in O(\log |I|)$ 。
- すべてのステージはツリーのブラックレベルを順に上がっていくため、パイプライン処理で並列化できます。あるステージが1つのブラックレベルの処理を完了すると、次のステージはそのレベルに進んで処理を続行できます。

初期ツリー
挿入位置を見つける
ステージ1では要素を挿入します
ステージ1ではノードの修復を開始します。
ステージ2では要素を挿入します
ステージ2ではノードの修復を開始します。
ステージ3では要素を挿入します
ステージ3ではノードの修復を開始します。
ステージ3では引き続きノードの修復を行います。

実行時間

ソート $I$ はこの分析では考慮されていません。また、 $|I|$ より小さいと想定される $|T|$ そうでなければ、結果として得られるツリーを最初から構築する方が効率的だろう。

仕事

参考文献と注釈

1 2Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「赤黒木」.アルゴリズム入門（第2 版）. MIT Press. pp. 273 –301. ISBN 978-0-262-03293-3。
↑パトン、ジェームズ。「赤黒の木々」。
↑ Morris, John (1998). "赤黒木" .データ構造とアルゴリズム.
↑ Bayer, Rudolf (1972). "対称バイナリBツリー：データ構造とメンテナンスアルゴリズム". Acta Informatica . 1 (4): 290– 306. doi : 10.1007/BF00289509 . S2CID 28836825 .
↑ Drozdek, Adam (2001). Data Structures and Algorithms in Java (2nd ed.). Sams Publishing. p. 323. ISBN 978-0534376680。
1 2 Guibas, Leonidas J. ; Sedgewick, Robert (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual Symposium on Foundations of Computer Science . pp. 8– 21. doi : 10.1109/SFCS.1978.3 .
↑ 「赤と黒の木」 . eternallyconfuzzled.com . 2007年9月27日のオリジナルからアーカイブ済み。2015年9月2日取得。
↑ Sedgewick, Robert (2012). Red–Black BSTs . Coursera.多くの人が、なぜ赤黒という名前を使ったのかと尋ねます。私たちは、このデータ構造、つまりバランスの取れたツリーの見方を、パーソナルコンピュータや、グラフィカルユーザーインターフェース、イーサネット、オブジェクト指向プログラミングなど、今日私たちが使っている多くのイノベーションの本拠地であるゼロックスPARCで発明しました。しかし、そこで発明されたものの1つがレーザー印刷で、私たちは近くにカラーレーザープリンターがあり、色で印刷できるようになったことに非常に興奮しました。そして、色の中で赤が一番見栄えが良かったのです。そのため、3つのノードで赤いリンク、つまりリンクの種類を区別するために、赤という色を選びました。これが、これまで質問してきた人たちへの答えです。
↑ 「「赤/黒の木」という用語はどこから来たのですか？」 . programmers.stackexchange.com . 2015年9月2日取得。
↑ Andersson, Arne (1993-08-11). "Balanced search trees made simple" . In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algorithms and Data Structures (Proceedings). Lecture Notes in Computer Science. Vol. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71 . CiteSeerX 10.1.1.118.6192 . doi : 10.1007/3-540-57155-8_236 . ISBN 978-3-540-57155-12018年12月8日にオリジナルからアーカイブされました。代替URL
↑ Okasaki, Chris (1999-01-01). "関数型プログラミングにおける赤黒木" . Journal of Functional Programming . 9 (4): 471– 477. doi : 10.1017/S0956796899003494 . ISSN 1469-7653 . S2CID 20298262 .
↑セッジウィック、ロバート（1983）。アルゴリズム（第1版）。アディソン・ウェスリー。ISBN 978-0-201-06672-2。
↑ Sedgewick, Robert ; Wayne, Kevin. "RedBlackBST.java" . algs4.cs.princeton.edu . 2018年4月7日取得.
↑セッジウィック、ロバート(2008)。「左傾化した赤黒の木々」(PDF)。
1 2 3セッジウィック、ロバート；ウェイン、ケビン（2011）。アルゴリズム（第4版）。アディソン・ウェスリー・プロフェッショナル。ISBN 978-0-321-57351-3。
1 2 3 4 Mehlhorn, Kurt ; Sanders, Peter (2008). "7. ソート済みシーケンス" (PDF) .アルゴリズムとデータ構造: 基本ツールボックス. ベルリン/ハイデルベルク: Springer. CiteSeerX 10.1.1.148.2305 . doi : 10.1007/978-3-540-77978-0 . ISBN 978-3-540-77977-3。
1 2 Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2022). "13. 赤黒木".アルゴリズム入門（第4版）. MIT Press . pp. 331 –332. ISBN 9780262046305。
↑クヌースの順序の定義を用いると：子供の最大数
↑セッジウィック、ロバート（1998）。C ++ のアルゴリズム。アディソン・ウェスリー・プロフェッショナル。565 ～ 575ページ。ISBN 978-0-201-35088-3。
↑ 「IBM Developer」。developer.ibm.com 。 2024年5月25日取得。
↑ 「epollの実装（1）」 .大同の雑感. 2014年9月。2020年10月11日にオリジナルからアーカイブ済み。 2018年6月25日取得。
↑ Pfaff 2004
1 2 「ロバート・セジウィック」(PDF) . Cs.princeton.edu . 2020年6月4日. 2022年3月26日取得.
↑ 「バランスのとれた木構造」（PDF）。Cs.princeton.edu 。 2022年3月26日取得。
↑デメイン、ED;ハーモン、D.イアコノ、J.パトラシュク、M. (2007)。「動的最適性 - ほぼ」(PDF)。SIAM ジャーナルオンコンピューティング。37 (1): 240.土井: 10.1137/S0097539705447347。S2CID 1480961。
↑ 「Java で HashMap はどのように動作するのか」。coding-geek.com。
↑ Tarjan, Robert Endre (1985 年 4 月) 「償却計算複雑度」(PDF) . SIAM Journal on Algebraic and Discrete Methods . 6 (2): 306– 318. doi : 10.1137/0606031 .
↑これらのツリー回転の重要な点は、ツリーのノードの順序を維持することです。
1 2左側の列は右側の列に比べてノード数がはるかに少なく、特に削除処理において顕著です。これは、最初の反復処理を挿入と削除の再バランスループから取り出すことで効率が向上することを示しています。なぜなら、名前付きノードの多くは最初の反復処理ではNILノードであり、その後は確実に非NILノードになるからです。（この注釈も参照してください。）
↑明瞭さを保つため、回転は色変更の前に配置されています。ただし、この2つは可換なので、回転を末尾に移動することは自由です。
1 2同じ分割はベン・プファフにも見られる。
↑ Dinesh P. Mehta、Sartaj Sahni (編)データ構造と応用ハンドブック10.4.2
↑上界での等式は、高さが偶数の_{最小RB木RB 2 kに対して成り立つ。} $2\cdot k$ と $n=2\cdot 2^{k}-2$ ノードのみ、そしてそれらのノードのみ。したがって、不等式は広く普及しているものよりもわずかに正確である。 $h<2\log _{2}(n+1),$ 例えば、コーメンの264ページを参照。さらに、これらの木は、RB要件1～4に適合する色付けを1つだけ許容する二分木である。しかし、他にもそのような木は存在する。例えば、子ノードを黒い葉に追加すると、必ず赤になる。（奇数の高さの最小RB木では、根の色を赤から黒に反転させることができる。）
1 2 Blelloch, Guy E. ; Ferizovic, Daniel; Sun, Yihan (2016). "Just Join for Parallel Ordered Sets" (PDF) . Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures . ACM. pp. 253–264 . arXiv : 1602.02120 . doi : 10.1145 /2935764.2935768 . ISBN 978-1-4503-4210-0. S2CID 2897793 . 。
↑ Park, Heejin; Park, Kunsoo (2001). "赤黒木のための並列アルゴリズム" . Theoretical Computer Science . 262 ( 1– 2): 415– 435. doi : 10.1016/S0304-3975(00)00287-5 .ソートされたリストから赤黒木を構築するための並列アルゴリズム $n$ アイテムは $O(1)$ 一緒に過ごす時間 $n$ CRCW PRAM 上のプロセッサで実行され、 $O(\log \log n)$ 一緒に過ごす時間 $n/\log \log n$ EREW PRAM上のプロセッサ。
↑ Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (編). Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox . Springer eBooks. Cham: Springer. pp. 252–253 . doi : 10.1007/978-3-030-25209-0 . ISBN 9783030252090. S2CID 201692657 .
↑ Akhremtsev, Yaroslav; Sanders, Peter (2016). "高速並列検索木操作". 2016 IEEE 23rd International Conference on High Performance Computing (HiPC) . pp. 291–300 . arXiv : 1510.05433 . doi : 10.1109/HiPC.2016.042 . ISBN 978-1-5090-5411-4。
↑ Jájá, Joseph (1992).並列アルゴリズム入門. Reading, Mass. [ua]: Addison-Wesley. pp. 65–70 . ISBN 0201548569. Zbl 0781.68009 .

さらに読む

数学の世界：赤黒木
サンディエゴ州立大学：CS 660：赤黒樹に関するノート、ロジャー・ホイットニー著
Pfaff, Ben (2004年6月) 「システムソフトウェアにおけるBSTのパフォーマンス分析」 ( PDF)スタンフォード大学。

外部リンク

Ben Pfaff:二分探索木と平衡木入門。フリーソフトウェア財団、ボストン、2004年、ftp.gnu.org（PDF gzip; 1662 kB）
C言語による完全かつ動作する実装
エリック・デメインによる、OCW MITの赤黒木に関する講義
YouTubeのバイナリーサーチツリー挿入可視化– 基本的なバイナリーサーチツリーと左傾赤黒木における、ランダムおよび事前ソートされたデータの挿入の可視化
C++で書かれた侵入型赤黒木
3.3 バランス探索木における赤黒二分探索木
赤黒BSTデモ

[Cormen2001-1] 1 2Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「赤黒木」.アルゴリズム入門（第2 版）. MIT Press. pp. 273 –301. ISBN 978-0-262-03293-3。

[wiscurl2-2] パトン、ジェームズ。「赤黒の木々」。

[3] Morris, John (1998). "赤黒木" .データ構造とアルゴリズム.

[Bayer72-4] Bayer, Rudolf (1972). "対称バイナリBツリー：データ構造とメンテナンスアルゴリズム". Acta Informatica . 1 (4): 290– 306. doi : 10.1007/BF00289509 . S2CID 28836825 .

[5] Drozdek, Adam (2001). Data Structures and Algorithms in Java (2nd ed.). Sams Publishing. p. 323. ISBN 978-0534376680。

[GS78-6] 1 2 Guibas, Leonidas J. ; Sedgewick, Robert (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual Symposium on Foundations of Computer Science . pp. 8– 21. doi : 10.1109/SFCS.1978.3 .

[7] 「赤と黒の木」 . eternallyconfuzzled.com . 2007年9月27日のオリジナルからアーカイブ済み。2015年9月2日取得。

[Sedgewick12-8] Sedgewick, Robert (2012). Red–Black BSTs . Coursera.多くの人が、なぜ赤黒という名前を使ったのかと尋ねます。私たちは、このデータ構造、つまりバランスの取れたツリーの見方を、パーソナルコンピュータや、グラフィカルユーザーインターフェース、イーサネット、オブジェクト指向プログラミングなど、今日私たちが使っている多くのイノベーションの本拠地であるゼロックスPARCで発明しました。しかし、そこで発明されたものの1つがレーザー印刷で、私たちは近くにカラーレーザープリンターがあり、色で印刷できるようになったことに非常に興奮しました。そして、色の中で赤が一番見栄えが良かったのです。そのため、3つのノードで赤いリンク、つまりリンクの種類を区別するために、赤という色を選びました。これが、これまで質問してきた人たちへの答えです。

[9] 「「赤/黒の木」という用語はどこから来たのですか？」 . programmers.stackexchange.com . 2015年9月2日取得。

[10] Andersson, Arne (1993-08-11). "Balanced search trees made simple" . In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algorithms and Data Structures (Proceedings). Lecture Notes in Computer Science. Vol. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71 . CiteSeerX 10.1.1.118.6192 . doi : 10.1007/3-540-57155-8_236 . ISBN 978-3-540-57155-12018年12月8日にオリジナルからアーカイブされました。代替URL

[11] Okasaki, Chris (1999-01-01). "関数型プログラミングにおける赤黒木" . Journal of Functional Programming . 9 (4): 471– 477. doi : 10.1017/S0956796899003494 . ISSN 1469-7653 . S2CID 20298262 .

[Algs1-12] セッジウィック、ロバート（1983）。アルゴリズム（第1版）。アディソン・ウェスリー。ISBN 978-0-201-06672-2。

[13] Sedgewick, Robert ; Wayne, Kevin. "RedBlackBST.java" . algs4.cs.princeton.edu . 2018年4月7日取得.

[14] セッジウィック、ロバート(2008)。「左傾化した赤黒の木々」(PDF)。

[Algs4-15] 1 2 3セッジウィック、ロバート；ウェイン、ケビン（2011）。アルゴリズム（第4版）。アディソン・ウェスリー・プロフェッショナル。ISBN 978-0-321-57351-3。

[Mehlhorn2008-16] 1 2 3 4 Mehlhorn, Kurt ; Sanders, Peter (2008). "7. ソート済みシーケンス" (PDF) .アルゴリズムとデータ構造: 基本ツールボックス. ベルリン/ハイデルベルク: Springer. CiteSeerX 10.1.1.148.2305 . doi : 10.1007/978-3-540-77978-0 . ISBN 978-3-540-77977-3。

[Cormen2009-17] 1 2 Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2022). "13. 赤黒木".アルゴリズム入門（第4版）. MIT Press . pp. 331 –332. ISBN 9780262046305。

[18] クヌースの順序の定義を用いると：子供の最大数

[19] セッジウィック、ロバート（1998）。C ++ のアルゴリズム。アディソン・ウェスリー・プロフェッショナル。565 ～ 575ページ。ISBN 978-0-201-35088-3。

[20] 「IBM Developer」。developer.ibm.com 。 2024年5月25日取得。

[21] 「epollの実装（1）」 .大同の雑感. 2014年9月。2020年10月11日にオリジナルからアーカイブ済み。 2018年6月25日取得。

[22] Pfaff 2004

[LLRB-23] 1 2 「ロバート・セジウィック」(PDF) . Cs.princeton.edu . 2020年6月4日. 2022年3月26日取得.

[24] 「バランスのとれた木構造」（PDF）。Cs.princeton.edu 。 2022年3月26日取得。

[DHIP-25] デメイン、ED;ハーモン、D.イアコノ、J.パトラシュク、M. (2007)。「動的最適性 - ほぼ」(PDF)。SIAM ジャーナルオンコンピューティング。37 (1): 240.土井: 10.1137/S0097539705447347。S2CID 1480961。

[26] 「Java で HashMap はどのように動作するのか」。coding-geek.com。

[tarjan-27] Tarjan, Robert Endre (1985 年 4 月) 「償却計算複雑度」(PDF) . SIAM Journal on Algebraic and Discrete Methods . 6 (2): 306– 318. doi : 10.1137/0606031 .

[28] これらのツリー回転の重要な点は、ツリーのノードの順序を維持することです。

[pullout-29] 1 2左側の列は右側の列に比べてノード数がはるかに少なく、特に削除処理において顕著です。これは、最初の反復処理を挿入と削除の再バランスループから取り出すことで効率が向上することを示しています。なぜなら、名前付きノードの多くは最初の反復処理ではNILノードであり、その後は確実に非NILノードになるからです。（この注釈も参照してください。）

[30] 明瞭さを保つため、回転は色変更の前に配置されています。ただし、この2つは可換なので、回転を末尾に移動することは自由です。

[cases-31] 1 2同じ分割はベン・プファフにも見られる。

[32] Dinesh P. Mehta、Sartaj Sahni (編)データ構造と応用ハンドブック10.4.2

[33] 上界での等式は、高さが偶数の_{最小RB木RB 2 kに対して成り立つ。} $2\cdot k$ と $n=2\cdot 2^{k}-2$ ノードのみ、そしてそれらのノードのみ。したがって、不等式は広く普及しているものよりもわずかに正確である。 $h<2\log _{2}(n+1),$ 例えば、コーメンの264ページを参照。さらに、これらの木は、RB要件1～4に適合する色付けを1つだけ許容する二分木である。しかし、他にもそのような木は存在する。例えば、子ノードを黒い葉に追加すると、必ず赤になる。（奇数の高さの最小RB木では、根の色を赤から黒に反転させることができる。）

[join-based-34] 1 2 Blelloch, Guy E. ; Ferizovic, Daniel; Sun, Yihan (2016). "Just Join for Parallel Ordered Sets" (PDF) . Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures . ACM. pp. 253–264 . arXiv : 1602.02120 . doi : 10.1145 /2935764.2935768 . ISBN 978-1-4503-4210-0. S2CID 2897793 . 。

[35] Park, Heejin; Park, Kunsoo (2001). "赤黒木のための並列アルゴリズム" . Theoretical Computer Science . 262 ( 1– 2): 415– 435. doi : 10.1016/S0304-3975(00)00287-5 .ソートされたリストから赤黒木を構築するための並列アルゴリズム $n$ アイテムは $O(1)$ 一緒に過ごす時間 $n$ CRCW PRAM 上のプロセッサで実行され、 $O(\log \log n)$ 一緒に過ごす時間 $n/\log \log n$ EREW PRAM上のプロセッサ。

[36] Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (編). Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox . Springer eBooks. Cham: Springer. pp. 252–253 . doi : 10.1007/978-3-030-25209-0 . ISBN 9783030252090. S2CID 201692657 .

[37] Akhremtsev, Yaroslav; Sanders, Peter (2016). "高速並列検索木操作". 2016 IEEE 23rd International Conference on High Performance Computing (HiPC) . pp. 291–300 . arXiv : 1510.05433 . doi : 10.1109/HiPC.2016.042 . ISBN 978-1-5090-5411-4。

[38] Jájá, Joseph (1992).並列アルゴリズム入門. Reading, Mass. [ua]: Addison-Wesley. pp. 65–70 . ISBN 0201548569. Zbl 0781.68009 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[

[

[ 19 ]

[

[

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

。

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

37

[ 38 ]

歴史

用語

不動産

2-3-4ツリーとの類似性

アプリケーションと関連するデータ構造

実装

サンプルコードに関する注記、および挿入・削除の図

挿入

挿入図に関する注記

ケース1を挿入

ケース2を挿入

ケース3を挿入

ケース4を挿入

ケース5を挿入

ケース6を挿入

除去

単純なケース

黒くなった根以外の葉の除去

削除図に関する注記

ケース1を削除

ケース2を削除

ケース3を削除

ケース4を削除

ケース5を削除

ケース6を削除

境界の証明

セット操作と一括操作

並列アルゴリズム

並列一括処理

参加ベース

実行時間

仕事

パイプライン

実行時間

仕事

関連項目

参考文献と注釈

さらに読む

外部リンク