読み方：エーブイエルき

AVL木【Adelson-Velskii and Landis' tree】

概要

AVL木とは、データの探索を効率的に行うための二分探索木の一種で、左右の枝の高さのバランスを常に一定の範囲内に保つ自己調整機能を持つもの。

通常の二分探索木では、データの追加順序によっては木が片側に偏り、探索時間が線形に近づく問題が生じることがある。AVL木はこの問題を防ぐため、各ノードに左右の部分木の高さ差を示す平衡係数を持たせ、その値が一定範囲を超えた場合に再構成処理を行う。これにより木全体の高さ（根から最も遠い葉までの距離）が常に対数オーダーに保たれ、探索効率が安定する。

具体的には、高さ差が2以上になったら「回転」と呼ばれる操作を実施し、部分木の構造を調整して高さの均衡を回復する。回転操作には単回転と二重回転があり、挿入や削除によって生じた不均衡の型に応じて適切な方法が選択される。これらの操作は局所的な構造変更であり、二分探索木としての順序性は維持される。

AVL木は検索性能の安定性が高い反面、回転処理やバランス情報の管理が必要となるため、実装が比較的複雑である。データの追加や削除が頻繁に行われると再平衡処理の計算コストが発生するが、探索頻度の方が大きい用途では探索の計算コストの削減によって相殺され、全体として性能向上を図ることができる。大規模なデータを扱うデータベースや解析システムなどで広く用いられている。