データ構造の比較：主要な探索木（BST・AVL・B木・赤黒木・スプレー木）の違いと計算量

データ構造の中でも、データを効率的に検索するために設計された「探索木（サーチツリー）」には、さまざまな種類が存在します。それぞれ性質や特徴が異なり、用途に応じて使い分けられています。本記事では、代表的な探索木を取り上げ、その違いと操作ごとの時間計算量を比較して解説します。

主な探索木の種類

探索木の基本となるのは二分探索木（Binary Search Tree: BST）です。さらに、バランスを保つ仕組みを持つAVL木、赤黒木（Red-Black Tree）、スプレー木（Splay Tree）、ディスク向けに多分岐を採用したB木などが広く知られています。

• 二分探索木（BST）：各ノードが最大2つの子を持ち、左の子は親より小さく、右の子は親より大きいという規則でデータを配置します。シンプルですが、挿入順序によって木のバランスが崩れる可能性があります。
• AVL木：挿入や削除のたびに高さのバランスを自動的に調整する自己平衡型の二分探索木です。常に木の高さを O(log n) 程度に保ちます。
• B木：1つのノードに複数の要素を持たせる多分岐の平衡木です。ディスクアクセスを前提としたデータベースやファイルシステムで広く利用されています。
• 赤黒木（Red-Black Tree）：各ノードを「赤」か「黒」で色分けし、色の制約によって木全体のバランスを保証する自己平衡型の二分探索木です。C++の std::map など標準ライブラリでも採用されています。
• スプレー木（Splay Tree）：アクセスされたノードを根へ移動させる「スプレー操作」を行う自己適応型の木です。最近使われたデータへのアクセスが高速になる特性があります。

平均ケース（Average Case）における計算量

まず、平均的なケースにおける挿入・削除・検索の時間計算量を見てみましょう。

平均ケースでは、すべての探索木が対数オーダーの計算量を示します。これは、データがランダムな順序で挿入されれば、木がある程度バランスよく成長することが多いためです。

最悪ケース（Worst Case）における計算量

次に、最悪ケースでの計算量を比較します。ここが探索木選択の重要なポイントになります。

最悪ケースの差が意味すること

注目すべきは二分探索木（BST）です。ソート済みのデータを順番に挿入すると、BSTは片方向に伸びた「線形リスト」のような形になり、検索・挿入・削除すべてが O(n) まで悪化します。

一方、AVL木・赤黒木などの自己平衡型探索木は、挿入や削除の際に回転操作などでバランスを自動修正するため、最悪ケースでも O(log n) を保証します。B木も同様に平衡性を保つため、最悪ケースでも対数時間で動作します。

スプレー木については、個々の操作の最悪計算量は O(n) となり得ますが、償却解析（amortized analysis）では O(log n) の性能が保証される点が特徴です。

まとめ

探索木の選択では、「最悪ケースでも安定した性能が必要か」「メモリ上かディスク上か」といった要件を考慮することが重要です。

• 実装が簡単で学習用なら：二分探索木（BST）
• 常に厳密なバランスと高速な読み取りが必要なら：AVL木
• 挿入・削除が頻繁で全体的な安定性が求められるなら：赤黒木
• ディスクベースの大規模データ（DB・ファイルシステム）なら：B木
• 特定データへの再アクセスが多いワークロードなら：スプレー木

このように、各探索木には一長一短があり、計算量の比較表を理解したうえで、システムの特性に合ったデータ構造を選ぶことが性能向上の鍵となります。