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

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

class  TreeNode<...> { 
          ...

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

Rekursives Suchen

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

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

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

Suchen des größten Elements

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 $(3+4)\cdot 5+2\cdot 3$ als Baumdarstellung sieht es so aus:

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

Literatur

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.