削除ケース3
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
兄弟ノードSは赤だから、PとおいのCとDは黒でなければならない。Pでdir-回転すると、SがNの祖父母ノードになる。そして、PとSの色を反転させても、Nを通る経路は黒ノードが1つ少ないままである。しかし、Nは赤の親Pと黒の兄弟Sを持っているので、ケースD4、D5、D6の変換で赤黒木の形を復元することができる。 Case_D3: // Sは赤 && P+C+Dは黒: RotateDirRoot(T,P,dir); // Pは根かもしれない P->color = RED; S->color = BLACK; S = C; // != NIL // ここで: Pは赤 && Sは黒 D = S->child[1-dir]; // 遠いおい if (D != NIL && D->color == RED) goto Case_D6; // Dは赤 && Sは黒 C = S->child[ dir]; // 近いおい if (C != NIL && C->color == RED) goto Case_D5; // Cは赤 && S+Dは黒 // それ以外のC+Dは黒とみなす。 // Case_D4に該当する。 → 記号の説明 最初の反復 上位の反復 削除ケース4
※この「削除ケース3」の解説は、「赤黒木」の解説の一部です。
「削除ケース3」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
ウィキペディア小見出し辞書の「削除ケース3」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 削除ケース3のページへのリンク
