вставьте N элементов в пустое двоичное дерево поиска

Question

Почему в наихудшем случае big-O для вставки N элементов в пустое двоичное дерево поиска n ^ 2?нет никаких проверок баланса.

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

Обратите внимание, как мы получаем каждый раз еще одно сравнение - таким образом, первый элемент принимает 0 сравнений, второй принимает 1, третий принимает 2 и т.д. - суммируя до n (n-1).

Конечно, это только в том случае, если вы вставляете в порядке сортировки (либо от маленького к большому, либо от большого к маленькому).Вставка в порядке, который позволяет сбалансировать дерево, обойдется значительно дешевле.

Answer 2

В худшем случае ваш BST - это список, и вставка N элементов в конец пустого is равна O (n ^ 2).