挿入ケース6
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
カレントノードNは、Gの外側の孫（左子の左子または右子の右子）であることが確定している。今度はGで(1-dir)-回転して、Gの代わりにPを置き、PをNとGの親とすると、要件4に違反するため、Gは黒、Gの前の子Pは赤となる。PとGの色を入れ替えた後の木は、要件4を満たしている。黒Gを経由していた経路はすべて黒Pを経由するようになったので、要件5も満たしたままである。 // Case_I6 (Pは赤 && Uは黒 && NはGの外側の孫): RotateDirRoot(T,G,1-dir); // Gは根である可能性がある P->color = BLACK; G->color = RED; return; // 挿入完了} // RBinsert1の終了 このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレースである。
※この「挿入ケース6」の解説は、「赤黒木」の解説の一部です。
「挿入ケース6」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
ウィキペディア小見出し辞書の「挿入ケース6」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 挿入ケース6のページへのリンク
