赤黒木

赤黒木
タイプ	木
発明された	1978
発明者	レオニダス・J・ギバスとロバート・セジウィック
ビッグO記法の複雑さ
空間複雑性 空間 ${\displaystyle O(n)}$ 時間計算量 関数 償却 最悪の場合 検索 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ 入れる ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ 消去 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

赤黒木の例

コンピュータサイエンスにおいて、赤黒木は自己平衡型二分探索木 データ構造であり、順序付けられた情報の高速な保存と検索で知られています。赤黒木のノードは、多くの場合赤と黒で描画される追加の「色」ビットを保持しており、これにより木が常にほぼ平衡状態を保つことができます。^[1]

ツリーが変更されると、新しいツリーは再配置され、「再描画」されます。これは、最悪のケースにおいてツリーがどの程度不均衡になるかを制限する色付け特性を復元するためです。これらの特性は、この再配置と再色付けが効率的に実行されるように設計されています。

（再）バランス調整は完璧ではありませんが、探索時間（ここではツリー内のエントリ数）を保証します。挿入と削除の操作、ツリーの並べ替えと色の変更も、同様に実行時間内に実行されます。^{[2] [3]}${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle O(\log n)}$

各ノードの色を追跡するには、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 は、挿入操作をわずか 46 行の}Javaで実装できることを示しました。^{[12] [13]} 2008 年に Sedgewick は、挿入および削除操作を簡素化した Andersson のアイデアを活用して、左に傾いた赤黒木を提案しました。 Sedgewick は当初、2 つの子が赤であるノードを許可していたため、彼の木は 2–3–4 木に似ていましたが、後にこの制限が追加され、新しい木は 2–3 木に似るようになりました。 Sedgewick は挿入アルゴリズムをわずか 33 行で実装し、元の 46 行のコードを大幅に短縮しました。^{[14] [15]}

用語

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

プロパティ

二分探索木に課せられた要件に加えて、赤黒木は以下の要件を満たす必要がある: ^[17]

1. すべてのノードは赤か黒のいずれかになります。
2. すべての null ノードは黒とみなされます。
3. 赤いノードには赤い子がありません。
4. 特定のノードからそのリーフ ノード (つまり、子孫のヌル ノード) へのすべてのパスは、同じ数の黒いノードを通過します。
5. (結論) ノードNが子ノードを 1 つだけ持つ場合、その子ノードは必ず赤ノードでなければならない。もし子ノードが黒ノードであれば、その葉ノードの黒の深さはNのヌルノード（ルール 2 により黒ノードとみなされる）とは異なるため、要件 4 に違反する。

Cormenら^[17]などの著者は、 「ルートが黒であること」が第5の要件であると主張しているが、MehlhornとSanders ^{[16]やSedgewickとWayne [15]}はそうではない。^{: 432–447}ルートは常に赤から黒に変更できるため、この規則は解析にほとんど影響を与えない。本稿でも、再帰アルゴリズムと証明に若干の支障をきたすため、この規則は省略する。

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

検索やツリーの走査といった読み取り専用操作は、いずれの要件にも影響を与えません。一方、挿入や削除といった変更操作は要件1と2を容易に満たしますが、その他の要件に関しては、要件3の違反を回避するために、ある程度の努力が必要です。これは「赤違反、または要件4の違反は、黒違反。

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

赤黒木は、他の二分探索木と同様に、要素への非常に効率的な順次アクセス（例えば、左→ルート→右の順序での走査）を可能にします。しかし、ルートから葉への走査を介した漸近的に最適な直接アクセスもサポートしており、その結果、探索時間が長くなります。 ${\displaystyle O(\log n)}$

2～3～4本の木の類似性

図1: 2-3-4ツリーと赤黒ツリーの類似点

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

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

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

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

