Robert Sedgewick: Algorithmen

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


17. Digitales Suchen



Übungen

  1. Skizzieren Sie den digitalen Suchbaum, der sich ergibt, 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 eingefügt werden.
  2. Erzeugen Sie einen 1000 Knoten besitzenden digitalen Suchbaum und vergleichen Sie seine Höhe sowie die Anzahl der Knoten auf jeder Ebene mit einem gewöhnlichen binären Suchbaum und einem Rot-Schwarz-Baum (Kapitel 15), wenn diese aus den gleichen Schlüsseln erzeugt wurden.
  3. Finden Sie eine Menge von 12 Schlüsseln, die einen besonders schlecht ausgeglichenen digitalen Such-Trie ergeben.
  4. Skizzieren Sie den digitalen Such-Trie, der sich ergibt, 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 eingefügt werden.
  5. Ein Problem bei digitalen Such-Tries für Mehrwege-Suche mit 26 Wegen besteht darin, daß manche Buchstaben des Alphabets sehr selten benutzt werden. Schlagen Sie einen Ausweg vor.
  6. Beschreiben Sie, wie Sie ein Element aus einem digitalen Mehrwege-Suchbaum löschen würden.
  7. Skizzieren Sie den Patricia-Baum, der sich ergibt, 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 eingefügt werden.
  8. Finden Sie eine Menge von 12 Schlüsseln, die einen besonders schlecht ausgeglichenen Patricia-Baum ergeben.
  9. Schreiben Sie ein Programm, das alle Schlüssel in einem Patricia-Baum ausgibt, die mit den gleichen t Bits beginnen wie ein gegebener Suchschlüssel.
  10. Für welche der digitalen Methoden ist es sinnvoll, ein Programm zu schreiben, das die Schlüssel in sortierter Reihenfolge ausgibt? Für welche der Methoden läßt sich diese Operation nicht ausführen?


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