Suchalgorithmen für Datenbäume
Ein Beispiel für einen binären Datenbaum haben Sie bereits in der Einleitung gesehen. An dieser Stelle soll nur auf diese Sorte Baum eingegangen werden.
Binäre Bäume besitzen immer einen linken und einen rechten Ast. Als eine spezielle Ausprägung eines Graphen sind die Knoten Datenelemente in der Datenstruktur.
Es gibt verschiedene Operationen, die man auf einen Baum anwenden kann. Natürlich funkionieren Breitensuche und Tiefensuche auch hier. Zusätzlich spricht man von einer Traversierung, wenn alle Knoten genau einmal besucht werden sollen (um z.B. Operationen auf diese auszuführen).
Man könnte den Baum auch wie eine Liste durchlaufen. Man müsste einen Ast bis zu seinem Ende verfolgen und schliesslich wieder zurück zu seiner Verzweigung gehen. Geht man dabei zuerst nach links und beim zweiten Auftreffen auf den Knoten erst nach rechts, so spricht man von Linkstraversierung.
Ein passender Algorithmus zu dieser Vorgehensweise, wäre folgender:
- Ist das aktuelle Element das Ziel? Dann breche die Suche ab und gebe das aktuelle Element zurück.
- Ist links ein Element vorhanden und ist das Element noch nicht besucht worden -> gehe nach links.
- Ist rechts ein Element vorhanden, ist das Element noch nicht besucht worden und ist 2. falsch-> gehe nach rechts.
- Ist 1. - 3. falsch, gehe einen Schritt zurück.
- Wiederhole 1. - 4., bis alle Elemente besucht wurden.
Der Vorschlag entspricht einer iterativen Lösung, die nicht die schnellste sein muss.
- Was würde sich für einen rekursiven Algorithmus ändern?
- Überlegen Sie, was sich am Algorithmus ändern würde, wäre der Baum sortiert.