スケープゴート木

name=Scapegoat treeスケープゴートツリーは計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された。探索、挿入、削除の償却時間計算量が//O//であり、探索においては最悪時間計算量も//O//である。

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

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

1. 理論
-----

二分探索木は、ノードの半分が根の左側にあり、もう半分が右側にある場合に、平衡であるつまり重みのバランスが取れていると言う。この概念を拡張し、α-平衡なノードとは、以下の緩和されたウェイトバランス基準を満たすノードとして定義される。 size ≤ α*size size ≤ α*size 上記のサイズは次のように再帰的に定義される。function size isif node = nil thenreturn 0elsereturn size + size + 1end ifend function α=1の場合、平衡から最も遠い木でもこの条件を満たすのに対し、α= 0.5はほとんど完全な二分木のみ条件を満たす。

α-平衡の二分探索木は、α-高さ平衡である。つまり、 height ≤ floor) 対偶により、α-高さ平衡でない木は、α-平衡ではない。

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

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

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

2. 操作
-----

2.1. 探索
-------

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

2.2. 挿入
-------

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

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

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

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

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

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

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

ここで、x は現在見ているノード、x+1 はその親である。size[x]は前回のsize[x+1] を再利用すれば良いため、sizeが実際に必要な唯一の関数呼び出しとなる。スケープゴートを見つけると、スケープゴートを根とする部分木を再構築し、この部分木は完全二分木となる。この再構築は、部分木のノードを、中央値を部分木のノードとするように再帰的に選択すれば、//O//時間で実行できる。

再構築操作には//O//時間がかかるため、挿入の時間計算量は最悪の場合//O//になる。 ただし、これらの最悪のケースは頻発しないため、挿入にかかる償却時間は//O//で済む。

2.2.1. 挿入コストの証明の概略
------------------

ノード //v の//不平衡度を、左ノードと右ノードの間のサイズの差の絶対値から1を引いた物と0のいずれか大きい方として定義する。

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

補題： //v//を根とする部分木を再構築する直前では

補題の証明：

を再構築直後の部分木の根とする。ここで、再構築直後では完全に平衡であるため、その高さ //h// は となる。 もし回の高さが1増加するような挿入が生じた場合、

。

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

となり、//O//である。

2.3. 削除
-------

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

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

2.3.1. 削除コストの証明の概略
------------------

スケープゴート木が要素を持ち、再構築された直後とする。 高々回の削除は、木を再構築する前に実行できる。 これらの削除には、それぞれ 時間しかかからない。その後、回目の削除において木が再構築され、 の時間がかかる。以上を考慮すると以下のように償却コストがである。

3. 語源
-----

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

4. 関連項目
-------

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

5. 参考文献
-------

6. 外部リンク
--------

[1] by Kubo Kovac
url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-700.pdf
chapterurl=http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html