Nicht-rekursives Einfügen

Die insert-Methode

Im letzten Abschnitt haben wir gesehen, wie leicht man eine rekursive Einfüge-Methode in einen binären Suchbaum schreiben kann. Nur wenige Zeilen Quelltext sind dafür notwendig. Das Problem bei solchen rekursiven Methoden ist allerdings, dass viele Schüler (und Lehrer) Probleme mit dem Verständnis des Ablaufs haben, vor allem mit den verschachtelten Rekursionsebenen, das ist wirklich nicht jedermanns Sache. Für solche Leute habe ich diese Seite angelege. Hier wird erklärt, wie man eine Einfüge-Methode schreibt, die nicht rekursiv ist.

Fall 1 - Der Baum ist leer

In diesem Fall ist das Einfügen eines neuen (ersten) Elements ganz einfach:

   if (root == null)
      root = new Element(v);

Wenn der Baum leer ist und der root-Zeiger auf null verweist, wird einfach der Konstruktor für ein neues Element aufgerufen und die Adresse des neuen Elements in root gespeichert.

Fall 2 - Der Baum enthält genau ein Element

   if (v < root.value)
      root.left = new Element(v);
   else
      root.right = new Element(v);

Wenn die Wurzel bereits vorhanden ist, wird der neu einzufügende Wert mit der Wurzel verglichen. Ist der neue Wert kleiner als die Wurzel, so wird das neue Element als linker Teilbaum an die Wurzel angehängt, andernfalls als rechter Teilbaum.

Fall 3 - Der Baum enthält viele Elemente

In der Praxis enthält ein binärer Suchbaum bereits viele Elemente. Wir erhalten eine funktionierende insert()-Methode, indem wir die beiden eben besprochenen Fälle geschickt kombinieren und in eine while-Schleife einbetten. Aber zunächst der Quelltext;

   public void insert(int v)
   {
      if (root == null)
        root = new Element(v);
      else
      {  
         Element help = root;                  // (1)
         while (help != null)
         {
            if (v < help.value)                // (2)
               if (help.left != null)          // (3)
                  help = help.left;            // (5) (6)
               else
               { 
                  help.left = new Element(v);  // (4)
                  return; 
               }  
            else                               // (7)
               if (help.right != null)
                 help = help.right;
               else
               { 
                  help.right = new Element(v); 
                  return; 
              }  
         }
      }   
   }

Die Nummern in den Klammern beziehen sich auf das Flussdiagramm zur Darstellung des nicht-rekursiven Einfüge-Algorithmus:

Wenn der Baum leer ist (root == null), wird ein neues Element angelegt und dann wird der Zeiger root auf dieses neue Element gesetzt (Fall 1). Enthält der Baum bereits Elemente, so wird ein Hilfszeiger auf die Wurzel gesetzt:

 Element help = root; // (1)

Dann wird dieser Hilfszeiger so "umgebegen", bis er auf denjenigen Knoten zeigt, an den das neue Element als linker oder rechter Teilbaum angehängt werden soll. Dies geschieht mit Hilfe einer while-Schleife. Solange der Hilfszeiger nicht den Wert null hat (solange er also auf einen Knoten zeigt), wird überprüft, ob das neue Element kleiner ist als das Element, auf das der Hilfszeiger zeigt (2).

Angenommen, der Hilfszeiger verweist gerade auf das Element 50 in dem obigen Baum, und es soll die Zahl 30 eingefügt werden. Nun gilt die Bedingung v < help.value, denn 30 < 50. Also wird nachgeschaut, ob ein linker Nachfolger der 50 existiert:

if (help.left != null)... // (3)

Dies ist der Fall, die 20 ist der linke Nachfolger der 50. Also wird die Anweisung

help = help.left // (5) (6)

ausgeführt. Der Hilfszeiger zeigt jetzt auf die 20. Dann wird die while-Schleife erneut durchlaufen (6). Da die 30 nicht kleiner ist als das Element 20, wird der else-Zweig dieser if-else-Anweisung ausgeführt (7). Hier wird zunächst einmal überprüft, ob ein rechter Nachfolger der 20 existiert. Dies ist nicht der Fall, es gibt keinen rechten Nachfolger. Also wird jetzt der Befehl

 help.right = new Element(v) 

ausgeführt (Fall 2). Es wird Speicherplatz für ein neues Element erzeugt und der Zeiger help.right wird mit diesem Speicherplatz verknüpft. Damit wird das neue Element 30 korrekt in den Baum eingefügt.

Die return-Anweisung am Ende des if- bzw. else-Zweiges ist unbedingt notwendig, weil sonst der Hilfszeiger auf das soeben einfügte neue Element gesetzt würde. Dann würde die while-Schleife ein weiteres Mal durchlaufen und das Element ein zweites Mal in den Baum eingefügt, dann ein drittes Mal, ein viertes Mal und so weiter.