Vorlesung Informatik 2 - Teil B: Theorie

4.6 Suchbaum

Eine wichtige Anwendung von Binärbäumen ist der Suchbaum. Er Implementiert einen assoziativen Speicher (Map), mit der Einschränkung, dass die Schlüssel sortierbar (comparable) sein müssen.

Für die Konstruktion eines  binären Suchbaums gilt folgende rekursive Regel:

  • Die Schlüssel der Knoten im linken Teilbaum sind kleiner  als der Schlüssel der Wurzel,
  • Die Schlüssel der Knoten im rechten Teilbaumsind größer als der Schlüssel der Wurzel.

Wenn wir einen Suchbaum konstruieren, tragen wir rekursiv jeden neuen Schlüssel in den richtigen Teilbaum ein.

Beispiel (der Baum enthält nur Schlüssel):

Suchbaum aus den Buchstaben des Wortes INDIANER:

                              I
                             / \
                           D    N
                          / \    \
                         A   E    R
 

Probieren Sie es selbst für verschiedene Zeichenfolgen aus, einen Suchbaum zu konstruieren.

Implementierung:

class Suchbaum<K extends Comparable, V> extends Baum implements meineMap<K,V>{
    protected K key;

    public SuchBaum(K key, V inhalt){
           super(inthalt);
           this.key = key;
    }
    public void put(K key, V inhalt){
         if(inhalt==null || key==null) throw new IllegalArgumentException("Key und Inhalt dürfen nicht null sein!");
         int vergleich = key.compareTo(this.key);
         if(vergleich==0) this.inhalt=inhalt; // Inhalt wird ersetzt
         else if(vergleich<0) {     // im linken Teilbaum einfügen
              if(this.links==null) this.setLinks(new SuchBaum(key, inhalt));
              else ( (SuchBaum<K,V>)this.links).put(key, inhalt);   // REKURSION
         } else{   // rechter Teilbaum analog
              ...

Aufgrund der rekursiven Struktur ist auch die Methode rekursiv.

Die Methode get(K key) :V  arbeitet ebenfalls rekursiv - das programmieren wir in den Übungen.

Wenn man einen Suchbaum in der In-Order ausgibt, entsteht die natürliche Reihenfolge der Objekte. 

Suchbäüme haben einen gravierenden Nachteil: sie können zu Listen degradieren, z.B. der Suchbaum zu den Buchstaben ABCDEFG.

Ein balancierter Suchbaum hätte aber den Vorteil, dass er beim Einfügen und Suchen O(log N) hätte, denn wir bewegen uns ja immer entlang eines absoluten Pfades. 

 

Lehrvideo