挿入ケース5
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
親Pは赤だが、おじUは黒。最終的な目標は、親ノードPを祖父母の位置に回転させることだが、NがGの内側の孫の場合（つまり、NがGの右子の左子またはGの左子の右子の場合）、これはうまくいかない。Pでdir-回転を行うと、カレントノードNとその親Pの役割が入れ替わる。この回転により、Nを通る経路（図中の2の部分木）が追加され、Pを通る経路（図中の4の部分木）が削除される。しかし、PもNも赤なので、要件5は維持される。要件4はケース6で復元される。 Case_I56: // Pは赤 && Uは黒: if (N == P->child[1-dir]) { // Case_I5 (Pは赤 && Uは黒 && NはGの内側の孫): RotateDir(P,dir); // Pは根にはならない N = P; // 新しいカレントノード P = G->child[dir]; // Nの新しい親 // Case_I6に該当する } → 記号の説明 最初の反復 上位の反復 挿入ケース6
※この「挿入ケース5」の解説は、「赤黒木」の解説の一部です。
「挿入ケース5」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
ウィキペディア小見出し辞書の「挿入ケース5」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 挿入ケース5のページへのリンク
