Suchbaum

Der Suchbaum stellt einen guten Kompromiss aus den Datenstrukturen Feld und Liste dar: Er ist dynamisch, erlaubt also jederzeit nachträgliches Einfügen oder Löschen ohne zusätzlichen Speicherbedarf. Er erlaubt zugleich eine schnelle Suche, da die Idee der binären Suche übertragbar ist, wodurch sich logarithmischer Suchaufwand ergibt.

Eine Klasse zum Suchen vorbereiten

Voraussetzung für den Aufbau eines Suchbaums ist eine Ordnung der zu verwaltenden Elemente. Für die Klasse BinarySearchTree wird die erforderliche Ordnung so realisiert, dass für die Basisklasse der zu speichernden Objekte gefordert wird, dass sie das Interface ComparableContent implementiert. In diesem Interface wird mit den drei Methoden isLess(), isGreater() und isEqual() die Vergleichbarkeit der Elemente verankert.

public interface ComparableContent<ContentType> {

  public boolean isGreater(ContentType pContent);

  public boolean isEqual(ContentType pContent);

  public boolean isLess(ContentType pContent);

}

Die folgende Beispielklasse Entry speichert für jedes Objekt exemplarisch ein ganzzahliges Attribut, das über eine get-Methode abgefragt werden kann. In den drei Vergleichsmethoden muss ein Objekt die Frage beantworten, wie es sich selbst gegenüber einem zweiten Objekt (hier pContent) der gleichen Klasse einordnet.


public class Entry implements ComparableContent<Entry> {

    private int wert;

    public Entry(int pWert) {
        this.wert = pWert;
    }

    public boolean isLess(Entry pContent) {
        return wert < pContent.getWert();
    }

    public boolean isEqual(Entry pContent) { 
        return wert == pContent.getWert();
    }

    public boolean isGreater(Entry pContent) {
        return wert > pContent.getWert();
    }

    public int getWert() {
        return wert;
    } 
}

Einen Suchbaum aufbauen

Steht die Basisklasse, so steht dem Aufbau des Suchbaums nichts mehr im Wege. Im nachfolgenden Beispiel würden nacheinander die Elemente 45, 25 usw. in den Suchbaum eingefügt. Für das geordnete Einfügen sorgt die Methode insert.

Somit ergibt sich der folgende Beispielsuchbaum:

Entry int1 = new Entry(45); 
Entry int2 = new Entry(25); 
Entry int3 = new Entry(65); 
Entry int4 = new Entry(15); 
Entry int5 = new Entry(35); 

tree = new BinarySearchTree<Entry>();

tree.insert(int1);
tree.insert(int2);
tree.insert(int3);
tree.insert(int4);
tree.insert(int5);

In einem Suchbaum suchen

Um nun ein Element im Suchbaum zu suchen, ist zunächst ein Such-Objekt der Basisklasse (in unserem Beispiel Entry) anzulegen. Kann die Methode search() ein passendes Objekt im Baum finden, so wird dieses Objekt zurückgegeben. Bleibt die Suche erfolglos, so gibt sie null zurück. Eine Fallunterscheidung kann die beiden Fälle trennen.

Entry suchitem = new Entry(77);

Entry ergitem = tree.search(suchitem); 

if (ergitem!=null) {
    System.out.println("Ja"); 
}
else { 
    System.out.println("Nein");
}

Einen Suchbaum durchlaufen

Analog zum Binärbaum kann auch der Suchbaum rekursiv durchsucht werden. Diese Möglichkeit ist aber vorrangig für Debugging-Zwecke (z.B. zum Ausdrucken des Suchbaum-Inhalts) interessant.

private void durchlaufeBaum(BinarySearchTree<Entry> mytree) {

    if (!mytree.isEmpty()) {

        durchlaufeBaum(mytree.getLeftTree());
        System.out.println(mytree.getContent());
        durchlaufeBaum(mytree.getRightTree());

    }
}

results matching ""

    No results matching ""