B-Bäume

B - Bäume sind Mehrweg - Bäume. Sie entsprechen allen Kriterien einer Baumstruktur. Siehe Ausarbeitung: "Bäume Allgemein".

Eigenschaften:

1.) Ein B -Baum hat eine Ordnung (k), die die Kapazität eines Knotens angibt.

2.) Knoten können mindestens k und maximal 2*k Nachfolger haben.

3.) Alle Blätter haben die selbe Höhe. Das heißt B - Bäume sind balanciert.

4.) Die Wurzel hat entweder keine oder mindestens zwei Nachfolger.

5.) Die Zeiger der Knoten auf die Nachfolger sind, in einem logischen Algorithmus aufgebaut, zwischen den Schlüsselwerten Der logische Algorithmus sortiert die einzutragenden Schlüsselwerte in die Knoten und in die Nachfolgeknoten ein. In den linken Nachfolgeknoten werden die < oder = Schlüsselwerte eingetragen und in den rechen Nachfolgeknoten die> Schlüsselwerte. (Siehe Beispiel B - Baum der Ordnung 3)

6.) Die Inhalte der Knoten (Schlüsselwerte) dienen als Wegweiser.

7.) Die Datenwerte werden in die Blätter eingetragen, das sind in die untersten Glieder der hierarchisch aufgebauten Baumstruktur. (Blätter sind Knoten ohne Nachfolger, siehe Ausarbeitung "Baumstrukturen Allgemein") Außerdem werden die Datenewerte als Schlüsselwerte in den Vaterknoten eingetragen, wenn die Kapazität des Knotens überschritten wird und der Knoten aufgespallten werden muss. (Siehe einfügen eines Knotens)

8.) Ein B - Baum ist nur ein Suchbaum. Das heißt es werden keine anderen Daten als die Schlüsselwerte in den Baum eingetragen.

9.) In einen Knoten können maximal 2 * k + 1 Werte eingetragen werden.

10.) Der B - Baum wächst nach oben.

Das heißt, wenn der Wurzelknoten die maximale Anzahl von eingetragenen Werten erreicht hat, teilt er sich in 2 neu Knoten und bildet einen neuen Wurzelknoten. Der neue Wurzelknoten verweist auf die alten geteilten Wurzelknotenteile.

Knotenstruktur:

Wurzelknoten und Vaterknoten:

Speicherplatz für Schlüßelwert,

Pointer der auf den linken Nachfolgeknoten (Sohnknoten) zeigt,

Pointer der auf den rechten Nachfolgeknoten (Sohnknoten) zeigt.

Blatttknoten = Datenknoten:

Speicherplatz für Schlüßelwert.

Funktionen:

Einfügen eines Knotens:

Eingefügt wird in die Blätter des Baumes.

1.) Positionieren: Das entsprechende Blatt in welches eingetragen werden soll, wird durch den Suchalgorithmus gesucht(Siehe Eigenschaften Punkt 5.)).

2.) Kontrollieren: Wenn Platz vorhanden ist, wird der Wert eingetragen und die Prozedur ist beendet.

Ist das Blatt vollkommen mit Daten gefüllt (Kapazität des Knotens = 2*k), wird der Inhalt des vollen Blattes aufgeteilt. Der Datensatz wird davor noch professorisch in das Blatt eingetragen. (Erklärungmaximal 2 * k + 1 Einträge in einen Knoten möglich, siehe Eigenschaften Punkt 8.)).

3.) Aufteilen: Der mittlere Datensatz wird als neuer Schlüssel in den Vorgängerknoten (Vaterknoten) eingetragen. Dieser Schlüssel verweist auf ein neu erstelltes Blatt. Die rechts vom mittleren Datensatz stehenden Daten, werden in das neue Blatt eingetragen.

Ist der Vaterknoten vollkommen mit Daten gefüllt muss auch er aufgeteilt werden. Diese Prozedur läuft solange bis ein Vaterknoten gefunden wird der einen freien Speicherplatz zur Verfügung hat, oder bis der Wurzelknoten des Baumes erreicht worden ist.

Hat der Wurzelknoten einen freien Speicherplatz, wird der Datensatz eingetragen.

Ist auch der Wurzelknoten vollkommen gefüllt muss er ebenso aufgeteilt werden. (Siehe Aufteilen des Wurzelknotens)

4.) Aufteilen des Wurzelknotens: Der mittlere Wert vom Nachfolgeknoten (Sohnknoten) wird zu dem Wurzelknoten dazugehängt. Darauf wird der mittlere Wert in eine neu erstellten Wurzelknoten eingetragen, der auf die aufzuteilende Wurzel zeigt. Damit wird der der neu erstellte Knoten zur neuen Wurzel. Jetzt werden die rechts vom mittleren Datensatz der alten Wurzel stehenden Daten in einen neu erstellten Knoten eingetragen. Die neue Wurzel zeigt auf diesen neuen Nachfolgeknoten und die Prozedur ist beendet.

Funktionen:

Löschen eines Elementes: (einfachster Fall)

1.) Zuerst wird der zu löschende Wert wird gesucht.

2.) Dann wird der Knoten in dem das zu löschende Glied steht und der Nachfolgeknoten (Sohn) zusammengeschlossen und kontrolliert, ob die maximale Kapazität nicht überschritten wird.

3.) Wenn die Kapazität überschritten wurde, dann wird der

604 Worte in "deutsch"  als "hilfreich"  bewertet