挿入ケース2
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
親PとおじUの両方が赤なら、両方を黒に塗り替え、祖父母Gを赤にすることで要件5を維持することが可能となる。親やおじを通る経路は必ず祖父母を通るので、これらの経路上の黒ノードの数は変わっていない。しかし、祖父母Gが赤の親を持つ場合、要件4に違反する可能性がある。GをNにラベル付けした後、ループ不変条件が満たされるので、1つ上の黒レベル（＝2の木レベル）でリバランシングを繰り返すことができるようになる。 // Case_I2 (PとUが赤): P->color = BLACK; U->color = BLACK; G->color = RED; N = G; // 新しいカレントノード // 1段階上の黒を反復 // (= 2の木レベル) } while ((P = N->parent) != NULL); // (do while)ループの終了
※この「挿入ケース2」の解説は、「赤黒木」の解説の一部です。
「挿入ケース2」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
ウィキペディア小見出し辞書の「挿入ケース2」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 挿入ケース2のページへのリンク
