Binäre Suche im Baum

[Vorheriges Kapitel] [Vorherige Seite] [Inhaltsverzeichnis] [Nächste Seite] [Nächstes Kapitel]

SortedBinaryTrees.om
PROCEDURE Find(tree: Tree; key: Objects.Object;
               VAR parent, node: Node) : BOOLEAN;
BEGIN
   node := tree.root; parent := NIL;
   WHILE node # NIL DO
      IF tree.compare(key, node.object) = 0 THEN
         RETURN TRUE
      END;
      parent := node;
      IF tree.compare(key, node.object) < 0 THEN
         node := node.left;
      ELSE
         node := node.right;
      END;
   END;
   RETURN FALSE
END Find;

*Ein Abstieg entsprechend einem Schlüssel ist an mehreren Stellen notwendig (Insert, Delete und Lookup), so daß es sich lohnt, dies innerhalb von SortedBinaryTrees nur einmal zu formulieren.
 
*Der jeweilige Elternteil wird mit zurückgegeben, um ggf. das Einfügen zu erleichtern.
 

[Vorheriges Kapitel] [Vorherige Seite] [Inhaltsverzeichnis] [Nächste Seite] [Nächstes Kapitel]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999