スケープゴート木
ノード v の不平衡度を、左ノードと右ノードの間のサイズの差の絶対値から1を引いた物と0のいずれか大きい方として定義する。
I ( v ) = max  ( | left  ( v ) − right  ( v ) | − 1 , 0 ) {\displaystyle I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)}
v を根とする部分木を再構築した直後ではI( v )=0 である。
補題: vを根とする部分木を再構築する直前では I ( v ) ∈ Ω ( | v | ) {\displaystyle I(v)\in \Omega (|v|)} ( Ω {\displaystyle \Omega } は漸近記法。)
補題の証明:
v 0 {\displaystyle v_{0}} を再構築直後の部分木の根とする。ここで、再構築直後では完全に平衡であるため、その高さ h(v_0) は h ( v 0 ) = log  ( | v 0 | + 1 ) {\displaystyle h(v_{0})=\log(|v_{0}|+1)} となる。 もし Ω ( | v 0 | ) {\displaystyle \Omega (|v_{0}|)} 回の高さが1増加するような挿入(つまり、挿入された各ノードが高さを1ずつ増やす場所)が生じた場合、
スケープゴートツリーは計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された。探索、挿入、削除の償却時間計算量がO(log n)であり、探索においては最悪時間計算量もO(log n)である。
探索の最悪時間計算量がO(log n)である他の平衡二分探索木と異なる特徴として、スケープゴート木はノードごとに新たな要素を持たないため、メモリオーバーヘッドがない。つまり、ノードはキーと左右の子を指す2つのポインタのみを保存する。この性質によって、スケープゴート木の実装が容易になる上、データ構造アライメントによりノードのオーバーヘッドを最大3分の1に削減できる。
多くの平衡木は、平衡を維持するために何度も簡単な処理を呼ぶが、スケープゴート木は複雑な処理を低確率で呼ぶという違いがある。スケープゴート木では平衡を維持するために、「スケープゴート」と呼ばれる特定のノードを根とする部分木を完全二分木として再構築する。したがって、スケープゴート木の更新の時間計算量は、最悪の場合O (n)である。