翻訳と辞書 Words near each other ・ AVALON (ラジオ番組) ・ AVAグランプリ ・ AVAマルチメディアグランプリ ・ AVCアジアクラブ選手権 ・ AVE (曖昧さ回避) ・ AVE MARIA (本田美奈子のアルバム) ・ AVEC (大江千里のアルバム) ・ AVENGE WORLD/世界は疵を抱きしめる ・ AVIコンテナ ・ AVIファイル ・ AVL木 ・ AVNアワード ・ AVN最優秀新人賞 ・ AVN殿堂 ・ AVP2 エイリアンズ VS. プレデター ・ AVP2 エイリアンズVS.プレデター ・ AVP不適合分泌症候群 ・ AVない奴ら ・ AVな彼女 ・ AVアンプ Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク AVL木 ： ウィキペディア日本語版 AVL木[えーぶいえるき] AVL木（えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree）とは、コンピュータサイエンスにおいて、「どのノードの左右部分木の高さの差も1以下」という条件を満たす2分探索木のことである。 平衡2分探索木の1つで、木に対する操作によって条件を満たさないノードが発生しても、回転と呼ばれる操作を行うだけで木をAVL木に再構成でき、平衡を維持できる。 AVL木は最初に考案された平衡2分探索木であり、その名は1962年に論文を発表したソ連の2人の数学者、とに由来する。 == 平衡条件と計算量 == 通常の2分探索木は入力されるデータの順番によって木の構成が変わるため、探索効率が安定しない。例えば、データがソートされた状態で順に入力されると、木は線形リストと等価な構造になるため、探索の計算量は最悪の$O\backslash left(n\backslash right)$になってしまう。木が完全2分木であれば計算量は最良の$O\backslash left(\backslash log\; n\backslash right)$になるが、完全2分木でなくとも木全体の高さがより小さくバランスが取れている状態、すなわち平衡な状態であれば木の性能は十分発揮できる。AVL木は「どのノードの左右部分木の高さの差も1以下」であることを平衡の条件としており、これを常に満たすので、探索の計算量は常に$O\backslash left(\backslash log\; n\backslash right)$程度になる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「AVL木」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.