B-Bäume

[Gast vplus]

Hallöchen,

kenn jemand von Euch zufällig die Formel, mit der man die Anzahl der maximal möglichen Einträge von einem B-Baum der Höhe h vom Typ k berechnen kann?

Außerdem brauche ich auch noch einmal die Formel, mit der man die Höhe von einem B-Baum vom Typ k mit X Einträgen berechnen kann.

Viele Grüße

vplus

[SNOWMAN]

Ach, das müsst ich eigentlich wissen, hatte ich erst vor kurzem in der Schule :hells:

Vllt. hillft folgende Seite weiter:

http://exai2.wu-wien.ac.at/~panny/algdat/maintree/node1.html

Afair(as far as i remember): ist das doch mit diesem mathematischen ! was, oder? Ich hab vergessen wie des heißt, als bay. Realschüler hat man das nicht behandelt :-(

[Anybody]

Das "!" nennt sich Fakultät

[Gast vplus]

Hi,

ich meine aber keinen binären Suchbaum, sondern einen B-Baum bzw. Bayer-Baum... .

Gruß

vplus

[geloescht_Newlukai]

Also. Ein Baum vom Typ 3 und der Höhe 3 hat doch auf der ersten Ebene 1, dann 3 und dann 9 Knoten.

Bei ein paar Versuchen mit anderen Bäumen kommt man dann auf:

1 + sum(k^i)

wobei i von 1 bis n-1 läuft.

Die andere müßt ich ma noch überlegen.

[kingofbrain]

Servus,

Frage eins kann Dir Wikipedia beantworten. Leider komme ich jetzt nicht mehr drauf, aber mit dem Suchbegriff "B-Baum" habe ich am Wochenende genau diese Formel gefunden. Auswendig weiss ich sowas nicht mehr, das ist leider schon wieder zu lange her.

Peter

[Gast vplus]

Ich habe in der Zwischenzeit ein klein wenig rumprobiert und bin dabei auf die folgende Formel gekommen!

n = a(i) = 2 * k * (2*k+1)^i (mit i = 0..h)