†AVL木(AVL-tree)とは、どの節点においても、「その左部分木の高さ」と「右部分木の高さ」の差が1以下となる木のことである。名称の由来は、考案者のAdel'son-Vel'skiiとLandisから来ている。データの追加・削除で高さの差が2以上になった場合には、木の再構成が行われる。†AVL木にデータを追加する場合は、2分探索木と同じように該当場所を探し、そこに追加する。ここで、追加した結果、左右の高さの差が2になる節点があれば、次のように木の再構成を行う。木の形によって、木の再構成として、1重回転と2重回転のどちらかが選択される。†データ追加の結果、AVL木が次のようになった場合には、左右の木のバランスを保つために、1重回転が行われる。次図のα,β,γは部分木とする。†データ追加の結果、AVL木が次のようになった場合には、まずβを2つに分割してから、再構成を行うための2重回転が行われる。†AVL木からデータを削除する場合、挿入のときと同じように該当データを探し削除する(削除の考え方は2分探索木と同じ)。この結果、木の高さの差が2以上になった場合、再構成が行われる。データ構造(4580d)。