FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Praktische Informatik

GDB - Bäume

GDB - Bäume 2008-02-23 11:38
Anonymer User
Wenn man einen B*-Baum der Klasse (2,2,h*) hat, was bedeutet dann das h*? Dass die Höhe beliebig sein kann?
Und was bedeutet der Splitfaktor? Normalerweise hat man doch m=1. Was ändert sich wenn m=2 ist?

RE: GDB - Bäume 2008-02-23 14:47
T
Und was bedeutet der Splitfaktor? Normalerweise hat man doch m=1. Was ändert sich wenn m=2 ist?
bevor man einen knoten splittet, müssen erst zwei vollständig gefüllt sein. das heisst vorher versucht man durch hin- und herschieben alles noch irgendwie auszugleichen.

RE: GDB - Bäume 2008-02-23 21:38
ole
hat schon mal jemand die musterlösung zur klausur angesehen?

in aufgabe 9a) wird ein [latex]\tau (2,2)[/latex] baum verwendet.
laut skript müssen alle pfade von einem Blatt zur Wurzel also eine länge von 2-1 = 1(GDB-6-19) haben.
in der musterlösung wird aber so gesplittet, dass sich eine länge von 2 ergibt(Einfügen der 54). was ist denn nun falsch? das skript oder die musterlösung?

RE: GDB - Bäume 2008-02-24 10:43
Anonymer User
Hast Recht. In der Aufgabestellung steht tatsächlich (2,2). In der Musterlösung haben sie wirklich vergessen, das anzugeben. Aber was will man denn machen? Entweder erhöht sich die Höhe des Baums beim Einfügen in den vollen Knoten, oder man verletzt die Eigenschaft k, also dass da mehr einträge eingefügt werden dürfen, als 2k. Wenn man den höheren Splitfaktor hätte, könnte man erstmal alle Knoten voll machen, aber trotzdem musste man die Höhe ändern, wenn man noch mehr einfügt…

RE: GDB - Bäume 2008-02-24 17:01
Anonymer User
könnte jemand den vorgang "mischen" nach löschen nochmal erklären? wäre gut an dem bespiel im skript kapitel 6 seite 19.

RE: GDB - Bäume 2008-02-24 21:13
vlog
Das ist die Skriptfolie GDB-6-38.

Man möchte 11 löschen. Sie steht in der Wurzel, und kann nicht einfach so gelöscht werden, weil sie noch 2 Zeiger enthält. Dafür braucht man einen Sohnknoten. Es stehen 3 zu Auswahl - entweder der mit den Schlüsseln 1,3,9 oder der mit 15,17 oder mit 19,25. Ich würde lieber den linken nehmen, weil da es noch 3 Einträge gibt (vorausgesetzt, es ist ein (2,h) Baum, also mit minimaler Anzahl Einträge 2). Es wird aber der mittlere genommen und aus diesem wandert der Schlüssel 15 nach oben auf den Platz, wo 11 gestanden hat.
So. Jetz haben wir unten einen Knoten mit nur einem Eintrag. So was darf es nicht geben bei den Bäumen mit (2,h). Also vereinigt (mischt) man die Knoten. In diesem Fall den rechtesten mit dem Knoten, in dem nur die 17 übrig geblieben ist. Dafür wandert der Schlüssel 18 nach unten und die Einträge aus dem rechten Knoten werden in den mittleren kopiert.

Also zusammengefasst die Vorgehensweise beim Mischen:
1. Es sind weniger als die minimale Anzahl Einträge in dem Knoten
2. Es wandert der Schlüssel (der die Zeiger auf die zu mischende Knoten enthält) vom Vater in den betroffenen Sohnknoten.
3. Aus dem anderen Knoten werden alle Einträge in den Knoten mit dem von Oben gewanderten Element kopiert. Und der leere Knoten wird gelöscht.

Korrigiert mich, wenn ich was falsch geschlieben habe :)

RE: GDB - Bäume 2008-02-25 12:25
SkaterAzN
Auf den Musterlösungen zum Aufgabenblatt 6 aufgabe 1c.
Wieso wird der baum so komisch gesplittet nach dem einfügen von der 4?

RE: GDB - Bäume 2008-02-25 15:10
Anonymer User
Ist wegen dem Splitfaktor m=2.
Die 4 wird, wie beim normalen Split, als Zeiger nach oben kopiert, weil sie in der Mitte des Knotens stehen würde. Oben würde dann stehen 4_8. Und wegen dem Splitfaktor 2 werden die Einträge auf m+1 also auf 3 Knoten regelmäßig verteilt. Deswegen hat man am Ende nicht die 3 Knoten der Form:
2_3_4, 6_8 und 12_17_20_25, sondern je 3 Elemente: 2_3_4, 6_8_12 und 17_20_25. Jetzt sind die Zeiger aufm Vaterknoten, 4_8 nicht mehr aktuell. Deswegen verschwindet die 8 und auf deren Stelle wird die 12 kopiert (der höchste Element des Knotens).

So verstehe ich das.

RE: GDB - Bäume 2008-02-25 21:02
Anonymer User
Und was bedeutet jetzt das h*, wenn man einen B*-Baum der Klasse (2,2,h*) hat? Dass die Höhe beliebig sein kann?

RE: GDB - Bäume 2008-02-26 09:36
vlog
Genau. Die Höhe kann beliebig sein.