スケープゴート木
二分探索木は、ノードの半分が根の左側にあり、もう半分が右側にある場合に、平衡であるつまり重みのバランスが取れていると言う。この概念を拡張し、α-(重さ)平衡なノードとは、以下の緩和されたウェイトバランス基準を満たすノードとして定義される。
上記のサイズは次のように再帰的に定義される。
α=1の場合、平衡から最も遠い木(すべてのノードが片方にしかノードを持たず、実質リストである状態)でもこの条件を満たすのに対し、α= 0.5はほとんど完全な二分木のみ条件を満たす。
α-(重さ)平衡の二分探索木は、α-高さ平衡である。つまり、
対偶により、α-高さ平衡でない木は、α-(重さ)平衡ではない。
スケープゴート木は常にα-平衡を維持するわけではないが、以下の緩和されたα-高さ平衡を保つ。
この高さ平衡条件に反する状態は、ノードの挿入時に検出でき、重み平衡に反する部分の存在も意味する。
このスケープゴート木高さの制限は赤黒木に似ている。 ただし、平衡のための操作(スケープゴート木の再構築、赤黒木の回転)が行われるノードの決定する実装が大きく異なる。