AVL木
AVL木では、1つのデータを挿入、削除する度に全てのノードが条件を満たしているか調べる。ここでは、その手がかりとして各ノードに平衡係数を持たせることを考える。平衡係数は以下のように各ノードの左右部分木の高さの差で定義する(左右は逆でもよい)。
平衡係数は挿入や削除などの操作の度に再計算する。すなわち、左部分木の方が高くなるほど+1、右部分木の方が高くなるほど-1すればよい。
平衡係数が2以上または-2以下のノードが存在する時、木の再構成が必要である。再構成後は平衡係数を更新する。