AVL木

【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】

平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の高さが, もう片方の子供のものと高々1しか違わないという条件を満たす. AVL は提案者である2人のロシア人アデルソンヴェルスキとランディスの頭文字. 木に対して変更が行われたとき, 回転 (rotation) と呼ばれる操作を連続して行い, 条件を満たすように木を変形する. これにより, 要素の挿入・削除・ある要素が含まれるかの確認を $O(\log n)\,$ の時間で行うことができる.