非根の黒葉ノードの削除
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
複雑なケースは、Nが根でなく、黒色で、NILの子だけを持つ（⇔色が正確な子を持たない）場合である。最初の反復で、NはNILに置き換えられる。 void RBdelete2( RBtree* T, // -> 赤黒木 struct RBnode* N) // -> 削除対象ノード { struct RBnode* P = N->parent; // -> Nの親ノード byte dir; // Nの位置するPの側 (∈ { LEFT, RIGHT }) struct RBnode* S; // -> Nの兄弟ノード struct RBnode* C; // -> 近いおい struct RBnode* D; // -> 遠いおい // P != NULL, Nは根ではないので。 dir = childDir(N); // ノードNが位置する親Pの側（LEFT か RIGHT） // 親PのNをNILに置き換える: P->child[dir] = NIL; goto Start_D; // ループに移動する // (do while)-ループの開始: do { dir = childDir(N); // ノードNの位置する親Pの側Start_D: S = P->child[1-dir]; // Nの兄弟 (黒高さ >= 1) D = S->child[1-dir]; // 遠いおい C = S->child[ dir]; // 近いおい if (S->color == RED) goto Case_D3; // Sが赤 ===> P+C+Dが黒 // S is black: if (D != NIL && D->color == RED) // 黒でないとみなす goto Case_D6; // Dが赤 && Sが黒 if (C != NIL && C->color == RED) // 黒でないとみなす goto Case_D5; // Cが赤 && S+Dが黒 // ここでは、両方のおい == NIL (最初の反復) または黒 (上位の反復). if (P->color == RED) goto Case_D4; // Pが赤 && C+S+Dが黒 リバランシングループは以下の不変条件を持つ。 各反復の始めに、Nの黒高さは反復番号から1を引いたものに等しく、これは最初の反復では0であり、上位の反復ではNは真の黒ノード であることを意味する。 Nを通る経路の黒ノード数は削除前より1つ少ないが、それ以外の経路では変化しないので、他の経路が存在する場合はPで黒違反が発生することになる。 他のすべての性質（性質4を含む）は、木全体で満たされている。
※この「非根の黒葉ノードの削除」の解説は、「赤黒木」の解説の一部です。
「非根の黒葉ノードの削除」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
- 非根の黒葉ノードの削除のページへのリンク
