AVL木
AVL木の削除は、通常の二分探索木と同様の削除操作を行ったあと、平衡条件を満たしているか調べ、満たしていない場合は回転を行う。
挿入と同様に、まずは探索してきた経路上を「削除したノードの親ノード」から「根ノード」に向かって順に調べていく。平衡条件を満たさないノードがあった場合、そのノードと高い方の部分木の根ノードに着目して単回転、または複回転を行う。
なお、削除するノードが子ノードを2つ持つ場合、削除するノードの左部分木のうち最大値を持つノード(もしくは右部分木のうち最小値を持つノード)を探索して、削除するノードと置き換える処理が発生するが、ここで探索した経路も記憶しておく必要があることに注意する。ノードを削除するのは置き換え後なので、平衡条件の確認も置き換えられた先の親ノードから始めなければならない。