Berechnungen im B-Baum (MIN / MAX)
14. Juli 2014
Hier einmal kurz veranschaulicht wie man die Minimalen und Maximalen Elemente im B-Baum berechnet (und aufzeichnet)
– sehr ausführlich –
———————————
B-Baum Typ (2,3) (Berechnung von MIN)
– es müssen MINDESTENS 2 Elemente in einem Knoten stehen
– ausgenommen der WURZEL dessen Anzahl ist egal. Aber es muss mindest. 1 sein.
damit Kinder Knoten gebildet werden können. (Jeder Knoten hat K+1 Kinder)
B-Baum Typ (2,3) (Berechnung von MAX)
– jeder Knoten muss komplett gefüllt sein (K*2 Knoten => 2*2 = 4)
– Die Wurzel muss jetzt natürlich auch komplett befüllt sein.
– es muss über die Höhe 3, für jeden Knoten k+1 Kinder geben
EDIT
Ich habe gerade noch eine kleine Brücke gefunden. Für alle die sich das keine langen komplexen Formeln merken können.
MIN
Ihr nehmt einfach die vorherige anzahl an Knoten, und nehmt dann [ Knoten * Knoten + Knoten ]
Und am ende müsst ihr diese nur noch mit der Anzahl der Elemente in einem Knoten Addieren. (funktioniert nur bei der berechnung von MIN)
Berechnung Typ (2,3)
Die Wurzel hat einen Knoten. also:
1*1 +1 = 2 -> 2 knoten auf der höhe 2
jetzt nehmt ihr das ergebnis von der Wurzel, und rechnet damit weiter
2*2+2 = 6 -> 6 Knoten auf der höhe 3
usw.
6*6+6 = 36 -> 36 knoten auf der höhe 4 (ab hier macht das Zeichnen dann auch keinen spass mehr : )
—
Für MAX kann man das ähnlich darstellen: im Typ (2,h)
es ist einfach immer MAL 5 => denn 2*2+1 (Knoten * 2 + 1 Kind)
[ ( KNOTEN * 5 ) ]
Wurzel : max 4
4 * 5 = 20
20 * 5 = 100
100 * 5 = 500
500 * 5 = 2500
—–
Ich glaub ausführlicher geht es nicht mehr :)
Wenn dennoch fragen offen geblieben sind: einfach anschreiben!
——
HAUSAUFGABEN
Ich höre schön das stöhnen und seufzen aus dem Hintergrund ^^
Aber die beste Art etwas neues zu lernen, ist nun mal das mehrfache anwenden.
Die Aufgabe ist auch ganz simpel: berechnet die folgenden Typen von B-Bäumen mal per Hand durch. (und macht dabei auch gerne Skizzen)
Und zur Kontrolle habt ihr hier direkt alle Lösungen (>“<)
1) B-Baum Typ (2,6) – min
2) B-Baum Typ (3,4) – max
3) B-Baum Typ (3,4) – min
4) B-Baum Typ (2,5) – max
