Kategorie: B-Bäume

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

So jetzt wird es lustig… viel spass…!

INFO

Dastellung:  [B-Baum (K,H)]

K = Knoten, die vorgegebene zahl K ist der min wert für Elemente in einem Knoten, und max ist 2*k

H = Höhe, die vorgebene zahl H, ist die max. höhe die ein Baum erreichen darf (wobei die wurzel bereits 1 ist)

• wenn kein wert angegeben ist, heisst es, das es schlichtweg kein limit gibt.
• für die wurzel gilt stehts: anzahl elemente egal

für uns heisst das jetzt: [2,h]

• 2 Knoten = min 2 Elemente pro knoten, max 4 (2*k), sobald also ein 5ter hinzu kommt, muss dieser nach oben hin rausgeschoben werden.
• h = nicht gegeben, also kann es unendlich groß werden (in unserem fall wird die höhe bei 2 stoppen)

Formel zur Berechnung der Knoten

• minimal: 1(Wurzel) + 2/k*((k+1)^(h-1) – 1)
• maximal: (1/2k)*((2k+1)^h – 1)

Formel zur Berechnung der Anzahl der Elemente

• minimal:   2(k+1)^(h-1) + 1
• maximal: ( 2(k+1)^(h-1) ) – 1