削除ケース6
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
兄弟Sは黒、Sの遠い子Dは赤である。Pでdir-回転した後、兄弟SはPとSの遠い子Dの親となる。PとSの色を交換し、Dを黒にする。部分木の根は依然として同じ色、すなわち赤か黒（図中の ）であり、これは変換前も変換後も同じ色を指している。こうすることで、要件4が守られる。Nを通らない部分木の経路（図中のDとノード3を通る経路）は、以前と同じ数の黒ノードを通るが、Nには黒ノードの祖先が1つ追加される。Pが黒くなったか、Pが黒かったのにSの祖父母が黒くなったか、のどちらかである。したがって、Nを通過する経路は、さらに1つの黒ノードを通過するので、要件5が回復し、全体の木は赤黒木の形になる。 Case_D6: // Dは赤 && Sは黒: RotateDirRoot(T,P,dir); // Pは根かもしれない S->color = P->color; P->color = BLACK; D->color = BLACK; return; // 削除終了} // RBdelete2の終了 このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレースである。
※この「削除ケース6」の解説は、「赤黒木」の解説の一部です。
「削除ケース6」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
ウィキペディア小見出し辞書の「削除ケース6」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 削除ケース6のページへのリンク
