二分探索木対。AVL木：建設の複雑さ

1. 序章

このチュートリアルでは、二分探索ツリーとAVLツリーの時間計算量の違いについて説明します。具体的には、配列からツリーを構築するための予想されるシナリオと最悪のシナリオに焦点を当てます。

スペースの複雑さに関しては、分析されたケースに関係なく、両方のツリーでスペースを構築する必要があります。

二分探索木（BST）では、各ノードの値は、左側の子孫の値および右側のサブツリーの値よりも大きくなります。

BSTの目標は、効率的な検索を可能にすることです。ほとんどの場合ですが、BSTの形状は、ノードを挿入する順序に依存することに注意してください。 最悪の場合、プレーンBSTはリンクリストに縮退し、検索が複雑になります。

バランスツリーは、この問題を克服するために設計されました。バランスの取れたツリーを構築しながら、高速検索に適した形状を維持します。特に、 AVLツリーの場合、各ノードの左右のサブツリーの高さは最大で1だけ異なります。

このプロパティは、AVLツリーの高さがであることを意味します。それを確実にするために、挿入によってツリーのバランスが崩れた場合、ツリーのバランスを取り直す必要があります。これにより、計算のオーバーヘッドが発生します。

ここでは、比較可能なオブジェクトの配列からAVLツリーとBSTを構築する複雑さを分析します。

まず、最悪のシナリオを分析しましょう。 BSTツリーとAVLツリーの両方で、構築アルゴリズムは同じパターンに従います。

アルゴリズムは空のツリーから始まり、配列全体を処理するまでの要素を連続して挿入します。を配置するために、アルゴリズムは最初にを含むツリーでそれを探します。検索手順では、子になる必要のあるノードを特定します。次に、アルゴリズムは、かどうかに応じての左または右の子として挿入します。

最悪のシナリオでは、挿入順序がツリーを歪める場合、 BSTへの挿入は線形時間操作です。

ツリーは本質的にリストであるため、最悪の場合にツリーに追加するには、以前にアタッチされたすべての要素をトラバースする必要があります。 合計で、ポインターに従います：

(1)

したがって、 BSTの構築には、最悪の場合2次の時間がかかります。

AVLツリーへの挿入には、対数線形時間がかかります。その理由は、AVLツリーの高さがノード数の対数であるため、最悪の場合に挿入するときにトラバースするのはエッジのみであるためです。合計で：

(2)

AVLツリーを構築する際の最悪の場合の複雑さはです。したがって、挿入によってリバランスがトリガーされる可能性がありますが、AVLツリーの構築は通常のBSTよりも高速です。

以下の分析では、のすべての挿入順序が同じように発生する可能性があると想定しています。

単一の挿入の複雑さは、BSTの平均ノード深度に依存します。ノードの深度の合計をノード数で割ったものとして計算できます（）。

ルートの左側のサブツリーにノードがある場合、右側のサブツリーには頂点が含まれます。次に、そのようなBSTの深さの予想される合計は次のとおりです。

(3)

ルートノードが他のすべてのノードの深さを1増やすため、追加します。

のすべての順列は同じ確率であるため、。の一様分布に従います。したがって、ノードを持つBSTのノードの予想される深さは次のとおりです。

(4)

再発を解くと、が得られます。したがって、ノードを持つBSTで予想されるノードの深さはです。したがって、空のツリーから開始して、を挿入し、次の手順を実行します。

(5)

したがって、平均的なケースでは、BSTの構築には対数線形時間がかかります。

AVLツリーはバランスが取れており、挿入順序に依存しないため、ツリーの深さは常にです。さらに、AVLツリーには最大で深さのノードがあります。したがって、平均ノード深度は次のように制限されます。

(6)

以来：

AVLツリーで予想されるノードの深さは次のとおりです。

(7)

平均ノード深度はBSTの場合と同じであるため、式（ 5 ）はAVLツリーにも当てはまります。したがって、 AVLツリーの構築は、予想される場合の対数線形操作でもあります。

この記事では、二分探索木（BST）とAVL木の構築の複雑さを比較しました。最悪のシナリオでは、AVLツリーの構築には時間がかかりますが、BSTの構築には複雑さが伴います。

ただし、予想される場合、両方のツリーに対数線形時間がかかります。