スケープゴート木のソースを表示

{{Infobox data structure
|name=Scapegoat tree
|type=木
|invented_by=アルネ・アンダーソン、アイガル・ガリペリン、[[ロナルド・リベスト]]
|space_avg=O(n)
|space_worst=O(n)
|search_avg=O(log n)
|search_worst=O(log n)
|insert_avg=O(log n)
|insert_worst=償却されたO(log n)
|delete_avg=O(log n)
|delete_worst=償却されたO(log n)
}}'''スケープゴートツリー'''は[[計算機科学]]における[[平衡二分探索木]]の一種である。Arne Anderssonと、Igal Galperinと[[ロナルド・リベスト]]によって発明された<ref name="galperin_rivest">{{Cite conference|first1=Igal|last=Galperin|first2=Ronald L.|last2=Rivest|authorlink2=Ronald L. Rivest|title=Scapegoat trees|journal=Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms|pages=165–174|year=1993|url=http://people.csail.mit.edu/rivest/pubs/GR93.pdf|isbn=0-89871-313-7|publisher=[[Society for Industrial and Applied Mathematics]]|place=Philadelphia}}</ref>。探索、挿入、削除の償却時間計算量が[[ランダウの記号|''O'']](log ''n'')であり、探索においては最悪時間計算量も''O''(log ''n'')である。 

探索の最悪時間計算量が''O''(log ''n'')である他の平衡二分探索木と異なる特徴として、スケープゴート木はノードごとに新たな要素を持たないため、メモリオーバーヘッドがない。つまり、ノードはキーと左右の子を指す2つのポインタのみを保存する。この性質によって、スケープゴート木の実装が容易になる上、[[データ構造アライメント]]によりノードのオーバーヘッドを最大3分の1に削減できる。 

多くの平衡木は、平衡を維持するために何度も簡単な処理を呼ぶが、スケープゴート木は複雑な処理を低確率で呼ぶという違いがある。スケープゴート木では平衡を維持するために、「スケープゴート」と呼ばれる特定のノードを根とする部分木を完全二分木として再構築する。したがって、スケープゴート木の更新の時間計算量は、最悪の場合''O'' (''n'')である。 

== 理論 ==
二分探索木は、ノードの半分が根の左側にあり、もう半分が右側にある場合に、平衡であるつまり重みのバランスが取れていると言う。この概念を拡張し、α-（重さ）平衡なノードとは、以下の緩和されたウェイトバランス基準を満たすノードとして定義される。 
 size(left) ≤ α*size(node)
 size(right) ≤ α*size(node)
上記のサイズは次のように再帰的に定義される。 
 '''function''' size(node) '''is'''
     '''if''' node = nil '''then'''
         '''return''' 0
     '''else'''
         '''return''' size(node<nowiki>-></nowiki>left) + size(node<nowiki>-></nowiki>right) + 1
     '''end if'''
 '''end function'''
α=1の場合、平衡から最も遠い木（すべてのノードが片方にしかノードを持たず、実質リストである状態）でもこの条件を満たすのに対し、α= 0.5は[[二分木|ほとんど完全な二分木]]のみ条件を満たす。 

α-（重さ）平衡の二分探索木は、'''α'''-'''高さ平衡'''である。つまり、 
 height(tree) ≤ floor(log<sub>1/α</sub> size(tree))
対偶により、α-高さ平衡でない木は、α-（重さ）平衡ではない。 

スケープゴート木は常にα-平衡を維持するわけではないが、以下の緩和されたα-高さ平衡を保つ。 
 height(scapegoat tree) ≤ floor(log<sub>1/α</sub> size(tree) + 1
この高さ平衡条件に反する状態は、ノードの挿入時に検出でき、重み平衡に反する部分の存在も意味する。 

このスケープゴート木高さの制限は[[赤黒木]]に似ている。 ただし、平衡のための操作（スケープゴート木の再構築、赤黒木の回転）が行われるノードの決定する実装が大きく異なる。赤黒木は場所を決定するために各ノードに追加の「色」情報を格納しますが、スケープゴート木は、再構築を実行するためにα-重さ平衡が満たされていない'''スケープゴート'''を見つける。これは、実際の回転がノードの平衡に依存するという点で[[AVL木]]似ているが、平衡を決定する方法が大きく異なる。 AVL木は挿入/削除のたびに平衡を確認するため、通常はその確認のための値「平衡係数」を各ノードに格納する。一方でスケープゴート木では、スケープゴートを見つける必要がある場合にのみ平衡であるかを計算し、新たな値をノードが持たなくて良い。 

他のほとんどの平衡二分探索木と異なり、スケープゴート木はその平衡度合いに関して柔軟に対応できる。つまり、0.5<α<1である任意のαに対して実装が可能である。 α値が高いほど平衡から遠い状態を許容するため、平衡化の処理が起きにくくなり、挿入操作は速くなるが、探索と削除が遅くなる。αが低い場合はその逆である。 したがって、実際には、これらの操作の生じる頻度に応じてαを調節できる。 

== 操作 ==

=== 探索 ===
探索手法は標準の二分探索木と変わらない。平衡二分探索木なため、最悪時間計算量は''O''(log ''n'' )。[[スプレー木]]は探索に最悪時間計算量が''O''( ''n'' )であるため、スプレー木より効率的である。他の平衡二分探索木と比較すると、ノードのメモリオーバーヘッドが少ないため、[[参照の局所性]]による速度改善が可能である。 

=== 挿入 ===
挿入操作は、一般的な二分探索木とほとんど同じだが、スケープゴートによる平衡化の処理が追加される。 

挿入する場所の探索では、挿入するノードの"深さ"も記録する。これは、根から探索で子に移動する回数を数えるだけの単純なカウンターで実装すれば、根と挿入されるノード間の辺の数を効率的に（''O''(log ''n'')で）計算できる。挿入するノードが（上記で定義された）α-高さ平衡条件に反している場合、以下の再構築を行う。 

再構築は、'''スケープゴート'''を根とする部分木全体を平衡化する操作である。スケープゴートは、挿入されたノードの先祖であり、α-重み平衡が満たされないノードである。再構築を必要とするとき、つまりα-高さ平衡条件に反している場合には、そのような先祖は1つ以上存在する。 それらのいずれかをスケープゴートとして部分木を再構築することでα-高さ平衡の条件が満たされた木が得られる。 

スケープゴートを見つけるためには、例えば挿入するノードから根まで遡り、α-重み平衡が満たされない最初のノードを選択すれば良い。 

根に戻るには、根からの探索経路を保存した''O''(log ''n'' )のメモリか、各ノードが持つ親ポインタを用いれば良い。 

上記のスケープゴートノードが実行可能なスケープゴートであるかどうかを判断するには、そのα-重み平衡が満たされているかを確認れば良い。これの確認には、定義通り以下を確認すれば良い。 
 size(left) ≤ α*size(node)
 size(right) ≤ α*size(node)
ただし、3つのサイズのうち2つを計算しておき、3つ目のサイズのみを計算することで、大規模に最適化できる。例えば挿入されたノードから順に根まで順次行うことで、スケープゴート木全体に処理を行う。親のノードを根とする部分木のサイズは、自分自身を根とする部分木のサイズと、兄弟（親が同じであるノードであり、自分自身ではないノード）の部分木のサイズと親のノードの数である1を足せば求まる。   

 size(parent) = size(node) + size(sibling) + 1
また、ノードを挿入する際にはノードを1つずつ挿入することから以下も成り立つ。 
 size(inserted node) = 1.
つまり、以下の計算を繰り返せば良い。 
 size[x+1] = size[x] + size(sibling) + 1  

ここで、x は現在見ているノード、x+1 はその親である。size[x]は前回のsize[x+1] を再利用すれば良いため、size(sibling)が実際に必要な唯一の関数呼び出しとなる。スケープゴートを見つけると、スケープゴートを根とする部分木を再構築し、この部分木は完全二分木となる<ref name="galperin_rivest">{{Cite conference|first1=Igal|last=Galperin|first2=Ronald L.|last2=Rivest|authorlink2=Ronald L. Rivest|title=Scapegoat trees|journal=Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms|pages=165–174|year=1993|url=http://people.csail.mit.edu/rivest/pubs/GR93.pdf|isbn=0-89871-313-7|publisher=[[Society for Industrial and Applied Mathematics]]|place=Philadelphia}}</ref>。この再構築は、部分木のノードを、中央値を部分木のノードとするように再帰的に選択すれば、''O''( ''n'' )時間で実行できる。 

再構築操作には''O''( ''n'' )時間（部分木のサイズ）がかかるため、挿入の時間計算量は最悪の場合''O''( ''n'' )になる。 ただし、これらの最悪のケースは頻発しないため、挿入にかかる'''償却'''時間は''O''(log ''n'' )で済む。 

==== 挿入コストの証明の概略 ====
ノード ''v の''不平衡度を、左ノードと右ノードの間のサイズの差の絶対値から1を引いた物と0のいずれか大きい方として定義する。 

<math>I(v) = \operatorname{max}(|\operatorname{left}(v) - \operatorname{right}(v)| - 1, 0) </math>

''v を''根とする部分木を再構築した直後ではI( ''v'' )=0 である。 

'''補題：''' ''v''を根とする部分木を再構築する直前では <math>I(v) \in \Omega (|v|) </math> （ <math>\Omega </math> は[[ランダウの記号|漸近記法]]。） 

補題の証明： 

<math>v_0</math>を再構築直後の部分木の根とする。ここで、再構築直後では完全に平衡であるため、その高さ ''h''(''v''_0) は<math>h(v_0) = \log(|v_0| + 1) </math> となる。 もし<math>\Omega (|v_0|)</math>回の高さが1増加するような挿入（つまり、挿入された各ノードが高さを1ずつ増やす場所）が生じた場合、 

<math>I(v) \in \Omega (|v_0|) </math> <math>h(v) = h(v_0) + \Omega (|v_0|) </math><math>\log(|v|) \le \log(|v_0| + 1) + 1 </math> 。 

となる。再構築の直前に<math>I(v) \in \Omega (|v|)</math>が成り立つため、''v''を根とする部分木に<math>\Omega (|v|)</math>回の挿入では再構築が行われない。そのため、これらの挿入はそれぞれ、探索のために<math>O(\log n)</math>時間しかかからない。そしてその後コスト<math>O(|v|)</math> の再構築を生じる挿入が生じる。ここまでの処理で償却時間を計算すると、 

<math>{\Omega (|v|) O(\log{n}) + O(|v|) \over \Omega (|v|)} = O(\log{n}) </math>

となり、''O''(log ''n'')である。

（スケープゴートが高さ''h''であるような再構築はO(2^<sup>''h''-1</sup> )回に1度生じる一方で、高さ''h''の完全二分木にはO(2^<sup>''h''</sup>)程度のノードしか持たない。そのため再構築には高々定数時間しか増えない。）

=== 削除 ===
スケープゴート木は、挿入より削除の方が簡単である珍しい二分木である。削除の準備として、スケープゴート木は木構造と別に1つ値を格納する必要がある。MaxNodeCountと呼ばれるこの値は、再構築されるまで、後述するNodeCountの最大値を保持する。木全体が再構築されるたびにMaxNodeCountは更新され、挿入処理の最後にはmax（MaxNodeCount、NodeCount）と更新される。 

削除を実行するには、単純な二分探索木と同様にノードを削除するだけですが、もし 
  NodeCount≤α* MaxNodeCount 
となった場合には、MaxNodeCountをNodeCountに更新した上で、木全体を再構築する。これにより、最悪でも''O''( ''n'' )時間の処理ではあるが、償却時間は''O''(log ''n'' )で済む。   

==== 削除コストの証明の概略 ====
スケープゴート木が<math>n</math>要素を持ち、再構築された直後とする（つまり、完全二分木であるとする）。 高々<math>n/2 - 1</math>回の削除は、木を再構築する前に実行できる。 これらの削除には、それぞれ <math>O(\log{n})</math>時間（要素を探索し、削除済みとしてフラグを立てる時間）しかかからない。その後、<math>n/2</math>回目の削除において木が再構築され、 <math>O(\log{n}) + O(n)</math> （あるいは単に<math>O(n)</math> ）の時間がかかる。以上を考慮すると以下のように償却コストが<math>O(\log{n})</math>である。 

<math>
{\sum_{1}^{{n \over 2}} O(\log{n}) + O(n) \over {n \over 2}} = 
{{n \over 2}O(\log{n}) + O(n) \over {n \over 2}} = 
O(\log{n}) \ 
</math>

== 語源 ==
'''スケープゴート木'''は''「何かがうまくいかない場合、人々はまず責任者（スケープゴート）を探す一般的な知識に基づく。」''<ref name="opendatastructures">{{Cite book|chapterurl=http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html|title=Open Data Structures (in pseudocode)|chapter=Chapter 8 - Scapegoat Trees|url=http://opendatastructures.org/versions/edition-0.1g/ods-python/ods-python-html.html|edition=0.1G β|first=Pat|last=Morin|author-link=Pat Morin|accessdate=2017-09-16}}</ref> [[聖書]]では、 スケープゴートは儀式的に他人の罪を負い、その後追い払われる動物（身代わり、生け贄）を意味する。 

== 関連項目 ==

* [[スプレー木]] 
* [[木構造 (データ構造)|木]] 
* [[木の回転]] 
* [[AVL木]] 
* [[B木|B]]木 

== 参考文献 ==
{{Reflist}}

== 外部リンク ==

* [http://people.ksp.sk/~kuko/bak/index.html スケープゴートツリーアプレット] by Kubo Kovac 
* {{Cite thesis|url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-700.pdf|title=On Consulting a Set of Experts and Searching|type=Ph.D. thesis|first=Igal|last=Galpern|publisher=[[Massachusetts Institute of Technology|MIT]]|date=September 1996}} 
* {{Cite book|chapterurl=http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html|title=Open Data Structures (in pseudocode)|chapter=Chapter 8 - Scapegoat Trees|url=http://opendatastructures.org/versions/edition-0.1g/ods-python/ods-python-html.html|edition=0.1G β|first=Pat|last=Morin|accessdate=2017-09-16}} 
[[Category:償却データ構造]]
[[Category:探索木]]
[[Category:二分木]]
{{デフォルトソート:すけえふこおとき}}