insérer des éléments N dans un arbre de recherche binaire vide

Question

Pourquoi est le pire des cas grand-O pour insérer des éléments N dans un arbre de recherche binaire vide n ^ 2? il n'y a aucun contrôle de l'équilibre.

Answer 1

Chaque élément est O (n), et il y a n éléments. Même si le O (n) par article est une "augmentation comme il va" n, vous obtenez toujours 0 + 1 + 2 + 3 ... (n-1) qui est n (n-1) / 2 = O ( n ^ 2).

En d'autres termes, supposons que nous ajoutons 10, 20, 30, 40:

Etape 1: arbre vide, insérer 10:

10

Etape 2: comparer 20 avec 10; plus, donc arbre devient:

10
  \
   20

Étape 3: comparer 30 avec 10; plus, donc déplacer vers le bas au noeud avec 20.         comparer 30 avec 20; plus, donc arbre devient:

10
  \
   20
     \
      30

Étape 4: comparer 40 avec 10; plus, donc déplacer vers le bas au noeud avec 20.         comparer 40 avec 20; plus, se déplacer vers le bas si au noeud avec 30.         comparer 40 avec 30; plus, donc arbre devient:

10
  \
   20
     \
      30
        \
         40

Remarquez comment nous obtenons une comparaison plus à chaque fois - de sorte que le premier élément prend 0 comparaisons, la seconde prend 1, le troisième prend 2 etc -. Sommation de n (n-1)

Bien sûr, cela est le cas que si vous insérez dans l'ordre de tri (soit petit au plus grand ou grand à petit). Insertion dans un ordre qui arrive à équilibrer l'arbre sera beaucoup moins cher.

Answer 2

Dans le pire des cas, le BST est une liste, et l'insertion des N éléments à la fin d'un vide est est O (n ^ 2).