rekursives Einfügen: Implementation

Eine Java-Implementation

Auf der Vorseite hatten wir allgemein den Algorithmus zum Einfügen in einen binären Suchbaum kennengelernt. Auf dieser Seite wollen wir nun eine komplette und lauffähige insert-Methode für den binären Suchbaum erarbeiten. Allerdings zeigt diese Seite nicht die "normale" Einfüge-Methode, wie sie in dem Flussdiagramm zu sehen ist, sondern eine auf den ersten Blick einfachere Methode, die deswegen so einfach erscheint, weil sie sich rekursiver Techniken bedient. Eine 1:1-Übesetzung des Flussdiagramms findet sich auf der nächsten Seite, wo es um das nicht-rekursive Einfügen geht.

Vorbereitung

Damit die hier gezeigten Methoden funktionieren, muss der Konstruktor der Klasse BinTree so aussehen:

    public BinTree(int v)
    {
        root = new Element(v);    
    }

Dem Konstruktor muss also als Parameter das erste Element des Baums übergeben werden. Es wird dann die Wurzel erzeugt und auch gleich mit dem entsprechendem Wert gefüllt. Selbstverständlich sind auch andere Implementationen möglich, aber das ist ja immer bei solchen Projekten der Fall. Wir einigen uns einfach auf die hier gezeigte Methode.

Die Mantelmethode

public void insert(int v)
{
   root = insertR(v,root);
}

Das war's schon? Nein, es handelt sich hier nur um die öffentliche Mantelmethode für die noch zu programmierende rekursive Methode insertR. Die Aufgabe von insert ist es, insertR mit bestimmten Parametern aufzurufen, aber so, dass der Benutzer nicht durch irgendwelche "unbequemen" Parameteraufrufe "belästigt" wird oder sogar Einblick in die Implementierung der Methode erhält (information hiding).

Stellen Sie sich doch einmal vor, der Benutzer möchte eine simple int-Zahl wie 12 in einen Baum einfügen und dann wird von ihm verlangt, dass er einen Zeiger der Klasse Element als zusätzlichen Parameter übergeben muss. Dann ist ein Aufruf wie

daten.insert(12);

doch wirklich einfacher und verständlicher als beispielsweise

daten.insert(12,daten.root);

Außerdem gäbe letztere Variante dem User einen Einblick in eine mögliche Implementation der Datenstruktur. Dies ist aber nicht im Sinne der wichtigen Prinzipien Datenkapselung bzw. information hiding.

Information hiding / Datenkapselung

Der Benutzer der Klasse BinTree kann nun ganz einfach die insert-Methode aufrufen und muss sich dabei nicht mit den internen Details der Klasse BinTree belasten.

Die rekursive (eigentliche) Einfüge-Methode

Hier nun der Quelltext der rekursiven Einfüge-Methode:

  private Element insertR(int v, Element tree)
   {
      if (tree==null)
          tree = new Element(v);
      else if (v < tree.value)
           tree.left = insertR(v,tree.left);
      else 
           tree.right = insertR(v,tree.right);
      return tree;
   }

Diese Methode sieht total einfach aus und ist auch leicht zu verstehen. Ein Flussdiagramm für diese Methode wäre auch wesentlich einfacher als das Flussdiagramm für die "normale" nicht-rekursive Methode, das auf der letzten Seite gezeigt wurde.

Erklärung der rekursiven Methode

Wenn der Baum leer ist - if (tree==null) - wird ein neues Element mit der Zahl v als Wurzel angelegt.

Ist der Baum nicht leer, wird zuerst geschaut, ob das neue Element kleiner ist als die Wurzel des Baums. Ist das der Fall, wird die Methode insertR rekursiv aufgerufen, und zwar für den linken Teilbaum. Dies wird durch den Parameter tree.left sichergestellt. Ist das neue Element dagegen nicht kleiner als die Wurzel, wird im else-Zweig insertR rekursiv für den rechten Teilbaum aufgerufen.

Diese Klasse speichert nur int-Zahlen. Meistens möchte man aber Objekte in einem Binärbaum speichern, dann müsste man den Datentyp int durch den Datentyp Object ersetzen, und eine show-Methode wäre dann nicht mehr möglich, da die Klasse Element ja keine Ahnung davon hätte, auf welche Weise die Elemente angezeigt werden sollen. Beschränkt man sich dagegen auf int-Zahlen (oder einen anderen gängigen Datentyp wie zum Beispiel String), dann kann man natürlich die Klasse Element mit einer einfachen show-Methode ausstatten.

Testen der Implementation

Das Einfügen ist ja unglaublich einfach, wenn man sich die rekursive Methode anschaut. Kaum zu glauben, dass das tatsächlich so funktioniert.

Damit Sie beim Testen der Einfüge-Methode nicht dauernd zehn oder mehr int-Zahlen eintippen müssen und beim nächsten Testen wieder, sollte man sich eine kleine Testklasse schreiben, die diese Arbeit übernimmt. Hier ein Beispiel für eine solche Testklasse:

import java.util.Random;

public class BinTreeTest
{
    BinTree derBaum;
    Random  zufall;
    
    public BinTreeTest()
    {
       zufall = new Random();
    }
    
    public void zufallsTest()
    {
       derBaum = new BinTree(zufall.nextInt(200));
       
       for (int i=1; i<25; i++)
          derBaum.insert(zufall.nextInt(300));
          
       derBaum.show();
    }    
    
    public void klausurTest()
    {
       derBaum = new BinTree(100);
       derBaum.insert( 50);
       derBaum.insert(150);
       derBaum.insert( 25);
       derBaum.insert( 75);
       derBaum.insert( 12);  
       derBaum.insert(120);       
       derBaum.insert(180);
       derBaum.show();
    }
}

In der Methode zufallsTest werden 25 Zufallszahlen in den Baum eingefügt und dann ausgegeben, und die Klasse klausurTest simuliert den Baum, der in der letzten Informatik-Klausur behandelt wurde, die ich meinen Schülern gestellt habe.

Auf die show-Methode komme ich im nächsten Abschnitt zu sprechen. Dort wird das rekursive Vorgehen auch eingehend besprochen.