FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Praktische Informatik

Gdb B-Bäume

Gdb B-Bäume 2009-02-11 18:56
Anonymer User
Kann mir jemand sagen wie ich auf die anzahl der Blätter komme in der Musterlösung zu Blatt 7 Aufgabe 2a) woher weiss ich das es nur 25 blätter gibt und nur 6 innere Knoten??
Woher weis ich das bei der Grossen Seite und woher bei der Lleinen???

RE: Gdb B-Bäume 2009-02-11 19:03
Anonymer User
Und warum wird im Skript manchmal gesagt das die maximale Belegung eines Knotens in einem B-Baum 2k ist und manchmal 2k+1 was sollen wir nun nehmen??

RE: Gdb B-Bäume 2009-02-11 19:55
Loom
Kann mir jemand sagen wie ich auf die anzahl der Blätter komme in der Musterlösung zu Blatt 7 Aufgabe 2a) woher weiss ich das es nur 25 blätter gibt und nur 6 innere Knoten??
Woher weis ich das bei der Grossen Seite und woher bei der Lleinen???

Die kleine Seite hat eine minimale Anzahl von Knoten und der große Teilbaum hat die maximale Anzahl Knoten. Denn nur dadurch ist die Entartung maximal (größte Differenz).

Wie angegeben ist die Höhe des Baumes 4 und die der beiden Teilbäume jeweils 3 (Eins weniger). Nun muss man nur noch die Eigenschaft des B-Baums benutzen: Ein Knoten hat min. k und maximal 2k Einträge (ausser der Wurzel, die hat min. 1). D.h. für den kleinen Baum mit minimalen Einträgen sind in jedem Knoten k Einträge (also 2). Jetzt kann man einfach durchzählen:
Höhe 1: ein Knoten (mit k=2 Einträgen und 3 Kindern)
Höhe 2: drei Knoten (die Kinder der Höhe 1; je 2 Einträge und 3 Kinder)
Höhe 3: von drei Knoten jeweils 3 Kinder = 3*3 = 9 Knoten (Blätter)
Zusammen: 1 + 3 + 9 = 13

Für den größeren Baum entsprechend, nur dass jeweils 2k Einträge und somit 2k+1 Kinder vorhanden sind. Man kann das einfach als Summe schreiben: [latex]\sum_{i=1}^{h} (2k+1)^{i-1} = \sum_{i=1}^{3} 5^{i-1} = 5^0 + 5^1 + 5^2 = 31[/latex]

Das 2k+1 ist übrigens der Fanout, welcher den maximalen Verzweigungsgrad angibt (also wieviele Kinder ein Knoten max. haben kann) und wird in den Folien mit m bezeichnet.

Und warum wird im Skript manchmal gesagt das die maximale Belegung eines Knotens in einem B-Baum 2k ist und manchmal 2k+1 was sollen wir nun nehmen??
Ich weiß zwar nicht wo du das gefunden hast, aber ein B-Baum-Knoten hat immer max. 2k Einträge. Dabei besteht ein Eintrag aus Schlüssel, Daten und Zeiger. Zusätzlich hat der Knoten noch selbst einen Zeiger (siehe Aufbau eine B-Baum Knotens). Daraus ergibt sich, dass ein Knoten max. 2k+1 Kinder hat (da er 2k+1 Zeiger beinhaltet).

RE: Gdb B-Bäume 2009-02-11 23:26
X3K6A2
woher weiss ich das es nur 25 blätter gibt und nur 6 innere Knoten

In der Groessenordnung ist der Baum noch von Hand zeichenbar, kann ich sehr empfehlen zum Verstaendniss. Meine ascii-art Kuenste reichen leider nicht fuer einen schoenen Baum hier.

RE: Gdb B-Bäume 2009-02-12 11:45
Anonymer User
Wie kommst du auf die hoch i-1 ?? Inder formel für :"Die Anzahl der Knoten N in einem vollständigen Baum der Höhe h" wird von i=0 gezählt und nur mit hoch i gerechnet?
Habe zwar verastanden das es Funktioniert würde baer gerne wissen woher das i-1 kommt:=)

RE: Gdb B-Bäume 2009-02-12 15:16
rothose86
Ob du von i=1 bis h und mit (i-1) in der Summe rechnest oder von i=0 bis h-1 mit i in der Summe ist das gleiche.

Wichtig bei den GDB-Bäumen ist zum Unterschied von anderen Veranstaltungen: Die Wurzel zählt bereits als Höhe 1! Deshalb muss auch nur bis h-1 summiert werden, weil mit i=0 schon die Wurzel erwischt wird, und diese bereits zur Höhe mitzählt.

RE: Gdb B-Bäume 2009-02-12 18:58
Mr.Powers
Zeichnen Sie alle B-Bäume der Klasse t (1,2) bei Vorgabe folgender Schlüssel:
1, 2, 3, 4, 5, 6
Bestimmen Sie dazu jeweils eine Einfügereihenfolge für jede der möglichen Baumausprägungen. Warum führen unterschiedliche Einfügereihenfolgen unter Umständen zu identischen Baumausprägungen?
Woher weiß ich vorher welche unterschiedlichen Baum Ausprägungen es gibt oder muss man das durch auf zeichnen ausprobieren?
Und warum führen unterschiedliche Einfügereihenfolgen nun zu identischen Baumausprägungen??

RE: Gdb B-Bäume 2009-02-12 19:08
rothose86
Woher hast du die Aufgabe ? ;)

RE: Gdb B-Bäume 2009-02-13 09:26
Mr.Powers
Ist ein altes Aufgabenblatt :)aber wie man ja weiß nehmen die Profs immer ganz gerne Aufgaben von alten Blättern:)