Kurs:Algorithmen und Datenstrukturen/Vorlesung/Binäre Suchbäume Suchen




Ein binärer Suchbaum kann für viele Anwendungen eingesetzt werden.

Hier ist der Baum ein Datenindex und eine Alternative zu Listen und Arrays. Beispielsweise kann dieser Baum als Suchbaum verwendet werden und nach "5" gesucht werden.

 

Bei der Anwendung von Bäumen zur effizienten Suche gibt es pro Knoten einen Schlüssel und ein Datenelement und die Ordnung der Knoten erfolgt anhand der Schlüssel. Bei einem binärer Suchbaum enthält der Knoten k einen Schlüsselwert k.key. Alle Schlüsselwerte im linken Teilbaum k.left sind kleiner als k.key und alle Schlüsselwerte im rechten Teilbaum k.right sind größer als k.key. Die Auswertung eines Suchbaums sieht wie folgt aus:

  1. Vergleich des Suchschlüssels mit Schlüssel der Wurzel
  2. Wenn kleiner, dann in linken Teilbaum weiter suchen
  3. Wenn größer, dann in rechtem Teilbaum weiter suchen
  4. Sonst gefunden/nicht gefunden
static class  TreeNode<K extends Comparable<K>>{
         
       K key;
       TreeNode<K> left = null;
       TreeNode<K> right = null;
        
       public TreeNode(K e) {key = e; }
       public TreeNode<K> getLeft() {return left; }
       public TreeNode<K> getRight()  {return right; }
       public K getKey() {return key; }
        
       public void setLeft(TreeNode<K> n) {left = n;}
       public void setRight(TreeNode<K> n) {right = n;}

         ...
        
 }

Knotenvergleich

Bearbeiten
class  TreeNode<...> { 
          ...

     public int compareKeyTo(K k) {
           return (key == null ? -1: 
                        key.compareTo(k));
     }
         ...
    
    
 }

Rekursives Suchen

Bearbeiten
protected  TreeNode<K>
         recursiveFindNode(TreeNode<K>  n, k){ 
          /* k wird gesucht */

          if (n!= nullNode) {
              int cmp = n.compareKeyTo(k.key);
              if (cmp == 0)
                  return n;
              else if (cmp > 0)
                  return 
                     recursiveFindNode(n.getLeft(),k);
              else 
                  return 
                     recursiveFindNode(n.getRight(),k);
          }
          else
                return null;
 }

Iteratives Suchen

Bearbeiten
protected  TreeNode<K> iterativeFindNode(TreeNode<K> k){ 
          /* k wird gesucht */
          TreeNode<K> n = head.getRight();
          while (n!= nullNode) {
              int cmp = n.compareKeyTo(k.key);
              if (cmp == 0)
                  return n;
              else 
                  n = (cmp > 0 ? 
                      n.getLeft(): n.getRight());
           }
           return null;
 }

Suchen des kleinsten Elements

Bearbeiten
protected  K findMinElement(){ 
          TreeNode<K> n = head.getRight();
          while (n.getLeft() != nullNode) 
              n = n.getLeft();
          return n.getKey();
}

Suchen des größten Elements

Bearbeiten
protected  K findMaxElement(){ 
          TreeNode<K> n = head.getRight();
          while (n.getRight() != nullNode) 
              n = n.getRight();
          return n.getKey();
}

Eine weitere Anwendungsmöglichkeit ist der Baum aus Termen. Wir haben den Term   als Baumdarstellung sieht es so aus:

 

Bei der Auswertung müssen die Operatoren auf die beiden Werte der Teilbäume angewandt werden.

Literatur

Bearbeiten

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14.3 zu finden.