スケープゴート木

スケープゴート木とは

スケープゴート木は、計算機科学における平衡二分探索木の一種です。Arne Andersson、Igal Galperin、ロナルド・リベストによって発明されました。このデータ構造は、探索、挿入、削除の各操作において、償却時間計算量がO(log n)という効率的な性能を発揮します。特に探索においては、最悪時間計算量もO(log n)である点が大きな特徴です。

特徴

他の平衡二分探索木と異なる点として、スケープゴート木はノードごとに新たな情報を保持しないため、メモリオーバーヘッドが少ないことが挙げられます。具体的には、各ノードはキーと左右の子ノードへのポインタのみを保存します。これにより、実装が容易になるだけでなく、データ構造アライメントによってノードのオーバーヘッドを最大で3分の1まで削減できます。

多くの平衡木が平衡を維持するために頻繁に単純な処理を行うのに対し、スケープゴート木は複雑な処理を低頻度で実行するという点で異なります。スケープゴート木では、平衡を保つために「スケープゴート」と呼ばれる特定のノードを根とする部分木を完全二分木として再構築します。この再構築処理により、更新操作の時間計算量は最悪の場合O(n)となります。

理論

二分探索木は、ノードの半分が根の左側に、もう半分が右側にある場合に平衡であるとされます。この概念を拡張し、α-(重さ)平衡なノードは、以下の基準を満たすノードとして定義されます。

size(left) ≤ α size(node)
size(right) ≤ α size(node)

ここで、size関数は次のように再帰的に定義されます。


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)であるスプレー木よりも効率的です。また、他の平衡二分探索木と比較してノードのメモリオーバーヘッドが少ないため、参照の局所性により高速化が期待できます。

挿入

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

挿入位置の探索時には、挿入ノードの深さも記録します。これは、根から探索で子に移動する回数を数える単純なカウンターで実装可能です。挿入するノードがα-高さ平衡条件に違反する場合、以下の再構築処理を行います。

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

スケープゴートを見つけるためには、挿入ノードから根まで遡り、α-重み平衡が満たされない最初のノードを選択します。根に戻るには、根からの探索経路を保存するか、各ノードが持つ親ポインタを利用します。

スケープゴートノードが有効なスケープゴートであるかを確認するには、以下のα-重み平衡条件を確認します。

size(left) ≤ αsize(node)
size(right) ≤ αsize(node)

最適化のため、3つのサイズのうち2つを計算しておき、残りの1つのみを計算することで効率化できます。例えば挿入ノードから順に根まで処理することで、スケープゴート木全体を走査できます。親のノードを根とする部分木のサイズは、自分自身を根とする部分木のサイズと、兄弟ノードの部分木のサイズと1を加算することで計算できます。


size(parent) = size(node) + size(sibling) + 1


また、ノードを1つずつ挿入することから、挿入されたノードのサイズは1です。


size(inserted node) = 1


したがって、次の計算を繰り返すことでサイズを計算できます。


size[x+1] = size[x] + size(sibling) + 1


ここで、xは現在見ているノード、x+1はその親です。size[x]は前回のsize[x+1]を再利用できるため、実際に必要な関数呼び出しはsize(sibling)のみとなります。

スケープゴートが見つかると、そのノードを根とする部分木を完全二分木に再構築します。この再構築は、部分木のノードを中央値が部分木のノードとなるように再帰的に選択することで、O(n)時間で完了します。

再構築にはO(n)時間かかるため、挿入の最悪時間計算量はO(n)となりますが、これらのケースは頻繁には起こらないため、挿入にかかる償却時間計算量はO(log n)となります。

挿入コストの証明の概略

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


I(v) = max(|left(v) - right(v)| - 1, 0)


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

補題：vを根とする部分木を再構築する直前では、I(v) ∈ Ω(|v|)となります。

補題の証明：
v0を再構築直後の部分木の根とします。このとき、再構築直後で完全に平衡であるため、高さh(v0)は以下のようになります。


h(v0) = log(|v0| + 1)


もしΩ(|v0|)回の高さが1増加するような挿入（挿入された各ノードが高さを1ずつ増やす位置）が生じた場合、I(v) ∈ Ω(|v0|)となります。


h(v) = h(v0) + Ω(|v0|)


log(|v|) ≤ log(|v0| + 1) + 1


再構築直前では、I(v) ∈ Ω(|v|)が成り立つため、vを根とする部分木にΩ(|v|)回の挿入が行われても再構築は行われません。これらの挿入はそれぞれ探索にO(log n)しかかからず、その後コストO(|v|)の再構築が発生します。償却時間計算量を計算すると


(Ω(|v|)O(log n) + O(|v|)) / Ω(|v|) = O(log n)


となり、O(log n)が証明できます。

(スケープゴートが高さhである再構築はO(2^h-1)回に1度生じるのに対し、高さhの完全二分木にはO(2^h)程度のノードしか持たない。そのため、再構築にかかる時間は高々定数倍にしかならない。)

削除

スケープゴート木は、挿入よりも削除が簡単な珍しい二分木です。削除の準備として、スケープゴート木は構造とは別に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)となります。


(Σ[1 to n/2]O(log n) + O(n)) / (n/2) = ((n/2)O(log n) + O(n)) / (n/2) = O(log n)

語源

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

関連項目

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

参考文献

Galpern, Igal (September 1996). On Consulting a Set of Experts and Searching (PDF) (Ph.D. thesis). MIT.
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日閲覧。

外部リンク

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

もう一度検索