スケープゴート木
I ( v ) ∈ Ω ( | v 0 | ) {\displaystyle I(v)\in \Omega (|v_{0}|)} h ( v ) = h ( v 0 ) + Ω ( | v 0 | ) {\displaystyle h(v)=h(v_{0})+\Omega (|v_{0}|)} log  ( | v | ) ≤ log  ( | v 0 | + 1 ) + 1 {\displaystyle \log(|v|)\leq \log(|v_{0}|+1)+1} 。
となる。再構築の直前に I ( v ) ∈ Ω ( | v | ) {\displaystyle I(v)\in \Omega (|v|)} が成り立つため、vを根とする部分木に Ω ( | v | ) {\displaystyle \Omega (|v|)} 回の挿入では再構築が行われない。そのため、これらの挿入はそれぞれ、探索のために O ( log  n ) {\displaystyle O(\log n)} 時間しかかからない。そしてその後コスト O ( | v | ) {\displaystyle O(|v|)} の再構築を生じる挿入が生じる。ここまでの処理で償却時間を計算すると、
Ω ( | v | ) O ( log  n ) + O ( | v | ) Ω ( | v | ) = O ( log  n ) {\displaystyle {\Omega (|v|)O(\log {n})+O(|v|) \over \Omega (|v|)}=O(\log {n})}
となり、O(log n)である。
(スケープゴートが高さhであるような再構築はO(2^ )回に1度生じる一方で、高さhの完全二分木にはO(2^)程度のノードしか持たない。そのため再構築には高々定数時間しか増えない。)
スケープゴート木は、挿入より削除の方が簡単である珍しい二分木である。削除の準備として、スケープゴート木は木構造と別に1つ値を格納する必要がある。MaxNodeCountと呼ばれるこの値は、再構築されるまで、後述するNodeCountの最大値を保持します。木全体が再構築されるたびにMaxNodeCountは更新され、挿入処理の最後にはmax(MaxNodeCount、NodeCount)と更新されます。
削除を実行するには、単純な二分探索木と同様にノードを削除するだけですが、もし
となった場合には、MaxNodeCountをNodeCountに更新した上で、木全体を再構築する。これにより、最悪でもO( n )時間の処理ではあるが、償却時間はO(log n )で済む。