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

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 :-(

Das "!" nennt sich Fakultät

Hi,

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

Gruß

vplus

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.

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

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)