二分探索木（バランスとアンバランス）を学んでいる間、解決する必要がある質問を思いつきました：
n 個の要素を使用して二分探索木を構築する場合 (バランスをとる必要はありません)、ツリー構築の合計時間の複雑さはどれくらいですか?
AVL ツリーが n 個の要素から構築されている場合、その AVL ツリーを構築するための時間の複雑さはどれくらいですか?
nlog(n) を超える必要がありますか? AVL ツリーの構築には多くのローテーションが必要だからです。
AVL ツリーでの挿入および削除操作は log(n) オーダーになることを知っています (ランダムな要素で構築された二分探索木の高さが log(n) の場合も同様です)。
しかし、ソート目的でバランスのとれた検索ツリーを使用する必要があるため、全体的なツリー構築コストとその変動について知る必要があります。
AVL ツリーの構築から始めましょう。ツリーを作成するには、n要素を挿入する必要があります。バランスの取れたツリーに要素を挿入するには、 が必要log(n)です。したがって、あなたはで終わりますO(n*log(n))。
通常のBSTに戻ります。直感に反しますが、このツリーをどのように構築するかによって異なります。BST のすべての要素を事前に把握していない場合 (オンライン アルゴリズムn)、各要素を次々に挿入する必要があります。非常に運が悪いと、挿入の複雑さが にO(n)なり、 に悪化しO(n^2)ます。
このような状況はほとんどありませんが、可能性があることに注意してください。
ただしO(nlog(n))、事前にすべての要素を知っていれば、達成できます。それらO(nlog(n))を並べ替えてから、次の順序で要素を挿入できます。中央の要素を取り、 root として挿入し、残っている両方の部分に対して再帰的に同じことを行います。nを使用して要素を挿入し、バランスの取れた BST を作成することになりますlog(n)。