時間複雑度の問題

Question

ノードをバイナリツリーに挿入する時間の複雑さは、平衡型と不平衡型の両方のBSTで同じですか？

Answer 1

平衡ツリーの場合、insertはルートからリーフまでのノード数であるO（log（n））を取ります。

ツリーは、それが挿入がノー（N）Oを意味し、

Answer 2

をnステップの最悪のケースをとることができ、挿入順序は、以下の場合は、時間の複雑さは、異なることができることを意味し、一つの長い鎖であることができ、アンバランスである場合いくつかの特定のパターン。示されているレベルの努力では完全には答えませんが、次の点を考慮してください。

BSTに1000個の要素を最小から最大まで挿入します。最後のものを挿入するときに何回の比較が必要ですか？

Answer 3

どうすれば同じことができますか？

同義語です。

ノードを挿入する場合（1）あなたは3つのノード（5-3-2）を横断しますここでは、この

5 
    /\ 
3 7 
/\ /\ 
2 4 6 8 

のようなBST

たとえば。ここではシナリオがあるかもしれない最悪の場合:-(アンバランスな場合のために今

）

 8 
    /
    7 
    /
    ... 
/
2 

あなたは7つのノードを通過する必要が1挿入します。

これを避けるために、バランスのとれた検索ツリーが導入されました。あなたはBSTの欠点に目を向けることができ、次にAVLツリーまたはRBツリーを調べることができます。あなたはそれがどのように違うかを知るでしょう。

高さの平衡BSTの場合、検索の複雑さはO(logn)になります。しかし、最悪の場合、不平衡のBSTに対しては、O(n)がかかるかもしれません。