スケープゴート木

**スケープゴートツリー**は計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された。探索、挿入、削除の償却時間計算量が''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(nodeleft) + size(noderight) + 1
     **end if**
 **end function**
α=1の場合、平衡から最も遠い木（すべてのノードが片方にしかノードを持たず、実質リストである状態）でもこの条件を満たすのに対し、α= 0.5はほとんど完全な二分木のみ条件を満たす。 

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

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

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

他のほとんどの平衡二分探索木と異なり、スケープゴート木はその平衡度合いに関して柔軟に対応できる。つまり、0.5I(v) = \operatorname{max}(|\operatorname{left}(v) - \operatorname{right}(v)| - 1, 0) 

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

**補題：** *v*を根とする部分木を再構築する直前では I(v) \in \Omega (|v|)  （ \Omega  は漸近記法。） 

補題の証明： 

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

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

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

{\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*)程度のノードしか持たない。そのため再構築には高々定数時間しか増えない。）

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

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

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


{\sum_{1}^ O(\log{n}) + O(n) \over {n \over 2}} = 
 = 
O(\log{n}) \ 


## 語源
**スケープゴート木**は*「何かがうまくいかない場合、人々はまず責任者（スケープゴート）を探す一般的な知識に基づく。」* 聖書では、 スケープゴートは儀式的に他人の罪を負い、その後追い払われる動物（身代わり、生け贄）を意味する。 

## 関連項目

* スプレー木 
* 木 
* 木の回転 
* AVL木 
* B木 

## 参考文献

## 外部リンク

* スケープゴートツリーアプレット by Kubo Kovac 
*  
*