Robert Sedgewick: Algorithmen

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


15. Ausgeglichene Bäume



Übungen

  1. Skizzieren Sie den Top-Down 2-3-4-Baum, der erzeugt wird, 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. Zeichnen Sie eine Rot-Schwarz-Darstellung des Baumes aus der vorangegangenen Übung.
  3. Geben Sie genau an, welche Verkettungen durch split und rotate geändert werden, wenn Z (nach Y) in den Beispielbaum aus diesem Kapitel eingefügt wird.
  4. Zeichnen Sie den Rot-Schwarz-Baum, der sich ergibt, wenn die Buchstaben A bis K der Reihe nach eingefügt werden, und beschreiben Sie, was im allgemeinen Fall passiert, wenn Schlüssel in wachsender Reihenfolge in die Bäume eingefügt werden.
  5. Wie viele Verkettungen im Baum müssen für eine Doppelrotation tatsächlich geändert werden, und wie viele werden in der angegebenen Implementation geändert?
  6. Generieren Sie zwei zufällige Rot-Schwarz-Bäume mit 32 Knoten, zeichnen Sie sie (entweder von Hand oder mit einem Programm) und vergleichen Sie sie mit den nicht ausgeglichenen binären Suchbäumen, die mit den gleichen Schlüsseln aufgebaut wurden.
  7. Generieren Sie zehn zufällige Rot-Schwarz-Bäume mit 1000 Knoten. Berechnen Sie die Anzahl der Rotationen, die benötigt werden, um die Bäume aufzubauen, und die durchschnittliche Entfernung von der Wurzel bis zu einem äußeren Knoten. Kommentieren Sie die Ergebnisse.
  8. Mit einem Bit pro Knoten für die »Farbe« können wir 2-, 3- und 4-Knoten darstellen. Wie viele verschiedene Typen von Knoten könnten wir darstellen, wenn wir zwei Bits pro Knoten für die Farbe verwenden würden?
  9. Rotationen werden in Rot-Schwarz-Bäumen benötigt, wenn 3-Knoten in einer »nicht ausgeglichenen Weise« in 4-Knoten umgewandelt werden. Warum kann man nicht auf Rotationen verzichten, indem man zuläßt, daß 4-Knoten als drei beliebige Knoten dargestellt werden, die durch zwei rote Verkettungen verbunden sind (vollkommen ausgeglichen oder nicht)?
  10. Geben Sie eine Folge von Einfügungen an, mit denen der Rot-Schwarz-Baum konstruiert wird, den Abbildung 15.11 zeigt.


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