AVL木

AVL木（えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree）とは、計算機科学|コンピュータサイエンスにおいて、「どの木構造 (データ構造)#用語|ノードの左右木構造 (データ構造)#用語|部分木の木構造 (データ構造)#用語|高さの差も1以下」という条件を満たす2分探索木のことである。平衡2分探索木の1つで、木に対する操作によって条件を満たさないノードが発生しても、木の回転|回転と呼ばれる操作を行うだけで木をAVL木に再構成でき、平衡を維持できる。AVL木は最初に考案された平衡2分探索木であり、その名は1962年に論文を発表したソビエト社会主義共和国連邦|ソ連の2人の数学者、とに由来する。