FIM: KV Algorithmen und Datenstrukturen 2

Algorithmen und Datenstrukturen 2 WS 1999/2000

11. Übung - abzugeben am 25. 1. 2000 in Ihrer Übungsgruppe

11.a Bayer-Baum: Aktionen an Hand von konkreten Daten

In einen leeren B(k,h)-Baum mit k=2 werden nacheinander mehrere Elemente eingefügt, danach werden vier wieder gelöscht. Stellen Sie den Baum nach jedem Strichpunkt dar.

Einfügen:	45, 23, 69, 10, 54 ; 9, 34, 76, 84, 41 ; 42, 43, 44, 46 ; 30, 31, 32 ; 11, 12, 13 ;
Löschen:	42, 41, 23 ; 34, 84 ;

Anmerkungen:
Beim Löschen von Werten ersetzen Sie (falls notwendig) durch den symmetrischen Vorgänger.
Überlegungen zum Löschen von Werten und eine kurze Wiederholung des Einfügens ist noch für die LVA am 24. 1. vorgesehen.

11.b Bayer-Baum: Ein Beispiel "aus der Praxis"

Sie haben die Aufgabe, die gesamte Menschheit (ca. 8 Mrd.) elektronisch zu erfassen. Für diese Anforderung (einigermaßen großer Datenbestand) ist ein Bayer-Baum natürlich eine geeignete Implementierungsform.

Doch zuerst einige Überlegungen zum erwarteten Aufwand:

Der verwendete Hintergrundspeicher blockt die Daten in 8 kB-Blöcken, auf die als Ganzes zugegriffen werden kann (read, write, update).
Über die Personen sollen nur grundlegende Daten gespeichert werden (z.B. Name, Geburtsdatum, Geschlecht, Staatszugehörigkeit). Treffen Sie realistische Annahmen.

Überlegen Sie sich (und schreiben Sie die Antworten auch auf!) folgende Fragen:

Welche Aktionen werden die meiste Zeit benötigen (Hintergrundspeicher/Hauptspeicher)?
Wie hoch wird der Baum werden?
Wieviele Knoten werden gelesen / geschrieben, wenn ein neuer Datensatz eingefügt wird (worst case, best case)?
Und beim Suchen?

Wie sieht es aus mit der Auslastung; wieviel Speicherplatz wird im schlechtesten Fall "verschwendet"?

12.a Diskussion: B-Baum Deklarationen, Ausgabe, Suchen und Löschen

Überlegen/wiederholen Sie (auch als Vorbereitung für die Abschlußklausur), wie die folgenden Programme zu realisieren sind:

DEFINITION OF MODULE BBaum;
  TYPE BTreeT= ..........

  PROCEDURE Print(root:BTreeT);
    (* Die Prozedur soll den B-Baum mit der Wurzel root in
       In-Order Folge durchlaufen und die Elemente (somit
       sortiert) ausgeben
     *)
  PROCEDURE Search(root:BTreeT; key:KeyT):BOOLEAN;
    (* Die Prozedur sucht im B-Baum mit der Wurzel root
       nach dem Datenelement mit dem Schlüssel key
       und gibt das Ergebnis der Suche zurück.
    *)
  PROCEDURE Zap(root:BTreeT);
    (* Die Prozedur gibt sämtlichen Speicher des
       B-Baums mit Wurzel root frei.
    *)
END BBaum.

(Diese Diskussion zält nicht mehr zu den "Übungskreuzerln". Daher ist keine Abgabe erforderlich!)

12.b Diskussion: B-Baum Abschätzung

Gegeben ein B(k,h)-Baum (Höhe h): Wieviele Knoten bzw. Datensätze sind in diesem Baum
- minimal (worst case)
- maximal (best case)
enthalten?

(Beachte dabei: )
(Diese Diskussion zält nicht mehr zu den "Übungskreuzerln". Daher ist keine Abgabe erforderlich!)

Last modified: Hörmanseder 2000-01-17