Loading article…
コンピュータサイエンスにおいて、自己平衡二分探索木（BST）とは、任意の項目の挿入や削除に対して、その高さ（ルートより下のレベルの最大数）を自動的に小さく保つノードベースの二分探索木のことである。 [ 1 ] これらの操作は、自己平衡二分探索木用に設計されている場合、木の高さが際限なく増加しないようにするための予防措置が含まれているため、これらの抽象的なデータ構造は「自己平衡」という属性を受ける。
高さがバランスのとれた二分木の場合、高さは対数として定義されます。数においてアイテムの数。これは、 AVL ツリーや赤黒木など、多くの二分探索木に当てはまります。スプレー木とトレアプは自己平衡ですが、高さ平衡ではありません。高さがアイテムの数に対して対数的になることが保証されていないためです。
自己平衡二分探索木は、可変順序付きリストの効率的な実装を提供し、連想配列、優先度付きキュー、セットなどの他の抽象データ構造にも使用できます。
二分探索木 (BST) に対するほとんどの操作は、木の高さに比例する時間を要するため、高さを小さく保つことが望ましい。高さhの二分木には、最大で2 0 +2 1 +···+2 h = 2 h +1 −1個のノードが含まれる。したがって、 n 個のノードと高さhを持つ任意の木について、次のことが成り立つ。
そしてそれは次のことを意味する。
言い換えれば、n個のノードを持つ二分木の最小高さはlog 2 ( n )を切り捨てた値です。つまり、[ 1 ]
しかし、BST項目挿入の最も単純なアルゴリズムでは、ごく一般的な状況で高さnの木が生成される可能性があります。たとえば、項目がキーのソート順で挿入される場合、木はn個のノードを持つリンクリストに退化します。この2つの状況のパフォーマンスの差は非常に大きい可能性があります。たとえば、n = 1,000,000の場合、最小の高さは 。
データ項目が事前に分かっている場合、値をランダムな順序で追加することで、平均的な意味で高さを小さく保つことができ、結果としてランダム二分探索木が得られます。しかし、オンラインアルゴリズムなど、このようなランダム化が実行不可能な状況も数多く存在します。
自己平衡二分木は、キー挿入時に木構造に対する変換（木の回転など）を実行することで、高さをlog 2 ( n )に比例させ、この問題を解決します。ある程度のオーバーヘッドは発生しますが、常に必要な検索コストよりも大きくはなく、すべての操作を高速に実行できることで正当化されます。
期待される最小高さの BST を維持することは可能ですが時間操作（検索/挿入/削除）の場合、このような構造を維持するために必要な追加のスペース要件は、検索時間の短縮を上回る傾向があります。比較のために、AVL ツリーは、単純な実装で必要な追加のストレージが 2 ビットだけで、最適な高さの 1.44 倍以内に収まることが保証されています。[ 1 ]したがって、ほとんどの自己平衡 BST アルゴリズムは、高さをこの下限の定数倍以内に維持します。
漸近的（「ビッグオー」）な意味では、 n個の項目を含む自己平衡 BST 構造は、項目の検索、挿入、削除を可能にする。最悪の場合の時間、およびすべての項目の順序付き列挙時間。実装によっては、これは操作ごとの時間制限であり、他の実装では、一連の操作に対する償却時間制限です。これらの時間は、比較のみによってキーを操作するすべてのデータ構造の中で、漸近的に最適です。
このタイプのツリーを実装するデータ構造には、以下のようなものがあります。
自己平衡二分探索木は、優先度キューなどの順序付きリストを構築および維持するために自然な方法で使用できます。また、連想配列にも使用できます。キーと値のペアは、キーのみに基づく順序で挿入されます。この機能において、自己平衡二分探索木は、主な競合相手であるハッシュテーブルと比較して、多くの利点と欠点があります。自己平衡二分探索木の利点の 1 つは、ハッシュテーブルでは提供されない、キーの順序での項目の高速 (実際には漸近的に最適) 列挙を可能にすることです。欠点の 1 つは、同じキーを持つ項目が複数存在する可能性がある場合、検索アルゴリズムがより複雑になることです。自己平衡二分探索木は、ほとんどの[ 2 ]ハッシュテーブル (に比べ）だが、平均的なパフォーマンスは劣る（に比べ)
自己平衡二分探索木は、可変順序付きリストを必要とするあらゆるアルゴリズムを実装するために使用でき、最悪ケースの漸近的パフォーマンスを最適化することができます。例えば、二分木ソートを自己平衡二分探索木で実装すると、非常に簡単に記述でき、かつ漸近的に最適なアルゴリズムが得られます。ソートアルゴリズム。同様に、計算幾何学における多くのアルゴリズムは、線分交差問題や点位置特定問題などの問題を効率的に解決するために、自己平衡二分探索木（BST）の変種を利用しています。（ただし、平均的なパフォーマンスにおいては、自己平衡BSTは他の解法よりも効率が低い場合があります。特に二分木ソートは、木のバランス調整のオーバーヘッドやキャッシュアクセスパターンのため、マージソート、クイックソート、ヒープソートよりも遅くなる可能性があります。）
自己平衡二分探索木は柔軟なデータ構造であり、追加情報を効率的に記録したり、新しい操作を実行したりするために容易に拡張できます。たとえば、各サブツリー内の特定のプロパティを持つノードの数を記録することで、特定のキー範囲内のそのプロパティを持つノードの数をカウントできます。時間。これらの拡張機能は、例えば、データベースクエリやその他のリスト処理アルゴリズムを最適化するために使用できます。
