Im BBaumApplet stehen insgesamt drei Operationen zur Verfügung. "insert" fügt den im Textfeld spezifizierten Schlüssel in den BBaum ein. "delete" löscht den spezifizierten Schlüssel und "reset" versetzt das Applet in den Initialzustand, d.h. es existiert kein BBaum. Bei größeren Bäumen, welche nicht gänzlich auf den Bildschirm passen, wird das Navigationspanel des Applets interessant. Damit ist es möglich sich innerhalb des BBaumes zu bewegen oder hinein-/herauszuzoomen. Zwischen Eingabepanel und Navigationspanel wird über die Buttons "<<" und ">>" umgeschalten.
Als Schlüssel werden nur ganze Zahlen akzeptiert.
| search() | |
| insert() | |
| delete() | |
| del() | |
| underflow() | |
| Fehlermeldung |
Die Methodennamen sind an das Skript zur Vorlesung "Datenstrukturen" angelehnt.
Um bei größeren Bäumen (ab Höhe3) die einzelnen Operation noch besser verfolgen zu können, habe ich noch eine 100% Version dieses Dokumentes erstellt, welche das Applet auf maximale Breite und Höhe vergrößert. Es ist emfehlenswert, den Browser vorher zu maximieren.
BBäume sind ausbalancierte Suchbäume. Sie sind besonders für die Aufbewahrung von großen Datenmengen auf sekundären Speichern (z.B. Festplatten) optimiert, weil sie im Vergleich zu normalen Bäumen weniger I/O Operationen bei der Suche benötigen. BBäume sind typische Vertreter der Vielwegbäume. Jeder BBaum Knoten enthält n Schlüssel (keys), welche in einem Array angeordnet sind. Die Anzahl n (in unserem Beispiel n=4) hängt normalerweise von der Blockgröße des sekundären Speichers ab. Jeder Schlüssel beinhaltet neben der eigentlichen Information bzw. dem Verweis auf die Information noch einen Zeiger auf den nachfolgenden BBaum Knoten. Außerdem existiert pro BBaum Knoten noch ein separater Zeiger p0 auf einen nachfolgenden BBaum Knoten. Da wir hier einen Suchbaum vorliegen haben, muß auch eine Ordnung herschen. Die Ordnung ist ähnlich dem binären Suchbaum. Der p0 Zeiger verweist auf die kleineren Schlüssel und die Zeiger der Schlüssel verweisen auf die größeren Elemente, in der Art, daß gilt: Alle nachfolgenden Schlüssel eines Schlüssels i sind größer als i aber kleiner als der rechte Schlüsselbruder i+1.
Ein BBaum wächst immer von unten nach oben. Beim Einfügen wird zuerst nach einem passenden Platz gesucht (siehe Suchkriterium). Ist der passende BBaum Knoten für den Schlüssel gefunden, so wird der Schlüssel in das Schlüsselfeld des Knoten so eingefügt, daß alle Schlüssel aufsteigend sortiert sind. Falls dabei noch ein Platz frei ist, so haben wir Glück gehabt. Ansonsten muß der Knoten geteilt werden. Dabei wird das mittlere Element entnommen, die linke Hälfte bleibt im Knoten, die rechte Hälfte bekommt einen neuen. Das entnommene Element wird beim rekursiven Aufstieg dann in den Vaterknoten eingefügt, welcher sich auch wieder teilen kann. Natürlich passen wir noch auf die Verzeigerung auf. Das, was am mittleren Schlüssel dranhängt, wird p0 Unterbaum vom neu entstandenen, rechten Knoten. Und da die rechte Hälfte immer größer als der mittlere Schlüssel ist, wird sie Nachfolger von ihm.
Das Löschen eines Schlüssels läuft erstmal ähnlich, soll heißen, es wird zuerst der Schlüssel gesucht. Wenn gefunden, dann müssen wir unterscheiden, ob der Schlüssel auf einem äußeren Knoten (Blatt) oder einem inneren Knoten liegt. Im ersteren Fall brauchen wir uns keine weiteren Gedanken zu machen, wie löschen den Schlüssel aus seinem Array. Beim zweiten Fall wird es schwieriger. Wir können den Schlüssel nicht so einfach löschen, weil an ihm ja noch andere Knoten dranhängen. Die Lösung: Wir ersetzen den zu löschenden Schlüssel durch den nächstkleineren Schlüssel (also den rechtesten Schlüssel des "nächstlinken" Unterbaumes). Die Verzeigerung und die Suchordnung bleiben erhalten. Jetzt wären wir auch schon fertig, wenn es da nicht das 50% Füllungskriterium gäbe. Es besagt, daß jeder BBaum Knoten außer die Wurzel immer mit minimal n/2 Schlüsseln besetzt sein muß. Blöd gelaufen, aber das ist so weil wir ja immer an einem schnellen Suchverhalten und damit an einer geringen Baumhöhe interessiert sind. Ergo, wir müssen überprüfen, ob in dem Knoten, wo wir einen Schlüssel löschen, nicht eine Underflow Situation eingetreten ist. Wenn doch, so schauen wir erstmal, ob nicht die Nachbarknoten eine Schlüssel für uns übrig haben. Zuerst fragen wir den rechten Bruder, ansonsten den linken. Warum? Weil es einfacher und schneller ist, an ein Array hinten etwas dranzuhängen, als die erste Stelle neu zu besetzen. Falls noch ein Schlüssel über ist, so holen wir uns diesen. Sind aber beide wegen Rationalisierungsmaßnahmen schon minimal besetzt, so kann uns nur noch der Vaterknoten weiterhelfen. Wir eignen uns also den Schlüssel des Vaterknotens an, der auf unseren Underflow Knoten zeigt. Gleichzeitig verleiben wir uns auch noch den rechten (wenn nicht vorhanden den linken) Bruder ein. Die Lücke im Vaterknoten wird durch eventuell vorhandene rechtere Schlüssel aufgefüllt. Natürlich wird auch die Verzeigerung neu angepaßt. Fertig? Zu allem Überfluß kann es nun noch passieren, daß auch der Vaterknoten zu einem Underflow Knoten wird. Zum Glück, gibt es sowas wie rekursive Programmierung. Falls die alte Wurzel nach einer Löschoperation keine Schlüssel mehr enthält, so wird sie gelöscht. Der p0 Unterbaum wird in diesem Falle neue Wurzel (kann auch nil sein).
Falls ich jetzt jemanden verwirrt haben sollte, so möge man mir vergeben (siehe BBaumApplet).