平衡二分探索木

平衡二分探索木とは

平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）は、計算機科学における重要なデータ構造の一つです。これは、二分探索木をベースとしており、その中でも特に、木の高さ（根から最も遠い葉までの階層数）をできるだけ小さく保つように設計されたものを指します。木の高さが低いほど、データへのアクセスや操作が高速になるため、効率的なデータ管理に不可欠です。

概要

二分探索木は、データの検索、挿入、削除などの操作を効率的に行うためのデータ構造ですが、キーが特定の順序で挿入されると、木が偏ってしまい、最悪の場合、連結リストのように機能してしまうことがあります。これにより、操作のコストが大幅に増加してしまいます。

平衡二分探索木は、このような問題を解決するために、木の回転などの操作を必要に応じて行い、木の高さを調整します。この調整にはいくらかのオーバーヘッドが伴いますが、それによって操作全体の効率を長期的に向上させることができます。

木は、ノード数がnの場合、最低でもlog nの高さが必要になります。これは、k段目には最大で2^k個のノードしか存在できないためです。完全な二分木は、まさにこの最小の高さを持つことになります。しかし、平衡二分探索木は常に最小の高さに保つ必要はなく、高さを最小値の定数倍以内に維持することを目標とします。

計算量

平衡二分探索木における主な操作の計算量は以下の通りです。

探索 (Search): O(log n)
挿入 (Insert): O(log n)
削除 (Delete): O(log n)

これらの計算量は、実装によっては最悪時のもの、または償却解析によるものとなります。

実装

平衡二分探索木を実装したデータ構造には、以下のようなものがあります。

AVL木 (AVL tree)
赤黒木 (Red-black tree)
B木 (B-tree)
2-3木 (2-3 tree)
2-3-4木 (2-3-4 tree)

また、平衡探索木ではありませんが、スキップリストも同様の用途に利用できます。Treapやスキップリストは、乱択アルゴリズムに基づいています。

応用

平衡二分探索木は、連想配列を実装するための基本的な方法として広く利用されています。キーと値のペアをキーに基づいて順序付けして格納することで、効率的な検索を可能にします。また、ハッシュテーブルと比較して、データの順序を保持できるという利点があります。

さらに、多くのアルゴリズムにおいて、最悪ケースでのパフォーマンスを向上させるために使用されます。例えば、二分探索を平衡二分探索木上で行うことで、O(n log n)のソートアルゴリズムを簡単に実装できます。

計算幾何学の分野でも、線分の交差判定や点位置決定などの問題を効率的に解決するために、平衡二分探索木が活用されています。

平衡二分探索木は、柔軟なデータ構造であるため、追加情報を記録したり、新しい操作を効率的に行うように拡張することが容易です。例えば、各部分木に含まれる特定の特性を持つノードの数を記録することで、特定の範囲のキーを持つノードの数をO(log n)時間で数えることができます。このような拡張は、データベースのクエリ最適化や、他のリスト処理アルゴリズムに応用することができます。

関連項目

スキップリスト
B木
* 木構造 (データ構造)

もう一度検索