Site hosted by Angelfire.com: Build your free website today!

Suche in einem Binärbaum

Dieser einfache, aber sehr geeignete Algorithmus setzt voraus, dass die Daten in einem Binärbaum angeordnet sind, in dem die Datensätze mit kleineren Schlüsseln im linken Unterbaum und die Datensätze mit größeren Schlüsseln im rechten Unterbaum eines Knotens angeordnet sind. Daraus ergibt sich, leicht erkennbar, folgende kompakte Methode:
Vergleiche den gesuchten Schlüssel mit dem der Wurzel. Stimmen beide überein, so ist der Datensatz gefunden. Ist er kleiner, gehe zum linken Unterbaum. Ist er größer, gehe zum rechten Unterbaum.
Wende dieses Verfahren rekursiv auf die Unterbäume an, bis der Datensatz gefunden ist, oder man bei einem leeren Knoten angekommen ist.
Im durchschnittlichen Fall sind 2 ln N Vergleiche nötig.
Die verwendete Datenstruktur kann unter Datenstrukturen für Suchalgorithmen eingesehen werden (head ist Pseudoknoten, head->r ist die eigentliche Wurzel des Baumes).

dataType cm_SuchenInBinaerbaum(itemType wert) {
     node *x = head->r;
     z->key = wert;
     while(wert != x->key)
         x = (wert < x->key) ? x->l : x->r;
     return x->daten;
}

   Computer    Programmieren (incl. C++ Kurs)    Algorithmen    Bücher

Zeitschriften    Heavy Metal    Mountainbiking    Meine Katze

Über mich und die Site    Links    Downloads    Gästebuch    HP mit Umfrage