空のバイナリ検索ツリーにN個のアイテムを挿入する

Question

空のバイナリ検索ツリーn^2にN個のアイテムを挿入するのはなぜ最悪の場合ですか？バランスチェックはありません。

Answer 1

各項目はO（n）であり、n個の項目があります。 1つのアイテムにつきO（n）が「増加するにつれて増加する」nであっても、n（n-1）/ 2 = O（n-1） n^2）。言い換えれば

、我々は10、20、30、40を追加しているとします

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

10 

手順2：10と20を比較します。ステップ3：30と10を比較する。ステップ3：30を10と比較する。ステップ3：30を10と比較する。大きいので、20でノードに移動してください。 30と20を比較してください。したがって、木は次のようになります。

10 
    \ 
    20 
    \ 
     30 

ステップ4：40と10を比較します。大きいので、20でノードに移動します。 40と20を比較します。大きいので、30のノードに移動してください。 40と30を比較してください。大きく、従ってツリーは次のようになる。

10 
    \ 
    20 
    \ 
     30 
     \ 
     40 

注意我々はもう一つの比較毎に取得する方法 - 第1要素が第2等がかかり、第1取り、0の比較を要する - nに加算（N-1） 。

もちろん、ソート順（小から大、または小から小まで）で挿入する場合にのみ当てはまります。ツリーのバランスをとるような順序で挿入すると、大幅に安くなります。

Answer 2

最悪の場合、BSTはリストであり、N個の項目を空の末尾に挿入するとO（n^2）になります。