スケープゴート木

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

Scapegoat tree
種類
発明者 アルネ・アンダーソン、アイガル・ガリペリン、ロナルド・リベスト
ビッグオー記法における時間計算量 (en
アルゴリズム 平均 最悪の場合
空白 O(n) O(n)
探索 O(log n) O(log n)
挿入 O(log n) 償却されたO(log n)
削除 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->left) + size(node->right) + 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.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)が実際に必要な唯一の関数呼び出しとなる。スケープゴートを見つけると、スケープゴートを根とする部分木を再構築し、この部分木は完全二分木となる[1]。この再構築は、部分木のノードを、中央値を部分木のノードとするように再帰的に選択すれば、O( n )時間で実行できる。

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

挿入コストの証明の概略編集

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

 

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

補題: vを根とする部分木を再構築する直前では   漸近記法。)

補題の証明:

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

    

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

 

となり、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 )で済む。

削除コストの証明の概略編集

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

 

語源編集

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

関連項目編集

参考文献編集

  1. ^ a b Galperin, Igal; Rivest, Ronald L. (1993). “Scapegoat trees”. Philadelphia: Society for Industrial and Applied Mathematics. 165–174. ISBN 0-89871-313-7. http://people.csail.mit.edu/rivest/pubs/GR93.pdf 
  2. ^ Morin, Pat. “Chapter 8 - Scapegoat Trees”. Open Data Structures (in pseudocode) (0.1G β ed.). http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html 2017年9月16日閲覧。 

外部リンク編集