挿入コストの証明の概略
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/02 05:57 UTC 版)
「スケープゴート木」の記事における「挿入コストの証明の概略」の解説
ノード v の不平衡度を、左ノードと右ノードの間のサイズの差の絶対値から1を引いた物と0のいずれか大きい方として定義する。 I ( v ) = max ( | left ( v ) − right ( v ) | − 1 , 0 ) {\displaystyle I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)} v を根とする部分木を再構築した直後ではI( v )=0 である。 補題： vを根とする部分木を再構築する直前では I ( v ) ∈ Ω ( | v | ) {\displaystyle I(v)\in \Omega (|v|)} （ Ω {\displaystyle \Omega } は漸近記法。） 補題の証明： v 0 {\displaystyle v_{0}} を再構築直後の部分木の根とする。ここで、再構築直後では完全に平衡であるため、その高さ h(v_0) は h ( v 0 ) = log ( | v 0 | + 1 ) {\displaystyle h(v_{0})=\log(|v_{0}|+1)} となる。 もし Ω ( | v 0 | ) {\displaystyle \Omega (|v_{0}|)} 回の高さが1増加するような挿入（つまり、挿入された各ノードが高さを1ずつ増やす場所）が生じた場合、 I ( v ) ∈ Ω ( | v 0 | ) {\displaystyle I(v)\in \Omega (|v_{0}|)} h ( v ) = h ( v 0 ) + Ω ( | v 0 | ) {\displaystyle h(v)=h(v_{0})+\Omega (|v_{0}|)} log ( | v | ) ≤ log ( | v 0 | + 1 ) + 1 {\displaystyle \log(|v|)\leq \log(|v_{0}|+1)+1} 。 となる。再構築の直前に I ( v ) ∈ Ω ( | v | ) {\displaystyle I(v)\in \Omega (|v|)} が成り立つため、vを根とする部分木に Ω ( | v | ) {\displaystyle \Omega (|v|)} 回の挿入では再構築が行われない。そのため、これらの挿入はそれぞれ、探索のために O ( log n ) {\displaystyle O(\log n)} 時間しかかからない。そしてその後コスト O ( | v | ) {\displaystyle O(|v|)} の再構築を生じる挿入が生じる。ここまでの処理で償却時間を計算すると、 Ω ( | v | ) O ( log n ) + O ( | v | ) Ω ( | v | ) = O ( log n ) {\displaystyle {\Omega (|v|)O(\log {n})+O(|v|) \over \Omega (|v|)}=O(\log {n})} となり、O(log n)である。 （スケープゴートが高さhであるような再構築はO(2^h-1 )回に1度生じる一方で、高さhの完全二分木にはO(2^h)程度のノードしか持たない。そのため再構築には高々定数時間しか増えない。）
※この「挿入コストの証明の概略」の解説は、「スケープゴート木」の解説の一部です。
「挿入コストの証明の概略」を含む「スケープゴート木」の記事については、「スケープゴート木」の概要を参照ください。
- 挿入コストの証明の概略のページへのリンク
