平衡二分探索木

ウィキペディア

平衡二分探索木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/22 06:35 UTC 版)

平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。

概要

二分探索木上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の二分探索木の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として連結リスト同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつもできるわけではない。特に入力が一括して与えられることのないオンラインアルゴリズム(online algorithm)の場合はそうである。

平衡二分探索木は木に対する変換(例えば木の回転)を木の高さを減らすために必要に応じて行うことでこの問題を解決する。いくらかのオーバーヘッドは要するものの、それは後述の操作のオーバーヘッドを長い目で見て劇的に減らすことで正当化される。

木の高さは常に最低でも$\lfloor \log n\rfloor$カテゴリ

ウィキペディア小見出し辞書

平衡二分探索木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/29 13:54 UTC 版)

「二分木」の記事における「平衡二分探索木」の解説

二分探索木の検索効率が最高になるのは、木の高さが最低な時で、即ち根から各葉までの高さができるだけ等しくなった場合である。そのような二分探索木を平衡二分探索木と呼ぶ。詳細は平衡二分探索木を参照されたい。