削除図に関する注記
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
前の状態 ケース→ 回転 割り当て 後の状態 →次 Δh P C S D P C S D — D2 → D3 P↶S N:=N ? ? ? 0 D1 N:=P ? ? 1 D4 → D5 C↷S N:=N D6 0 D6 P↶S → 削除: この一覧表では、前の状態の列で、ノード群の起こりうるすべてのケースをカバーしている。 図表において、PがNの親ノード、SがNの兄弟ノード、CがSのNと同じ方向の子ノード（近いおい）、DがSのもう一方の子ノード（遠いおい）となる（Sは削除前のNの黒高さが1でなければならないので最初の反復でNILノードにはなれないが、CとDはNILノードになってもよい）。 図では、カレントノードNが親Pの左の子となっているが、Nは左右どちら側にも存在することが可能である。サンプルコードでは、サイド変数 dir によって、両方の可能性をカバーしている。 削除の初め（最初の反復）では、Nは削除されるノードの代わりにNILノードである。親ノードでの位置だけが重要なので、削除図の左欄には （意味：カレントノードNはNILノードで左の子）で記号化される。操作を進めると、（黒高さ ≥ 1の）非NILのノードもカレントノードになる可能性がある(例：ケースD1参照)。 削除図にある黒丸（ と ）を数えることで、Nを通る経路は他の経路より黒丸が1つ少ないことがわかる。これはPでの黒違反を意味する。 前の状態の列グループはケースを定義し、その名前がケースの列で与えられる。そのため、空欄のセルの値は無視される。 一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。 回転の列は、回転がリバランシングに寄与しているかどうかを示す。 割り当ての列は、後続のステップに入る前にNへの割り当てが行われることを示す。これにより、他のノードP、C、S、Dも同様に再割り当てが行われる可能性がある。 ケースによってノードに変更があった場合、後の状態の列グループに示される。 次の列の矢印→は、このステップでリバランシングが完了したことを意味する。後の状態の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。 ループは Start_D から削除ケース1までのセクションに含まれ、親Pが新しいカレントノードNになることで、リバランスの問題が木で Δ h = 1 {\displaystyle \Delta h=1} レベル高くエスカレートされる。そのため、木の修復には最大で h {\displaystyle h} 回の繰り返しが必要になる（ h {\displaystyle h} は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に償却された定数になる。（ただ、余談だが Mehlhorn & Sandersが指摘している。"AVL木は一定の償却更新コストをサポートしない":165,158これは、削除後のリバランシングには当てはまるが、AVL挿入には当てはまらない。） ループの本体からは、ケースD3、D6、D5 + D6、D4、D2への分岐があり、削除ケース3セクションは、それ自体でケースD6、D5、D4への3種類の分岐がある。 D6とD5 ＋ D6とD3 ＋ D5 ＋ D6で回転が発生するが、すべてループの外側である。したがって、最大で合計3回の回転が発生する。 → 記号の説明 最初の反復 上位の反復 削除ケース1
※この「削除図に関する注記」の解説は、「赤黒木」の解説の一部です。
「削除図に関する注記」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
- 削除図に関する注記のページへのリンク
