索引はこちら
「A」で始まる主なワード
A
AVL木
その他の語句
用語の解説
AVL木とは
（エーブイエルキ,AVL tree,）
AVL木とは、2分木の中でも、どの節点においても、左右の部分木の高さの差が1以下の平衡（バランスが取れた）木のことである。
2分木に何の工夫もなしに単純にデータを追加していくと、最悪の場合には、一本道の木構造になってしまい、木とする意味がなくなる。
そこで、左右の木の偏りを修正する手法として、データの追加・削除で高さの差が2以上となりバランスが崩れると、木の再構成を行うことでAVL木を構築するという手法が考案された。
なお、AVLの名称は、上記手法を考案した2人の数学者であるAdelson-VelskiiとLandisにちなんで命名された。
