挿入図に関する注記
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/01 09:37 UTC 版)
前の状態 ケース→ 回転 割り当て 後の状態 →次 Δh P G U x P G U x — I3 → I1 → — I4 → I2 N:=G ? ? 2 i I5 P↶N N:=P o I6 0 o I6 P↷G → 挿入: この一覧表では、前の列で、ノード群の起こりうるすべてのケースをカバーしている。 図表において、PはNの親、GはNの祖父母、UはNのおじを表す。 図では、PはGの左の子として表されているが、Pは左右どちら側にも存在する可能性がある。サンプルコードでは、サイド変数 dir によって、両方の可能性をカバーしている。 Nは挿入ノードであるが、操作を進めると他のノードもカレントノードになる可能性がある（ケースI2を参照）。 図で、PがNと同じく赤色の場合は、赤違反であることを表している。 x列は子の向きの変化を表し、o（外側）はPとNがともに左またはともに右の子であることを意味し、i（内側）はPからNへの方向がGからPへの方向と違うことを意味する。 前の状態の列グループはケースを定義し、その名前がケースの列で与えられる。そのため、空欄のセルの値は無視される。したがって、ケースI2の場合、対応する図ではNの子方向は1つだが、サンプルコードでは両方の可能性をカバーしている。 一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。 回転の列は、回転がリバランシングに寄与しているかどうかを示す。 割り当ての列は、後続のステップに入る前にNへの割り当てが行われることを示す。これにより、他のノードP、G、Uも同様に再割り当てが行われる可能性がある。 ケースによってノードに変更があった場合、後の状態の列グループに示される。 次の列の矢印→は、このステップでリバランシングが完了したことを意味する。後の状態の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。 ループは挿入ケース1と挿入ケース2の章に含まれ、ケースI2では、Gが新しいカレントノードNになるという意味で、リバランシングの問題が Δ h = 2 {\displaystyle \Delta h=2} レベル高い木にエスカレートされる。そのため、木の修復には最大で h 2 {\displaystyle {\tfrac {h}{2}}} 回の繰り返しが必要になる（ここで h {\displaystyle h} は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に償却された定数になる。 ループの本体から、ケースI1は単独で抜け、ケースI4、I6、I5 + I6、I3への終了分岐がある。 回転はI6とI5 + I6の時にループの外側で発生する。したがって、合計で最大2回の回転が発生する。
※この「挿入図に関する注記」の解説は、「赤黒木」の解説の一部です。
「挿入図に関する注記」を含む「赤黒木」の記事については、「赤黒木」の概要を参照ください。
- 挿入図に関する注記のページへのリンク
