空のバイナリ検索ツリーにN項目を挿入

Question

なぜ空の二分探索木のn ^ 2にN項目を挿入するための最悪の場合、BIG-Oとは？何のバランスチェックはありません。

Answer 1

各項目は、O（N）であり、nアイテムがあります。項目ごとにO（n）は、 "それが行くように増加する" であるにもかかわらずnは、あなたはまだ（（N-1）/ 2 = Oを0 + 1 + 2 + 3 ...（N-1）はnを取得しますN ^ 2）。

言い換えれば、我々は10、20、30、40を追加していると仮定します：

ステップ1：空の木、10を挿入します：

10

ステップ2：10と20を比較します。大きな、したがって、ツリーはなります：

10
  \
   20

ステップ3：10と30を比較します。大きなので、20とノードに下に移動します。         20と30を比較します。大きな、したがって、ツリーはなります：

10
  \
   20
     \
      30

ステップ4：10と40を比較します。大きなので、20とノードに下に移動します。         20と40を比較します。大きなので、30とノードに下に移動します。         30と40を比較します。大きな、したがって、ツリーはなります：

10
  \
   20
     \
      30
        \
         40

我々はもう一つの比較毎に取得する方法に注目してください - 第1要素が第2等をとり、第1取り、0の比較を要する - nに加算（N-1）

あなたは（規模の大小に大小規模のいずれか）ソート順に挿入した場合、

もちろん、これは唯一のケースです。木が大幅に安くなるバランスをとるために起こるために挿入します。

Answer 2

最悪の場合、あなたのBSTはリストであり、空の最後にN個のアイテムの挿入はO（N ^ 2）である。