AVL treeとは? わかりやすく解説

Weblio 辞書 > コンピュータ > IT用語辞典 > AVL treeの意味・解説 

AVL木

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

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

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

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


AVL木

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

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


AVL木

(AVL tree から転送)

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

ナビゲーションに移動 検索に移動
AVL木の例

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

平衡二分探索木の1つで、木に対する操作によって条件を満たさないノードが発生しても、回転と呼ばれる操作を行うだけで木をAVL木に再構成でき、平衡を維持できる。

AVL木は最初に考案された平衡二分探索木であり、その名は1962年に論文を発表したソ連の2人の数学者、ゲオルギー・アデルソン・ヴェルスキー英語版エフゲニー・ランディス英語版に由来する。

平衡条件と計算量

通常の二分探索木は入力されるデータの順番によって木の構成が変わるため、探索効率が安定しない。例えば、データがソートされた状態で順に入力されると、木は線形リストと等価な構造になるため、探索の計算量は最悪の

複回転の様子。円はノードを、三角形は部分木を表す。ノード横の青い数字はそのノードの平衡係数を表す。

通常の二分探索木における挿入は、条件「左の子の値 ≤ 親の値 ≤ 右の子の値」を満たす枝の末端を探索し、そこに新たに作成したノードを繋ぐだけであるが、AVL木ではさらに平衡条件を満たしているか調べ、満たしていない場合は回転を行う。

まず、挿入すべき枝の末端を探索しながら、探索してきた経路を記憶しておく。これはスタック再帰呼出しを用いることで実現できる。挿入後、この経路上を「挿入したノードの親ノード」から「根ノード」に向かって順に調べていく。

平衡条件を満たさないノード(Pとする)があった場合に回転を行うが、ほとんどの場合、「P」と「Pの高い方の部分木の根ノード」に着目して1度回転を行えば、これらのノードとその子孫ノードは平衡条件を満たした状態になる。この回転を単回転または1重回転などと呼ぶ。

ただし、単回転では平衡条件が満たされない場合があることに注意しなければならない。具体的には、

  • Pの左部分木の方が高く、かつPの左の子ノードの右部分木の方が高い場合(図のLeft Right Case)
  • Pの右部分木の方が高く、かつPの右の子ノードの左部分木の方が高い場合(図のRight Left Case)

の2通りである。

この場合はそれぞれ以下のように2度回転を行うことで解決できる。これを複回転または2重回転などと呼ぶ。

  • 回転前のPの左の子ノードをL、Lの右の子ノードをLRとすると、まずLとLRで回転し、次にPと新たにPの左の子ノードとなったLRで回転する
  • 回転前のPの右の子ノードをR、Rの左の子ノードをRLとすると、まずRとRLで回転し、次にPと新たにPの右の子ノードとなったRLで回転する

このように、AVL木では部分木の構造によって単回転と複回転を使い分ける必要がある。

挿入後の平衡確認の終了条件

AVL木の挿入における平衡条件の確認は、探索してきた経路上の全てのノードが平衡条件を満たしていることを確認する必要は必ずしもなく、探索してきた経路上のどこかのノードを回転するか、探索してきた経路上に平衡係数が0のノードを見つけた時点で処理を終了できる。

なぜなら、挿入は木の高さを1大きくする操作であるのに対して、回転は木の高さを1小さくする操作であるから、これらの操作によってその部分木の高さが挿入前と等しくなるためである。また、挿入により平衡係数が0になったノードがあるということは、挿入前に高さが1小さかった方の部分木に挿入したということであるから、そのノードを根とする部分木の高さは挿入前後で変わっていないので、全てのノードが平衡条件を満たしていることがわかる。

ただし、探索してきた経路上に平衡係数が1もしくは-1のノードを見つけても処理を終了できない。

なぜなら、挿入により平衡係数が1もしくは-1になったノードがあるということは、挿入前のそのノードの左右部分木の高さは等しかったが、挿入により一方の部分木の高さが1大きくなったということであり、そのノードを根とする部分木の高さは1大きくなっているので、全てのノードが平衡条件を満たしていることを保証できないからである。

削除

AVL木の削除は、通常の二分探索木と同様の削除操作を行ったあと、平衡条件を満たしているか調べ、満たしていない場合は回転を行う。

挿入と同様に、まずは探索してきた経路上を「削除したノードの親ノード」から「根ノード」に向かって順に調べていく。平衡条件を満たさないノードがあった場合、そのノードと高い方の部分木の根ノードに着目して単回転、または複回転を行う。

なお、削除するノードが子ノードを2つ持つ場合、削除するノードの左部分木のうち最大値を持つノード(もしくは右部分木のうち最小値を持つノード)を探索して、削除するノードと置き換える処理が発生するが、ここで探索した経路も記憶しておく必要があることに注意する。ノードを削除するのは置き換え後なので、平衡条件の確認も置き換えられた先の親ノードから始めなければならない。

削除後の平衡確認の終了条件

AVL木の削除における平衡条件の確認は、探索してきた経路上の全てのノードが平衡条件を満たしていることを確認する必要は必ずしもなく、探索してきた経路上に平衡係数が1もしくは-1のノードを見つけた時点で処理を終了できる。

なぜなら、削除により平衡係数が1もしくは-1になったノードがあるということは、削除前のそのノードの左右部分木の高さは等しかったが、削除により一方の部分木の高さが1小さくなったということであり、そのノードを根とする部分木の高さは削除前後で変わっていないので、全てのノードが平衡条件を満たしていることがわかるからである。

ただし、探索してきた経路上のどこかのノードを回転したり、平衡係数が0のノードを見つけても処理を終了できない。

なぜなら、削除は木の高さを1小さくする操作であるのに対して、回転も木の高さを1小さくする操作であるから、これらの操作によって平衡条件を満たさなくなったノードが出てくる可能性があるためである。また、削除により平衡係数が0になったノードがあるということは、削除前に高さが1大きかった方の部分木から削除したということであるから、そのノードを根とする部分木の高さは1小さくなるので、同様の可能性がある。

特徴

赤黒木ではあるが、AVL木ではない木の例。AVL木の平衡条件の方が厳密である。

子ノードがない場合は部分木の高さを0と考えるため、1つの子ノードしか持たないノードについて、その子ノードは葉ノードとなる。すなわち、兄弟ノードを持たないノードは必ず葉ノードである。

AVL木のどの部分木もAVL木である。

AVL木は、あくまで各ノードの左右部分木の高さのバランスを保った木であり、各葉ノードの深さが均等な木というわけではない。深さが最も大きい葉ノードと最も小さい葉ノードの深さの差が2以上になって、完全二分木とはかけ離れた構造になることもある。

挿入や削除の操作は、毎回平衡条件の判定を伴うため比較的コストが掛かる。そのため、これらの操作が探索に比べてあまりにも頻繁に行われるような環境では、AVL木は性能を発揮しにくい。

AVL木は、同じく平衡二分探索木の1つである赤黒木に比べて平衡性をより厳密に維持するので、探索性能はAVL木の方がよいが、挿入や削除の性能は赤黒木の方がよい。

関連項目


「AVL tree」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「AVL tree」の関連用語

1
56% |||||



4
14% |||||





9
12% |||||

10
12% |||||

AVL treeのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



AVL treeのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
IT用語辞典バイナリIT用語辞典バイナリ
Copyright © 2005-2025 Weblio 辞書 IT用語辞典バイナリさくいん。 この記事は、IT用語辞典バイナリの【AVL木】の記事を利用しております。
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのAVL木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS