FIM: KV Algorithmen und Datenstrukturen 2

Algorithmen und Datenstrukturen 2 WS 1999/2000

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

12.a B-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 ;

Anmerkung: Beim Löschen von Werten ersetzen Sie (falls notwendig) durch den symmetrischen Vorgänger.

12.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.c Diskussion: B-Baum Deklarationen, Ausgabe, Suchen und Löschen

Sie überlegen, 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.

12.d 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: )

Last modified: hoermanseder@fim.uni-linz.ac.at 2000-01-17