inserir N itens em uma árvore de busca binária vazia

Question

Por que é o pior caso big-O para inserir N itens em uma árvore de busca binária vazio n ^ 2? não há equilíbrio cheques.

Answer 1

Cada item é O (n), e existem n itens. Mesmo que a O (n) por item é um "aumentando à medida que ele vai" n, você ainda obter 0 + 1 + 2 + 3 ... (n-1), que é n (n-1) / 2 = O ( n ^ 2).

Em outras palavras, suponha que estamos adicionando 10, 20, 30, 40:

Passo 1: vazia árvore, a inserção 10:

10

Passo 2: comparação com 20 de 10; maior, portanto, árvore torna-se:

10
  \
   20

Passo 3: comparar 30 com 10; maior, então mover para baixo para nó com 20. comparar 30 com 20; maior, portanto, árvore torna-se:

10
  \
   20
     \
      30

Passo 4: comparar 40 com 10; maior, então mover para baixo para nó com 20. comparar 40 com 20; maior, então mover para baixo para nó com 30. comparar 40 com 30; maior, portanto, árvore torna-se:

10
  \
   20
     \
      30
        \
         40

Observe como temos mais uma comparação de cada vez - para o primeiro elemento leva 0 comparações, a segunda leva 1, o terceiro leva 2 etc -. Soma de n (n-1)

Claro, este é apenas o caso se inserir na ordem de classificação (ou pequeno a grande ou grande a pequeno). Inserindo em uma ordem que acontece de equilibrar a árvore vai ser significativamente mais barato.

Answer 2

No pior dos casos, a sua BST é uma lista, e a inserção de itens n ao final de um vazio é é O (n ^ 2).