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