削除ケース1
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
P、S、Sの子は黒である。Sを赤にした後、Sを通るすべての経路（正確にはNを通らない経路）は、黒ノードが1つ少なくなる。ここで、Pをルートとする部分木のすべての経路は同じ数の黒ノードを持つが、Pを通らない経路より1つ少ないので、まだ要件4に違反している可能性がある。PをNにラベル付けした後、ループ不変条件が満たされるので、1上の黒レベル（=1上の木レベル）でリバランシングを繰り返すことができる。 // Case_D1 (P+C+S+Dは黒): S->color = RED; N = P; // 新しいカレントノード (根かもしれない) // 1黒レベル(1木レベル)を上げながら反復する } while ((P = N->parent) != NULL); // (do while)-ループの終了
※この「削除ケース1」の解説は、「赤黒木」の解説の一部です。
「削除ケース1」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
ウィキペディア小見出し辞書の「削除ケース1」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 削除ケース1のページへのリンク
