探索木の順序に高さの条件を加える
AVL木は、二分探索木のキー順序を守りながら、各節点で左右の部分木の高さの差を高々1に保つ木です。根だけでなく、すべての節点でこの条件を満たす必要があります。普通の二分探索木へ昇順の値を入れると、一方向に伸びて検索が線形時間へ近づくことがあります。AVL木は偏りを修復し、高さを要素数の対数程度に抑えます。説明では、空の部分木の高さを0、葉の高さを1とする規約を使います。実装で別の規約を使ってもよいですが、差の計算と保存する高さの更新を同じ定義でそろえることが重要です。
30・20・10を順に挿入する
空の木へ30、20、10を通常の探索順で入れると、30の左に20、20の左に10が付きます。節点30から見て左の高さは2、右は0なので、差は2となり条件に反します。この左・左の偏りには30を中心とする右回転を行い、20を新しい根、10を左、30を右にできます。中間のキー20を上げるため、左側のキーが小さく右側のキーが大きい順序は保たれます。回転はキーを勝手に並べ替えて探索条件を捨てる操作ではありません。親からの参照や移動する部分木の接続も正しく更新する必要があります。
内側へ曲がる偏りは二段階で直す
30、10、20の順なら、30の左の10から右へ20が付きます。この左・右の形は、単純に30だけを右回転しても望む釣合いになりません。まず10を中心に左回転し、次に30を中心に右回転すると、20の左右に10と30が来ます。右・左は対称の二重回転です。どの回転を選ぶかは、現在の不均衡な節点と、その子の部分木の高さなどから判断します。挿入のキー方向だけを見て書いた判定を、そのまま削除へ流用すると誤る場合があります。回転の名前を暗記するより、どの部分木をどこへつなぐかをキーの範囲で説明します。
高さ情報は接続変更の後に直す
節点に高さを保存する実装では、子の高さから1+max(左,右)を再計算します。回転で下へ移った節点を先に更新し、それから上へ来た節点を更新しないと、古い値を使って次の判定を誤る場合があります。二分探索木として正しくキーを返していても、高さ情報が壊れたままでは後の追加や削除で問題が表面化します。重複キーを許すのか、同じキーの値を置き換えるのかも決めます。等しいキーを左右へ適当に分けると、削除や探索の前提が曖昧になります。木の構造、保存した高さ、重複の規則を別々の検査項目にします。
削除は上まで影響が続く場合がある
削除では、後継などを使った通常の探索木の削除に加え、減った高さの影響を祖先へ伝えて釣合いを修復します。一つの回転で局所的に直っても、さらに上の高さが変わる場合があります。したがって最初の不均衡だけ修復して常に終了する、という方針は十分ではありません。探索、挿入、削除の計算量がO(log n)となるのは、キー比較などを一定費用とみなし、高さ不変条件を維持する前提です。長い文字列の比較やオブジェクトの確保など、実際の費用も別に考えます。高さが低いことだけで、あらゆる入力に最速とは言えません。
不変条件を再帰的に検査する
試験では、中間順の走査が期待するソート列と一致すること、すべての節点の高さ差が高々1であること、保存した高さが再計算した値と一致することを確認します。昇順、降順、交互の挿入、存在しないキーの削除、根の削除などを含めます。30・20・10と30・10・20の例は回転の違いを確かめる手計算です。汎用の実装を検証するなら、参照用の集合や辞書と照合し、削除も混ぜて繰り返します。回転回数や検索時間を報告する場合は実行条件を残し、ここでの構造の説明を測定した性能値として扱わないようにします。