自己バランス二分探索木

コンピュータサイエンスにおいて、自己バランス型二分探索木(BST) とは、任意の項目の挿入や削除に対して高さ (ルートの下の最大レベル数) を自動的に小さく保つノードベースの二分探索木です。 ^[1] 自己バランス型二分探索木用に設計されたこれらの操作には、木の高さが際限なく増加することに対する予防措置が含まれているため、これらの抽象データ構造は「自己バランス型」という属性を受け取ります。

高さバランスのとれた二分木の場合、高さはアイテムの数の対数になるように定義されます。これは、 AVL ツリーや赤黒ツリーなど、多くの二分探索ツリーに当てはまります。スプレイ ツリーとツリー パスは自己バランスがとれていますが、高さバランスがとれていません。これは、高さがアイテムの数の対数になることが保証されていないためです。 ${\displaystyle O(\log n)}$${\displaystyle n}$

自己バランス型二分探索木は、可変順序リストの効率的な実装を提供し、連想配列、優先キュー、セットなどの他の抽象データ構造にも使用できます。

二分探索木 (BST) のほとんどの操作は、木の高さに比例して時間がかかるため、高さを小さく保つことが望ましい。高さhの二分木には、最大で2 ⁰ +2 ¹ +···+2 ^h  = 2 ^{h +1} −1 個のノードを含めることができる。したがって、 n 個のノードと高さh を持つ任意の木について、次のことが言える。

${\displaystyle n\leq 2^{h+1}-1}$

そしてそれは次のことを意味します:

${\displaystyle h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor }$。

言い換えれば、n個のノードを持つ二分木の最小の高さはlog2 ( n )_を 切り捨てた値、つまり、となる。^[1]${\displaystyle \lfloor \log _{2}n\rfloor }$

ただし、BST 項目挿入の最も単純なアルゴリズムでは、一般的な状況では高さnのツリーが生成される場合があります。たとえば、項目がキーの順序でソートされて挿入されると、ツリーはn 個のノードを持つリンク リストに退化します。2 つの状況のパフォーマンスの違いは非常に大きくなる可能性があります。たとえば、n  = 1,000,000 の場合、最小の高さは です。 ${\displaystyle \lfloor \log _{2}(1,000,000)\rfloor =19}$

データ項目が事前にわかっている場合は、ランダムな順序で値を追加してランダムなバイナリ検索ツリーを作成することで、平均的な意味で高さを小さく保つことができます。ただし、このランダム化が実行できない 状況も数多くあります (オンライン アルゴリズムなど) 。

自己バランス型二分木は、キー挿入時にツリーの変換（ツリーの回転など）を実行して高さをlog ₂ ( n )に比例させることでこの問題を解決します。一定のオーバーヘッドは発生しますが、常に必要な検索コストよりも大きくはなく、すべての操作を高速に実行することで正当化される場合があります。

予想される時間の操作（検索/挿入/削除）で最小の高さの BST を維持することは可能ですが、そのような構造を維持するために必要な追加のスペース要件は、検索時間の短縮を上回る傾向があります。比較すると、 AVL ツリーは、単純な実装で 2 ビットの追加ストレージのみを必要としながら、最適な高さの 1.44 倍以内であることが保証されています。^[1]したがって、ほとんどの自己バランス BST アルゴリズムは、高さをこの下限の定数倍内に維持します。 ${\displaystyle O(\log n)}$

漸近的(" Big-O ") な意味では、 n個の項目を含む自己バランス BST 構造により、最悪の場合の時間で項目の検索、挿入、削除が可能になり、時間内にすべての項目を順序付けて列挙できます。実装によっては、これらは操作ごとの時間制限ですが、他の実装では、一連の操作にわたる償却制限です。これらの時間は、比較のみでキーを操作するすべてのデータ構造の中で漸近的に最適です。 ${\displaystyle O(\log n)}$${\displaystyle O(n)}$

このタイプのツリーを実装するデータ構造には次のものがあります。

• 2～3本の木
• AAツリー
• AVLツリー
• Bツリー
• 赤黒木
• スケープゴートの木
• タンゴの木
• トレップ
• 重量バランスの取れた木

自己バランス型二分探索木は、優先キューなどの順序付きリストを自然に構築および維持するために使用できます。また、連想配列にも使用できます。キーと値のペアは、キーのみに基づいた順序で単純に挿入されます。この能力において、自己バランス型 BST には、主な競合相手であるハッシュ テーブルに比べて多くの利点と欠点があります。自己バランス型 BST の利点の 1 つは、ハッシュ テーブルでは提供されない、キー順序 での項目の高速 (実際、漸近的に最適) 列挙が可能になることです。欠点の 1 つは、同じキーを持つ項目が複数ある可能性がある場合に、検索アルゴリズムが複雑になることです。自己バランス型 BST は、最悪の場合の検索パフォーマンスがほとんどの^[2]ハッシュ テーブルよりも優れています (と比較) が、平均的な場合のパフォーマンスは劣ります (と比較)。 ${\displaystyle O(\log n)}$${\displaystyle O(n)}$${\displaystyle O(\log n)}$${\displaystyle O(1)}$

自己バランス BST は、可変の順序付きリストを必要とするアルゴリズムを実装して、最悪の場合の最適な漸近的パフォーマンスを実現するために使用できます。たとえば、バイナリ ツリー ソートを自己バランス BST で実装すると、記述が非常に簡単でありながら漸近的に最適な ソート アルゴリズムが得られます。同様に、計算幾何学の多くのアルゴリズムは、自己バランス BST のバリエーションを利用して、線分の交差問題や点の位置問題などの問題を効率的に解決します。(ただし、平均的なパフォーマンスの場合、自己バランス BST は他のソリューションよりも効率が悪い可能性があります。特にバイナリ ツリー ソートは、ツリー バランスのオーバーヘッドとキャッシュアクセス パターンのため、マージ ソート、クイック ソート、またはヒープソートよりも遅くなる可能性があります。) ${\displaystyle O(n\log n)}$

自己バランス型 BST は、拡張が容易で、追加情報を効率的に記録したり、新しい操作を実行したりできる柔軟なデータ構造です。たとえば、特定のプロパティを持つ各サブツリーのノードの数を記録して、そのプロパティを持つ特定のキー範囲内のノードの数を時間内にカウントすることができます。これらの拡張機能は、たとえば、データベース クエリやその他のリスト処理アルゴリズムを最適化するために使用できます。 ${\displaystyle O(\log n)}$

• 検索データ構造
• デイ・スタウト・ウォーレンアルゴリズム
• フュージョンツリー
• リストをスキップ
• ソート

• アルゴリズムとデータ構造の辞書: 高さバランス二分探索木
• GNU libavl、C言語でバイナリツリーを実装したLGPLライセンスのライブラリ、ドキュメント付き