平衡二分探索木
(平衡2分探索木 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/22 06:35 UTC 版)
ナビゲーションに移動 検索に移動平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。
概要
二分探索木上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の二分探索木の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として連結リスト同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつもできるわけではない。特に入力が一括して与えられることのないオンラインアルゴリズム(online algorithm)の場合はそうである。
平衡二分探索木は木に対する変換(例えば木の回転)を木の高さを減らすために必要に応じて行うことでこの問題を解決する。いくらかのオーバーヘッドは要するものの、それは後述の操作のオーバーヘッドを長い目で見て劇的に減らすことで正当化される。
木の高さは常に最低でも
カテゴリ
平衡2分探索木と同じ種類の言葉
| 探索木に関連する言葉 | 探索木 2分探索木(にぶんたんさくき) 平衡2分探索木 |
- 平衡2分探索木のページへのリンク
