Robert Sedgewick: Algorithmen

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


18. Externes Suchen



Übungen

  1. Geben Sie den Inhalt des B-Baumes an, der entsteht, wenn die Schlüssel E A S Y Q U E S T I O N in der angegebenen Reihenfolge in einen ursprünglich leeren Baum mit M = 5 eingefügt werden.
  2. Geben Sie den Inhalt des B-Baumes an, der entsteht, wenn die Schlüssel E A S Y Q U E S T I O N in der angegebenen Reihenfolge in einen ursprünglich leeren Baum mit M = 6 eingefügt werden. Benutzen Sie die Variante des Verfahrens, bei der alle Datensätze in externen Knoten aufbewahrt werden.
  3. Skizzieren Sie den B-Baum, der erzeugt wird, wenn sechzehn gleiche Schlüssel in einen ursprünglich leeren Baum mit M = 5 eingefügt werden.
  4. Angenommen, eine Seite aus der Datenbank wird vernichtet. Beschreiben Sie für jede der in diesem Kapitel betrachteten Strukturen von B-Bäumen, wie Sie in diesem Falle vorgehen würden.
  5. Geben Sie den Inhalt der Tabelle des erweiterbaren Hashing an, die sich ergibt, wenn die Schlüssel E A S Y Q U E S T I O N in der angegebenen Reihenfolge in eine ursprünglich leere Tabelle eingefügt werden, wobei die Seiten vier Datensätze aufnehmen können. (Orientieren Sie sich dabei an dem Beispiel in diesem Kapitel, führen Sie kein Hashing durch, sondern verwenden Sie die Binärdarstellung von i mit fünf Bits als Schlüssel für den i-ten Buchstaben.)
  6. Geben Sie eine Folge von möglichst wenigen unterschiedlichen Schlüsseln an, die bewirken, daß ein Inhaltsverzeichnis des erweiterbaren Hashing von einer ursprünglich leeren Tabelle bis zur Größe 16 anwächst, ausgehend von einer ursprünglich leeren Tabelle, wobei die Seiten drei Datensätze aufnehmen können.
  7. Skizzieren Sie ein Verfahren für das Löschen eines Elementes aus einer Tabelle des erweiterbaren Hashing.
  8. Warum sind Top-Down B-Bäume für den simultanen Datenzugriff besser als Bottom-Up B-Bäume? (Es werde zum Beispiel angenommen, daß zwei Programme gleichzeitig versuchen, einen neuen Knoten einzufügen.)
  9. Implementieren Sie Suchen und Einfügen für internes Suchen unter Verwendung der Methode des erweiterbaren Hashing.
  10. Vergleichen Sie das Programm aus der vorangegangenen Übung mit den doppeltes Hashing und digitale Tries benutzenden Suchverfahren für interne Suchanwendungen.


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