「AVL木」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】''' 平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の...') |
|||
| 1行目: | 1行目: | ||
'''【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】''' | '''【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】''' | ||
| − | 平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の高さが, もう片方の子供のものと高々1しか違わないという条件を満たす. AVL は提案者である2人のロシア人アデルソンヴェルスキとランディスの頭文字. 木に対して変更が行われたとき, 回転 (rotation) と呼ばれる操作を連続して行い, 条件を満たすように木を変形する. これにより, 要素の挿入・削除・ある要素が含まれるかの確認を O | + | 平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の高さが, もう片方の子供のものと高々1しか違わないという条件を満たす. AVL は提案者である2人のロシア人アデルソンヴェルスキとランディスの頭文字. 木に対して変更が行われたとき, 回転 (rotation) と呼ばれる操作を連続して行い, 条件を満たすように木を変形する. これにより, 要素の挿入・削除・ある要素が含まれるかの確認を <math>O(\log n) \,</math> の時間で行うことができる. |
2007年7月11日 (水) 15:47時点における版
【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】
平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の高さが, もう片方の子供のものと高々1しか違わないという条件を満たす. AVL は提案者である2人のロシア人アデルソンヴェルスキとランディスの頭文字. 木に対して変更が行われたとき, 回転 (rotation) と呼ばれる操作を連続して行い, 条件を満たすように木を変形する. これにより, 要素の挿入・削除・ある要素が含まれるかの確認を の時間で行うことができる.
