Suchverfahren (2)


Die angegebene Suchroutine ist rechtsrekursiv, und sie hat nur Wertparameter bis auf das Resultat wo,  das unverändert durchgereicht wird. Damit läßt sich eine effiziente iterative Variante herleiten, und mit einer kleinen Zusatzüberlegung ergibt sie sich auch direkt auf sehr übersichtliche Weise.

Während des Suchens sind wir in einem von drei Zuständen: entweder, wir haben das Gesuchte schon gefunden, oder wir wissen schon, daß es nicht da sein kann, oder wir wissen noch nichts darüber. Diesen Suchzustand rechnen wir mit:

PROCEDURE suche(k: keytype; d: Daten; VAR wo: Ort);
VAR Zustand: (suchen, ja, nein);
BEGIN Zustand := suchen;
      WHILE Zustand = suchen
      DO IF leer(d) THEN wo := NIRGENDS; Zustand := nein;
         ELSE wo := Einstieg(d);
              IF k = key(wo) THEN Zustand := ja
              ELSE d := Teilstruktur(d);
              END;
         END;
      END;
END suche;
Für unsere frühere Suchroutine für Suchbäume bekommen wir durch die nötigen Anpassungen jetzt die iterative Version:
PROCEDURE lookup(k: keytype; b: stree): stree;
VAR Zustand: (suchen, ja, nein);
BEGIN Zustand := suchen;
      WHILE Zustand = suchen
      DO IF b = NIL THEN Zustand := nein
         ELSIF k < b^.key THEN b := b^.left;
         ELSIF k > b^.key THEN b := b^.right;
         ELSE (* k = b^.key *) Zustand := ja;
         END;
      END;
      RETURN b;
END lookup;
Daß wir hier ein Funktionsresultat zurückliefern anstatt eines Ergebnisparameters, ist nicht wesentlich.
zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36