サンプルコードと挿入図・削除図に関する注記
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
「赤黒木」の記事における「サンプルコードと挿入図・削除図に関する注記」の解説
この提案では、挿入と削除（非常に単純なケースを除く）の両方を、ノード、エッジ、カラーの6つの組合せで分解し、ケースと呼ぶことにする。ケースを修復（リバランシング）するコードは、後続のケースのコードを使用することがある。この提案では、挿入と削除の両方について、根とループに黒レベルを1つずつ近づけるケースを正確に含み、他の5つのケースはそれ自体で木をリバランシングする。より複雑なケースは、図に描かれる。 変数 N はカレントノードを表し、図中では N と表される。 は赤ノードを、 は（黒高さ ≥ 1 の）非NILの黒ノードを表し、（非NIL）ノード は赤・黒ノードのどちらでも良いが、同じ図の中では同じ色である。真のNILノードは図に描かれない。 図には3つの列と2～4つのアクションが含まれる。左の列は最初の反復を、右の列はそれ以上の反復を、中央の列は1つのケースを異なるアクションに分割したものを表す。 動作 "entry" は、ケースを定義するノードの集まりとその色を示し、ほとんどの場合、いくつかの要件に違反している。カレントノードNは青い枠で囲まれ、他のノードはNとの関係によってラベル付けされている。 回転が有効であると判断された場合は、次の動作は "rotate" とラベル付された絵となる。 再色付けが有効であると判断された場合は、次の動作は "color" とラベル付された絵となる。 まだ修復の必要がある場合、ノードの集まりは、新たに割り当てられたカレントノードNで挿入または削除のループ不変条件を満たし、再び青枠を持つようになる。また、Nに対して他のノードが新たに割り当てられる可能性もある。この動作は "reassign "とラベル付けされている。その後に続く動作は、他のケースのコードを再利用し、根に1つ近い黒レベルの反復となることもある。 番号が書かれた黒丸を頂点とする三角形（）は、赤黒木の部分木（要件4に従ってその親に接続）を表し、黒高さは反復レベルから1を引いた値に等しい。つまり最初の反復では0である。その部分木の根は、赤でも黒でもよい。番号が書かれた三角形（）は、黒高さが1つ少ない赤黒木の部分木を表し、すなわちその親は2回目の反復で黒高さが0になる。 コメント 簡単のため、サンプルコードでは論理和とU == NIL || U->color == BLACK // 黒とみなす 論理積をU != NIL && U->color == RED // 黒でないとみなす 使用する。 そのため、U == NIL の場合、論理和・論理積ともに式全体が評価されないことに留意する必要がある。この場合、どちらの場合も U->colorは評価されない（短絡評価参照）。(黒とみなすというコメントは、要件2に準じたものである。） この提案が実現すれば、関連するif文の発生頻度を大幅に減らすことができる。
※この「サンプルコードと挿入図・削除図に関する注記」の解説は、「赤黒木」の解説の一部です。
「サンプルコードと挿入図・削除図に関する注記」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
- サンプルコードと挿入図・削除図に関する注記のページへのリンク
