binary-tree - 空の二分探索木に N 個の項目を挿入する

Question

空の二分探索木 n^2 に N 個の項目を挿入する最悪のケースが big-O になるのはなぜですか? 残高チェックはありません。

Answer 1

各項目は O(n) であり、n 個の項目があります。アイテムごとの O(n) は「進むにつれて増加する」 n ですが、それでも 0 + 1 + 2 + 3 ... (n-1) が得られます。これは n(n-1)/2 = O( n^2)。

つまり、10、20、30、40 を追加するとします。

ステップ 1: ツリーを空にし、10 を挿入:

10

ステップ 2: 20 と 10 を比較します。大きいため、ツリーは次のようになります。

10
  \
   20

ステップ 3: 30 と 10 を比較します。大きいので、20 のノードに移動します。30 と 20 を比較します。大きいため、ツリーは次のようになります。

10
  \
   20
     \
      30

ステップ 4: 40 と 10 を比較します。大きいので、20 のノードに移動します。40 と 20 を比較します。大きいので、30 のノードに移動します。40 と 30 を比較します。大きいため、ツリーは次のようになります。

10
  \
   20
     \
      30
        \
         40

毎回もう 1 つの比較を取得する方法に注意してください。つまり、最初の要素は 0 回、2 番目は 1 回、3 番目は 2 回というように、合計すると n(n-1) になります。

もちろん、これは並べ替え順 (小さいものから大きいものへ、または大きいものから小さいもの) で挿入する場合にのみ当てはまります。たまたまツリーのバランスをとる順序で挿入すると、大幅に安くなります。

Answer 2

最悪の場合、BST はリストであり、空の is の末尾への N 個のアイテムの挿入は O(n^2) です。