Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


26. Bereichssuche



Übungen

  1. Erstellen Sie eine nichtrekursive Variante des in diesem Kapitel angegebenen Programms für die eindimensionale Bereichssuche.
  2. Erstellen Sie ein Programm für die Ausgabe aller Punkte aus einem binären Baum, die nicht in einem vorgegebenen Intervall liegen.
  3. Geben Sie die maximale und minimale Anzahl von Gitterquadraten, die bei dem Gitterverfahren durchsucht werden, als Funktion der Maße der Gitterquadrate und des den Suchbereich darstellenden Rechtecks an.
  4. Erörtern Sie die Idee, die darin besteht, das Durchsuchen von leeren Gitterquadraten durch die Benutzung verketteter Listen zu vermeiden: Jedes Gitterquadrat könnte mit dem nächsten nichtleeren Gitterquadrat in der gleichen Zeile und dem nächsten nichtleeren Gitterquadrat in der gleichen Spalte verbunden werden. Wie würde die Anwendung einer solchen Vorgehensweise die zu verwendende Größe der Gitterquadrate beeinflussen?
  5. Skizzieren Sie den Baum und die sich ergebende Zerlegung der Ebene, wenn wir für unser Beispiel einer Punktmenge einen 2D-Baum erzeugen und dabei mit einer vertikalen Trennungslinie beginnen. (Das heißt, rufen Sie range mit einem dritten Parameter false anstelle von true auf.)
  6. Geben Sie eine Punktmenge an, die zu dem ungünstigsten 2D-Baum führt, der keine Knoten mit zwei Nachfolgern hat; geben Sie die sich ergebende Zerlegung der Ebene an.
  7. Beschreiben Sie, wie die Verfahren modifiziert werden müßten, damit alle Punkte zurückgegeben werden, die innerhalb eines gegebenen Kreises liegen.
  8. Wenn alle Suchrechtecke mit der gleichen Fläche betrachtet werden, welche Form dürfte dann für jedes der Verfahren die geringste Leistungsfähigkeit zur Folge haben?
  9. Welches Verfahren sollte für die Bereichssuche bevorzugt werden, wenn die Punkte in großen, weit voneinander entfernten Haufen angeordnet sind?
  10. Skizzieren Sie den 3D-Baum, der sich ergibt, wenn die Punkte (3,1,5), (4,8,3), (8,3,9), (6,2,7), (1,6,3), (1,3,5), (6,4,2) in einen ursprünglich leeren Baum eingefügt werden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]