「AVL木」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】''' 平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (2人の利用者による、間の2版が非表示) | |||
| 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> の時間で行うことができる. |
| + | |||
| + | [[Category:組合せ最適化|えいぶいえるぎ]] | ||
2008年11月5日 (水) 16:27時点における最新版
【えいぶいえるぎ (AVL (Adelson-Velskii and Landis) tree)】
平衡二分探索木の一種. 任意の頂点に対し, 片方の子供を根とする部分木の高さが, もう片方の子供のものと高々1しか違わないという条件を満たす. AVL は提案者である2人のロシア人アデルソンヴェルスキとランディスの頭文字. 木に対して変更が行われたとき, 回転 (rotation) と呼ばれる操作を連続して行い, 条件を満たすように木を変形する. これにより, 要素の挿入・削除・ある要素が含まれるかの確認を の時間で行うことができる.