赤黒木は関数型プログラミングにおいても特に有用であり、最も一般的な永続データ構造の一つとして、変化後も以前のバージョンを保持できる連想配列や集合の構築に用いられます。赤黒木の永続バージョンは、挿入や削除のたびに空間を必要とし、さらに時間も必要とします。 ${\displaystyle 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を使用する代わりに、赤黒木が使用されるようになりました。これにより、ハッシュコードが衝突する要素の数に応じて、そのような要素をからまで検索する際の時間計算量が改善されます。 ^[26] ${\displaystyle O(m)}$ ${\displaystyle O(\log m)}$ ${\displaystyle m}$

実装

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

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

typedef enum Color : char {     
    黒、 
    赤 
}色; 

typedef enum方向: char {     
    左、 
    右 
}方向; 

// 赤黒木ノード
typedef構造体ノード{   
	struct Node * parent ; // ルートノードの場合はnull   
	ユニオン{ 
		// 結合して ->left/->right または ->child[0]/->child[1] を使用できるようにします
		構造体{ 
			構造体 Node *左;  
			構造体 Node *右;  
		};
		構造体Node *子[ 2 ];  
	};
	色color ; 
	intキー; 
}ノード; 

typedef構造体{  
	構造体 Node *ルート;  
}木; 

静的方向direction ( const Node * N ) {     
    N == N -> parent -> right ? RIGHT : LEFT を返します。       
}

Node * rotate_subtree ( Tree * tree , Node * sub ,方向dir ) {       
	ノード* sub_parent = sub -> parent ;   
	Node * new_root = sub -> child [ 1 - dir ]; // 1 - dir は反対方向です      
	ノード* new_child = new_root -> child [ dir ];   

	sub -> child [ 1 - dir ] = new_child ;    

	if (新しい子) {  
        new_child ->親= sub ;  
    }

	new_root ->子[ dir ] = sub ;  

	new_root ->親=サブ親;  
	サブ->親= new_root ;  
	if (サブ親) {  
		sub_parent -> child [ sub == sub_parent -> right ] = new_root ;    
	}それ以外{  
		ツリー->ルート= new_root ;  
    }

	new_rootを返します。 
}

左回転と
右回転、アニメーション。

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

この提案では、挿入と削除の両方（非常に単純なケースは除く）を、ノード、エッジ、および色からなる6つの集合（ケースと呼ばれる）に分解します。この提案では、挿入と削除の両方において、ルートに黒レベルを1つ近づけてループするケースが1つだけ含まれており、他の5つのケースはそれぞれツリーのバランスを調整します。より複雑なケースは図に示されています。

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

1. アクション「entry」は、ノードの集合を色付きで表示しますが、これはケースを定義しており、多くの場合、いくつかの要件に違反しています。現在のノードN
   は青い枠線で囲まれ、他のノードはNとの関係に応じてラベル付けされています。
2. 回転が有用であると考えられる場合、これは「回転」というラベルが付いた次のアクションに示されます。
3. 色の変更が有用であると考えられる場合は、次の「色」というアクションでそれが示されます。^[30]
4. まだ修復が必要な場合、ケースは他のケースのコードを利用し、現在のノード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は変更されません（短絡評価 を参照）。
（コメントはconsidered black要件2に準拠しています。）

if提案^[29]が実現すれば、関連する発言ははるかに少ない頻度でしか起こらなくなる。

挿入

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

// 親はオプションです
void insert ( Tree * tree , Node * node , Node * parent , Direction dir ) {          
node -> color = RED ; node -> parent = parent ; if ( ! parent ) { tree -> root = node ; return ; } parent -> child [ dir ] = node ; // ツリーのバランスを再調整しますdo { // ケース #1 if ( parent -> color == BLACK ) { return ; } Node * grandparent = parent -> parent ; if ( ! grandparent ) { // ケース #4 parent -> color = BLACK ; return ; } dir = direction ( parent ); Node * uncle = grandparent -> child [ 1 - dir ]; if ( ! uncle || uncle -> color == BLACK ) { if ( node == parent -> child [ 1 - dir ]) { // ケース #5 rotate_subtree ( tree , parent , dir ); node = parent ; parent = grandparent -> child [ dir ]; } // ケース #6 rotate_subtree ( tree , grandparent , 1 - dir ); parent -> color = BLACK ; grandparent -> color =	  
	  

	  
		  
		
	

	  

	
	 
		
		    
             
        

	       

		  
			
			  
			
		

		  
		     
		      
			      
				
				  
				  
				  
			

			
			    
			  
			  RED ; 
return ; } // ケース #2 parent -> color = BLACK ; uncle -> color = BLACK ; grandparent -> color = RED ; node = grandparent ; } while (( parent = node -> parent )); // ケース #3 return ; }			
		
	
		
		  
		  
		  
		  

	    

	
	

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

• ノードは現在のノードであり、最初は挿入ノードです。
• 各反復の開始時にノードは赤になります。
• 要件 3 は、すべてのノード ← 親のペアに対して満たされますが、親も赤の場合(ノードで赤違反) 、ノード←親という例外が発生する可能性があります。
• その他すべてのプロパティ (要件 4 を含む) はツリー全体で満たされます。

挿入図に関する注記

前に

場合

回転

割り当て

後

次

Δ h

P

G

あなた

×

P

G

あなた

×

I1

I2

N := G

?

?

2

—

I3

—

I4

私

I5

P ↶ N

N := P

o

I6

0

o

I6

P ↷ G

挿入 この概要の前欄には、 考えられるすべての星座のケース[31]が網羅されていることが示されています。

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

挿入ケース1

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

挿入ケース2

挿入ケース2

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

挿入ケース3

挿入ケース2が回実行され、ツリー全体の高さは1増加してhになりました 。現在のノードNはツリーの（赤）ルートであり、すべてのRBプロパティが満たされています。 ${\displaystyle {\tfrac {h-1}{2}}}$

挿入ケース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

挿入ケース6

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

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

除去

単純なケース

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

黒い非根葉の除去

複雑なケースは、Nがルートでなく、黒色で表示され、適切な子要素を持たない（⇔ NULLの子要素のみを持つ）場合です。最初の反復処理では、NはNULLに置き換えられます。

void remove ( Tree * tree , Node * node ) {      
Node * parent = node -> parent ; Node * sibling ; Node * close_nephew ; Node * distant_nephew ; Direction dir = direction ( node ); parent -> child [ dir ] = NULL ; goto start_balance ; do { dir = direction ( node ); start_balance : sibling = parent -> child [ 1 - dir ]; distant_nephew = sibling -> child [ 1 - dir ]; close_nephew = sibling -> child [ dir ]; if ( sibling -> color == RED ) { // ケース #3 rotate_subtree ( tree , parent , dir ); parent -> color = RED ; sibling -> color = BLACK ; sibling = close_nephew ; distant_nephew = sibling -> child [ 1 - dir ]; if ( distant_nephew && distant_nephew -> color == RED ) { goto case_6 ; } close_nephew = sibling -> child [ dir ]; if ( close_nephew && close_nephew -> color == RED ) { goto case_5 ; } // ケース #4 sibling -> color = RED ; parent	   

	 
	 
	 

	   

	  
	 

	 
		  

		    
		    
		  
		    
			
			  
			  
			  
			  

			    
			      
				 
            
			  
			      
				 
            

			
			  
			-> color = BLACK ;   
return ; } if ( distant_nephew && distant_nephew -> color == RED ) { goto case_6 ; } if ( close_nephew && close_nephew -> color == RED ) { goto case_5 ; } if ( ! parent ) { // ケース #1 return ; } if ( parent -> color == RED ) { // ケース #4 sibling -> color = RED ; parent -> color = BLACK ; return ; } // ケース #2 sibling -> color = RED ; node = parent ; } while ( parent = node -> parent ); case_5 : rotate_subtree ( tree , sibling , 1 - dir ); sibling -> color = RED ; close_nephew -> color = BLACK ; distant_nephew = sibling ; sibling = close_nephew ; case_6 : rotate_subtree ( tree , parent , dir ); sibling -> color = parent -> color ; parent -> color = BLACK ; distant_nephew -> color = BLACK ; return ; }			
		

		      
			 
        

		      
			 
        

		  
		    
            
        

		    
			
			  
			  
			
		

		
		  
		  

	    



	    
	  
	  
	  
	  



	  
	  
	  
	  
	

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

• 各反復の開始時に、Nの黒の高さは反復回数から1を引いた値に等しい。つまり、最初の反復では0であり、Nは真の黒ノードである。より高い反復で。
• Nを通るパス上のブラック ノードの数は削除前よりも 1 つ少なくなりますが、他のすべてのパスでは変更されません。そのため、他のパスが存在する場合はPでブラック違反が発生します。
• その他すべてのプロパティ (要件 3 を含む) はツリー全体で満たされます。

削除図に関する注記

前に

場合

回転

割り当て

後

次

Δ h

P

C

S

D

P

C

S

D

—

D1

D2

N := P

?

?

1

D3

P ↶ S

N := N

D6

0

D5

0

D4

0

D4

D5

C ↷ S

N := N

D6

0

D6

P ↶ S

削除 この概要の前欄には、色星座の 考えられるすべてのケース[31]が網羅されていることが示されています。

• 以下の図では、PはNの親、SはNの兄弟、C (近い甥を意味する) はNと同じ方向にある S の子、 D (遠い甥を意味する)はSのもう一方の子を表します ( S は、最初の反復では NULL ノードになることはできません。これは、削除前のNの黒の高さである 1 の黒の高さを持つ必要があるためですが、 CとD はNULL ノードになる場合があります)。
• 図では、現在のノードNが親ノードPの左の子として示されていますが、 Nはどちらの側に位置することも可能です。コードサンプルでは、​​side変数を用いて両方の可能性をカバーしていますdir。
• 削除の開始時（最初の反復）において、Nは削除されるノードを置き換えるNULLノードです。親ノードにおける位置のみが重要なので、次のように表記されます。（つまり、現在のノードNはNULLノードであり、左の子ノードである）が削除図の左列に表示されます。操作が進むにつれて、適切なノード（黒の高さが1以上のノード）も現在のノードになる場合があります（例：ケース2を参照）。
• 黒い弾丸を数えることによって（そして削除図において、 Nを通るパスには他のパスよりも丸印が1つ少ないことがわかります。これは、 Pにおいて黒違反（もし存在する場合）があることを意味します。
• 前の列グループの色配列は、列caseで名前が付けられたケースを定義します。これにより、空白セルに入力された値は無視されます。
• 概要の行は、考えられるすべての RB ケースの範囲が簡単に理解できるように順序付けられています。
• 列の回転は、回転が再バランス調整に寄与するかどうかを示します。
• 列の割り当ては、後続の反復ステップに入る前にNが割り当てられていることを示しています。これにより、他のノードP、C、S、Dも再割り当てされる可能性があります。
• ケースによって何かが変更された場合は、の後の列グループに表示されます。
• あ次の列の記号は、このステップでリバランスが完了したことを示します。次の列でケースが1つだけ特定された場合は、そのケースが次のケースとして示されます。そうでない場合は、疑問符が付きます。
• ループとは、親ノードPが新しい現在のノードNになるという点で、再バランス調整の問題がツリー内の上位レベルにエスカレートされる場所です。そのため、ツリーを修復するには最大h回の反復が必要です（ hはツリーの高さ）。エスカレーションの確率は反復ごとに指数関数的に減少するため、再バランス調整の総コストは平均して一定、つまり償却定数となります。（余談ですが、MehlhornとSandersは「AVLツリーは一定の償却更新コストをサポートしていない」と指摘しています^{[16] ：165、158。}これは削除後の再バランス調整には当てはまりますが、AVL挿入には当てはまりません^[32]）。${\displaystyle \Delta h=1}$
• ループ本体の外には、ケース 3、6、5、4、および 1 への終了ブランチがあります。セクション「Delete case 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でのdir-回転により、 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の色は、赤か黒のいずれかのままです（図では、変換前と変換後の両方で同じ色を指すノード（つまり、Dとノード3 ）が存在します。これにより、要件3は維持されます。Nを通過しないサブツリー内のパス（つまり、図ではノードDとノード3を通過するパス）は、以前と同じ数の黒いノードを通過しますが、Nには黒い祖先が1つ追加されます。つまり、Pが黒になったか、元々黒でSが黒い祖先として追加されたかのどちらかです。したがって、 Nを通過するパスは黒いノードを1つ追加で通過するため、要件4が復元され、ツリー全体がRB形状になります。

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

境界の証明

図2: 高さh =1、2、3、4、5の赤黒木RB _h 。それぞれの最小ノード数は1、2、4、6、10。

そこには高さの ある赤黒の木があり、${\displaystyle h\in \mathbb {N} }$ ${\displaystyle h}$

${\displaystyle m_{h}}$	${\displaystyle =2^{\lfloor (h+1)/2\rfloor }+2^{\lfloor h/2\rfloor }-2}$
	${\displaystyle ={\Biggl \{}}$	${\displaystyle 2\cdot 2^{\tfrac {h}{2}}-2=2^{{\tfrac {h}{2}}+1}-2}$		たとえ​ ${\displaystyle h}$
	${\displaystyle 3\cdot 2^{\tfrac {h-1}{2}}-2}$		奇数の 場合${\displaystyle h}$

ノード（は床関数）であり、この高さの赤黒木はより少ないノードでは存在しないため、最小となる。その黒の高さは     （黒根を持つ）または奇数（その場合は赤根を持つ）の場合も   ${\displaystyle \lfloor \,\rfloor }$
${\displaystyle \lceil h/2\rceil }$ ${\displaystyle h}$ ${\displaystyle (h-1)/2~.}$

証拠

ある高さの赤黒木が最小のノード数を持つためには、赤ノード数が最大となる最長経路が1つだけ存在し、それによって木の高さが最大となり、黒ノードの高さが最小となる必要があります。この経路以外はすべて黒ノードでなければなりません。^{[15] : 444 証明の概略}この木からノードが削除されると、高さまたは何らかのRB特性が失われます。

赤い根を持つ高さのRB木は最小である。これは次の式と一致する。 ${\displaystyle h=1}$

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

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

	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (m_{h-1})}$	${\displaystyle +}$	${\displaystyle (1)}$	${\displaystyle +}$	${\displaystyle (2^{\lfloor (h-1)/2\rfloor }-1)}$
			（上位サブツリー）		（根）		（2番目のサブツリー）
その結果
	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (2^{\lfloor h/2\rfloor }+2^{\lfloor (h-1)/2\rfloor }-2)}$	${\displaystyle +}$	${\displaystyle 2^{\lfloor (h-1)/2\rfloor }}$
		${\displaystyle =}$	${\displaystyle 2^{\lfloor h/2\rfloor }+2^{\lfloor (h+1)/2\rfloor }-2}$   ■

関数のグラフは凸型かつ区分線形で、次の点でブレークポイントがあります。この関数は、 ( OEISのシーケンスA027383 ) についてA027383( h –1)として表にまとめられています。${\displaystyle m_{h}}$ ${\displaystyle (h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)}$ ${\displaystyle k\in \mathbb {N} .}$ ${\displaystyle m_{h}=}$ ${\displaystyle h\geq 1}$

関数を解くと${\displaystyle h}$

不等式は となり、奇数の場合は となる。 ${\displaystyle 9>8=2^{3}}$ ${\displaystyle 3>2^{3/2}}$ ${\displaystyle h}$

${\displaystyle 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}$ 。

偶数の場合も奇数の場合も、間隔は ${\displaystyle h}$

	${\displaystyle \log_{2}(n+1)}$	${\displaystyle \leq h\leq }$	${\displaystyle 2\log_{2}(n+2)-2=2\log_{2}(n/2+1)}$	${\displaystyle {\bigl [}<2\log _{2}(n+1)\;{\bigr ]}}$
	（完全な二分木）		（極小赤黒木）

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

結論

ノード（キー）を持つ赤黒木には木の高さがある${\displaystyle n}$ ${\displaystyle h\in O(\log n).}$

集合演算と一括演算

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

• Join : 関数Join は、2つの赤黒木t ₁とt ₂とキーkに対して実行されます。ここでt ₁ < k < t ₂、つまりt ₁のすべてのキーはkより小さく、t ₂のすべてのキーはkより大きい場合です。関数 Join は、 t ₁とt ₂のすべての要素をkとして含む木を返します。

2つの木の黒の高さが同じ場合、Joinは単に左サブツリーt ₁、ルートk、右サブツリーt ₂を持つ新しいノードを作成します。t 1 と t 2 の両方が黒のルートを持つ場合、 kを_赤に設定します。そうでない場合、_kは黒に設定します。

黒の高さが等しくない場合、t _{1 の黒の高さが}t ₂よりも大きいと仮定します(その他の場合は対称的です)。Join は、 t ₁の右のスパインに沿って、 t ₂とバランスの取れた黒ノードcまで進みます。この時点で、左の子がc、ルートk (赤に設定)、右の子がt ₂である新しいノードが作成され、 c が置き換えられます。最大で 3 つの赤ノードが連続して出現できるため、新しいノードによって赤と黒の不変条件が無効になる可能性があります。これは、二重回転で修正できます。二重の赤の問題がルートに伝播した場合、ルートは黒に設定され、プロパティが復元されます。この関数のコストは、2 つの入力ツリー間の黒の高さの差です。

• 分割：赤黒木をキーxより小さい木とキーxより大きい木に分割するには、まず赤黒木にx を挿入することでルートからパスを描きます。この挿入後、 xより小さいすべての値はパスの左側に、 x より大きいすべての値は右側に配置されるようになります。結合を適用すると、左側のすべてのサブツリーが、パス上のキーを下から上への中間ノードとしてボトムアップで結合され、左側のツリーが形成されます。右側の部分は対称形になります。

一部のアプリケーションでは、Split はx が木に存在するかどうかを示すブール値も返します。Split のコストは木の高さのオーダーです。このアルゴリズムは実際には赤黒木の特殊な性質とは何の関係もなく、AVL 木など、結合演算を含む任意の木に使用できます。${\displaystyle O(\log n),}$

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

関数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 ))
    で、 (T L .color=black) かつ (T'.right.color=T'.right.right.color=red) の場合:
        T'.right.right.color=黒;
        return rotateLeft(T')
     return T' /* T ' '[recte T'] */

関数joinLeftRB(T L , k, T R ):
  /* joinRightRB と対称 */

関数join(T L , k, T R ):
     T L .blackHeight>T R .blackHeightの場合:
        T'=joinRightRB(T L ,k,T R )
        の場合(T'.color=red) かつ (T'.right.color=red) の場合:
            T'.color=黒
        T R .blackHeight>T L .blackHeightの場合、 T'
    を返します。
        /* 対称 */
    (T L .color=black) かつ (T R .color=black)
        の場合: Node(T L ,⟨k,red⟩,T R )
    を返します。Node (T L ,⟨k,black⟩,T R )
を返します。

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

関数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') = 分割(T.left, k)
        戻り値(L',b,join(R',T.key,T.right))
    (L',b,R') = split(T.right, k)
    戻り値(join(T.left,T.key,L'),b,T.right)

集合AとBを表す2つの赤黒木t ₁とt _{2の和集合は、} A ∪ Bを表す赤黒木tである。次の再帰関数は、この和集合を計算する。

関数union(t 1 , t 2 ):
     t 1 = NULL の場合t 2を返すt 2 = NULL の場合t 1を返す
    (L 1 ,b,R 1 )=split(t 1 ,t 2 .key)
    
    proc1=開始:
        T L =union(L 1 ,t 2 .left)
    proc2=開始:
        T R =union(R 1 ,t 2 .right)
    すべてのproc1、proc2
    を待機し、 join(T L , t 2 .key, T R )
を返します。

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

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

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

並列アルゴリズム

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

赤黒木の結合ベースのアルゴリズムは、結合、交差、構築、フィルター、マップ削減などの一括操作に対して並列です。

並列バルク操作

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

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

結合ベース

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

1. まず、挿入する要素のバルクIをソートする必要があります。
2. その後、アルゴリズムはI をほぼ等しいサイズの部分に分割します。${\displaystyle k\in \mathbb {N} ^{+}}$ ${\displaystyle \langle I_{1},\cdots ,I_{k}\rangle }$
3. 次に、木T は、 との範囲が対応する部分のみで重なるようにk個の部分に分割される必要があります( )。言い換えると、順序付けにより、すべての に対して次の制約が成り立ちます。 ${\displaystyle \langle T_{1},\cdots ,T_{k}\rangle }$ ${\displaystyle I_{m}}$ ${\displaystyle T_{n}}$ ${\displaystyle m=n}$ ${\displaystyle j\in \mathbb {N} ^{+}|\,1\leq j<k}$
   1. ${\displaystyle {\text{last}}(I_{j})<{\text{first}}(T_{j+1})}$
   2. ${\displaystyle {\text{last}}(T_{j})<{\text{first}}(I_{j+1})}$
4. アルゴリズムは の各要素を に順次挿入します。このステップはすべてのjに対して実行する必要があり、最大k 個のプロセッサで並列に実行できます。${\displaystyle I_{j}}$ ${\displaystyle T_{j}}$
5. 最後に、結果のツリーが結合され、操作全体の最終結果が形成されます。

ステップ 3 の分割の制約により、ステップ 5 でツリーを再度結合し、結果のシーケンスをソートできることが保証されることに 注意してください。

• 
  初期ツリー
• 
  IとTを分割する
• 
  スプリットTに挿入
• 
  Tに参加

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

バルク挿入(T, I, k):
    I.ソート()
    一括挿入Rec(T, I, k)

bulkInsertRec (T, I, k):
     k = 1の
        場合: forall e in I: T.insert(e)
    そうでない場合
        m := ⌊size(I) / 2⌋
        (T 1 , _, T 2 ) := split(T, I[m])
        バルク挿入Rec(T 1 , I[0 .. m], ⌈k / 2⌉)
            || bulkInsertRec(T 2 , I[m + 1 .. size(I) - 1], ⌊k / 2⌋)
        T ← join2(T 1 , T 2 )

実行時間

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

#再帰レベル	${\displaystyle \in O(\log k)}$
T(分割) + T(結合)	${\displaystyle \in O(\log |T|)}$
スレッドあたりの挿入数	${\displaystyle \in O\left({\frac {|I|}{k}}\right)}$
T(挿入)	${\displaystyle \in O(\log |T|)}$
T(bulkInsert)、k = #プロセッサ	${\displaystyle \in O\left(\log k\log |T|+{\frac {|I|}{k}}\log |T|\right)}$

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

仕事

#分割、#結合	${\displaystyle \in O(k)}$
W(分割) + W(結合)	${\displaystyle \in O(\log |T|)}$
#挿入	${\displaystyle \in O(|I|)}$
W(挿入)	${\displaystyle \in O(\log |T|)}$
W(一括挿入)	${\displaystyle \in O(k\log |T|+|I|\log |T|)}$

パイプライン

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

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

• 
  初期ツリー
• 
  挿入位置を見つける
• 
  ステージ1では要素を挿入する
• 
  ステージ1ではノードの修復が始まります
• 
  ステージ2では要素を挿入する
• 
  ステージ2ではノードの修復が始まります
• 
  ステージ3では要素を挿入する
• 
  ステージ3ではノードの修復が始まります
• 
  ステージ3ではノードの修復を継続します

実行時間

この解析ではソートIは考慮されません。また、は より小さいと仮定されます。そうでない場合、結果のツリーを最初から構築する方が効率的です。 ${\displaystyle |I|}$ ${\displaystyle |T|}$

T(挿入位置を見つける)	${\displaystyle \in O(\log |T|)}$
#ステージ	${\displaystyle \in O(\log |I|)}$
T(挿入) + T(修復)	${\displaystyle \in O(\log |T|)}$
T(bulkInsert) と~ # 個のプロセッサ${\displaystyle |I|}$	${\displaystyle \in O(\log |I|+2\cdot \log |T|)}$ ${\displaystyle =O(\log |T|)}$

仕事

W(挿入位置を見つける)	${\displaystyle \in O(|I|\log |T|)}$
#挿入、#修理	${\displaystyle \in O(|I|)}$
W(挿入) + W(修復)	${\displaystyle \in O(\log |T|)}$
W(一括挿入)	${\displaystyle \in O(2\cdot |I|\log |T|)}$ ${\displaystyle =O(|I|\log |T|)}$

参照

• データ構造のリスト
• ツリーデータ構造
• 木の回転
• 順序統計木
• AAツリー、赤黒ツリーのバリエーション
• 左寄りの赤黒木
• AVLツリー
• Bツリー（2-3ツリー、2-3-4ツリー、B+ツリー、B*ツリー、UBツリー）
• スケープゴートの木
• スプレーツリー
• Tツリー
• WAVLツリー
• GNU libavl

参考文献と注釈

1. コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2001). 「赤黒木」.アルゴリズム入門（第2版）. MIT Press. pp. 273–301. ISBN 978-0-262-03293-3。
2. パトン、ジェームズ. 「赤黒樹」.
3. Morris, John (1998). 「赤黒木」.データ構造とアルゴリズム.
4. Bayer, Rudolf (1972). 「対称バイナリBツリー：データ構造とメンテナンスアルゴリズム」. Acta Informatica . 1 (4): 290– 306. doi :10.1007/BF00289509. S2CID  28836825.
5. Drozdek, Adam (2001). 『Javaにおけるデータ構造とアルゴリズム』（第2版）. Sams Publishing. p. 323. ISBN 978-0534376680。
6. Guibas, Leonidas J. ; Sedgewick, Robert (1978). 「バランスツリーのための二色フレームワーク」.第19回コンピュータサイエンス基礎シンポジウム議事録. pp.  8– 21. doi :10.1109/SFCS.1978.3.
7. “Red Black Trees”. foreverlyconfuzzled.com . 2007年9月27日時点のオリジナルよりアーカイブ。 2015年9月2日閲覧。
8. Sedgewick, Robert (2012). Red–Black BSTs. Coursera.多くの人から、なぜ「赤黒」という名前を使ったのかと聞かれます。実は、このデータ構造、バランスツリーの見方を、パーソナルコンピュータや、今日私たちが身近に享受しているグラフィックユーザーインターフェース、イーサネット、オブジェクト指向プログラミングなど、その他多くの革新の発祥地であるゼロックスPARCで発明したからです。しかし、そこで発明されたものの一つがレーザー印刷で、当時カラー印刷ができるカラーレーザープリンターが普及し、その色の中で最も見栄えが良かったのが赤でした。そこで、3つのノードにある赤いリンク、つまりリンクの種類を区別するために、赤色を選びました。これが、これまで尋ねてきた質問への答えです。
9. 「「Red/Black Tree」という用語はどこから来たのか？」programmers.stackexchange.com . 2015年9月2日閲覧。
10. Andersson, Arne (1993-08-11). 「バランス探索木をシンプルに」 Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (編). 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-1. 2018年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.
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) .
15. セジウィック, ロバート; ウェイン, ケビン (2011). アルゴリズム（第4版）. Addison-Wesley Professional. ISBN 978-0-321-57351-3。
16. 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。
17. コーメン, トーマス;レイサーソン, チャールズ;リベスト, ロナルド;スタイン, クリフォード(2022). 「13. 赤黒木」.アルゴリズム入門（第4版）. MITプレス. pp. 331–332. ISBN 9780262046305。
18. クヌースの順序の定義を用いると、子供の最大数は
19. セジウィック, ロバート(1998). C++ アルゴリズム. Addison-Wesley Professional. pp. 565–575. ISBN 978-0-201-35088-3。
20. 「IBM Developer」. developer.ibm.com . 2024年5月25日閲覧。
21. 「epollの実装（1）」。Datong's Random Thoughts . 2014年9月。2020年10月11日時点のオリジナルよりアーカイブ。 2018年6月25日閲覧。
22. パフ 2004
23. "Robert Sedgewick" (PDF) . Cs.princeton.edu . 2020年6月4日. 2022年3月26日閲覧。
24. 「Balanced Trees」（PDF） . Cs.princeton.edu . 2022年3月26日閲覧。
25. デメイン、ED;ハーモン、D.イアコノ、J.パトラシュク、M. (2007)。 「動的最適性 - ほぼ」(PDF)。SIAM ジャーナル オン コンピューティング。37 (1): 240.土井:10.1137/S0097539705447347。S2CID  1480961。
26. 「JAVAでHashMapはどのように動作するのか」。coding-geek.com。
27. Tarjan, Robert Endre (1985年4月). 「償却計算複雑度」(PDF) . SIAM Journal on Algebraic and Discrete Methods . 6 (2): 306– 318. doi :10.1137/0606031.
28. これらのツリーの回転で重要なことは、ツリーのノードの順序が保持されることです。
29. 左列には右列よりもはるかに少ないノードが含まれており、特に削除に関しては顕著です。これは、最初の反復処理を挿入と削除のバランス調整ループから除外することで、ある程度の効率化が図れることを示しています。なぜなら、名前付きノードの多くは最初の反復処理ではNILノードであり、その後は完全に非NILノードとなるからです。（この注釈も参照してください。）
30. 分かりやすさを考慮し、回転は色付けの前に配置されています。しかし、回転と色付けは互いに可換であるため、回転を末尾に移動することは自由に選択できます。
31. 同じ分割が Ben Pfaff にも見られます。
32. Dinesh P. Mehta、Sartaj Sahni（編）データ構造とアプリケーションハンドブック10.4.2
33. 上限における等式は、ノードが偶数の高さの最小RB木RB _{2 k}に対してのみ成立する。したがって、この不等式は、Cormen p. 264 に見られるような広く用いられている例よりもわずかに正確である。さらに、これらの木は、RB要件1から4を満たす色付けを1つだけ許容する二分木である。しかし、他にもそのような木が存在する。例えば、黒い葉に子ノードを追加すると、必ず赤になる。（奇数の高さの最小RB木では、根の色を赤から黒に反転させることができる。）${\displaystyle 2\cdot k}$ ${\displaystyle n=2\cdot 2^{k}-2}$ ${\displaystyle h<2\log_{2}(n+1),}$
    
