einfügen N Artikel in einen leeren binären Suchbaum

Question

Warum ist das schlimmste Fall Big-O für Elemente in einen leeren binären Suchbaum N Einfügen von n ^ 2? gibt es keine Balance überprüft.

Answer 1

Jeder Artikel ist O (n), und es n Elemente. Auch wenn die O (n) pro Punkt eine "Erhöhung, wie es geht" n ist, erhalten Sie noch 0 + 1 + 2 + 3 ... (n-1), die n (n-1) / 2 = O ( n ^ 2).

Mit anderen Worten: Angenommen, wir fügen 10, 20, 30, 40:

Schritt 1: leerer Baum, legen 10:

10

Schritt 2: Vergleich 20 mit 10; größer, daher Baum:

10
  \
   20

Schritt 3: Vergleich von 30 mit 10; größer, bewegt, um mit 20 bis Knoten nach unten.         vergleiche 30 mit 20; größer, daher Baum:

10
  \
   20
     \
      30

Schritt 4: Vergleich 40 mit 10; größer, bewegt, um mit 20 bis Knoten nach unten.         vergleiche 40 mit 20; größer, bewegt, um mit 30 bis Knoten nach unten.         vergleiche 40 mit 30; größer, daher Baum:

10
  \
   20
     \
      30
        \
         40

Beachten Sie, wie wir noch einen Vergleich jedes Mal bekommen - so das erste Element nimmt 0 Vergleiche, die zweite 1 nimmt, nimmt die dritte 2 usw. -. Summieren bis n (n-1)

Natürlich ist dies nur dann der Fall, wenn Sie in Sortierreihenfolge (entweder klein bis groß oder groß bis klein) einlegen. Einfügen in einer Reihenfolge, die den Baum balancieren geschieht wird deutlich billiger.

Answer 2

Im schlimmsten Fall Ihre BST ist eine Liste, und die Einfügung von N Elementen an das Ende einer leeren ist O (n ^ 2).