AVL木
AVL木の削除における平衡条件の確認は、探索してきた経路上の全てのノードが平衡条件を満たしていることを確認する必要は必ずしもなく、探索してきた経路上に平衡係数が1もしくは-1のノードを見つけた時点で処理を終了できる。
なぜなら、削除により平衡係数が1もしくは-1になったノードがあるということは、削除前のそのノードの左右部分木の高さは等しかったが、削除により一方の部分木の高さが1小さくなったということであり、そのノードを根とする部分木の高さは削除前後で変わっていないので、全てのノードが平衡条件を満たしていることがわかるからである。
ただし、探索してきた経路上のどこかのノードを回転したり、平衡係数が0のノードを見つけても処理を終了できない。
なぜなら、削除は木の高さを1小さくする操作であるのに対して、回転も木の高さを1小さくする操作であるから、これらの操作によって平衡条件を満たさなくなったノードが出てくる可能性があるためである。また、削除により平衡係数が0になったノードがあるということは、削除前に高さが1大きかった方の部分木から削除したということであるから、そのノードを根とする部分木の高さは1小さくなるので、同様の可能性がある。