Kurs:Algorithmen und Datenstrukturen/Vorlesung/Binäre Suchbäume Suchen
Suchen[Bearbeiten]
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:
- Vergleich des Suchschlüssels mit Schlüssel der Wurzel
- Wenn kleiner, dann in linken Teilbaum weiter suchen
- Wenn größer, dann in rechtem Teilbaum weiter suchen
- 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.
