AVL木

IT用語辞典バイナリ

AVL木

読み方：エーブイエルき
【英】AVL tree

AVL木とは、2分木の中でも、どの節点においても、左右の部分木の高さの差が1以下の平衡（バランスが取れた）木のことである。

2分木に何の工夫もなしに単純にデータを追加していくと、最悪の場合には、一本道の木構造になってしまい、木とする意味がなくなる。そこで、左右の木の偏りを修正する手法として、データの追加・削除で高さの差が2以上となりバランスが崩れると、木の再構成を行うことでAVL木を構築するという手法が考案された。

なお、AVLの名称は、上記手法を考案した2人の数学者であるAdelson-VelskiiとLandisにちなんで命名された。

情報処理のほかの用語一覧

アルゴリズム：

AVL木  アルゴリズム  アセンディングソート  後入れ先出し  エイトクイーン問題  枝  親

>>アルゴリズムカテゴリの他の用語

OR事典

AVL木

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

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

「OR事典」の他の用語

組合せ最適化：

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

ウィキペディア

AVL木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/24 03:23 UTC 版)

AVL木（えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree）とは、コンピュータサイエンスにおいて、「どのノードの左右部分木の高さの差も1以下」という条件を満たす二分探索木のことである。