OR事典

AVL木

読み方：えいぶいえるぎ
【英】：AVL (Adelson-Velskii and Landis) tree

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

「OR事典」の他の用語

組合せ最適化：

0-1整数計画  2次割当問題  AVL木  NP困難  TDI性  アルゴリズム  オンラインアルゴリズム