リカーシブスローダウン
この例のカウンタは3種類の数字から成り、増加のみをサポートする。しかし減算など別の演算を定数時間の計算量でサポートする場合、さらに多くの数字を使う必要があり、不変条件は複雑になってしまう。そこで各ノードの状態を3つの状態に分類して不変条件を統一する。
ノードをその状態により緑・黄・赤に分類する。前の例では0, 1, 2の桁がそれぞれ緑・黄・赤となる。赤はそのままでは処理できないが、次の桁を変化させて自身を緑にできるような状態である。緑は黄に変化する場合はあるが、1回の変化で赤になることはない。黄はそれ以外であり、1回の変化で赤になる可能性がある。このとき不変条件は次のようになる。
「赤である任意の桁の下には0個以上の黄が続き、さらにその下の桁に緑が必ずある」
連続する黄は1つのノードとして表現する。