34. Blelloch, Guy E. ; Ferizovic, Daniel; Sun, Yihan (2016). 「並列順序集合のためのJust Join」(PDF) .第28回ACMアルゴリズムとアーキテクチャにおける並列性シンポジウム議事録. 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). 「赤黒木のための並列アルゴリズム」.理論計算機科学. 262 ( 1– 2): 415– 435. doi : 10.1016/S0304-3975(00)00287-5 .ソートされたアイテムリストから赤黒木を構築する並列アルゴリズムは、CRCW PRAM上のプロセッサと同期して動作し、 EREW PRAM上のプロセッサと同期して動作します。 ${\displaystyle n}$ ${\displaystyle O(1)}$ ${\displaystyle n}$ ${\displaystyle O(\log \log n)}$ ${\displaystyle n/\log \log n}$
36. サンダース、ピーター (2019). メルホーン、カート; ディーツフェルビンガー、マーティン; デメンティエフ、ローマン (編).シーケンシャルおよびパラレルアルゴリズムとデータ構造：基本ツールボックス. シュプリンガー電子書籍. 出版社: シュプリンガー. 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.

さらに読む

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

外部リンク

• Ben Pfaff:二分探索木とバランス木入門.フリーソフトウェア財団, ボストン 2004, ftp.gnu.org (PDF gzip; 1662 kB)
• C言語で書かれた完全かつ動作する実装
• OCW MIT 講義「赤黒樹」Erik Demaine著
• YouTubeでの二分探索木挿入の視覚化– 基本的な二分探索木と左傾斜赤黒木におけるランダムおよび事前ソートされたデータ挿入の視覚化
• C++で書かれた侵入型赤黒木
• 3.3 バランス探索木における赤黒BST
• 赤黒BSTデモ