Algorithmen[8]#2

[Christian S.]

Hallo, hat jemand von euch eine Idee in welche Richtung dieser Algorithmus zielen könnte? Überlege jetzt schon eine Weile, doch bisher scheitert jede Variante die mir eingefallen ist an der Invariante.
Edit: Falscher Titel, meine natürlich den für den (a, b)-Baum.

[Christian S.]

Würde mich echt über einen Tipp freuen, ich weiß insbesondere nicht, was ich mit dem Hinweis auf dem Blatt bezüglich der Höhe des Baumes anfangen soll .

[Thomas]

hm mit der höhe kann man sich die minimale und die maximale anzahl an knoten ausrechnen die ein graph der höhe h haben kann.außerdem kann man mit der höhe berechnen wieviele knoten eine ebene mind. oder höchstens vorhanden sein können. bin mit meinen überlegungen bis jetzt aba auch noch nicht wirklich weit gekommen.

[ryo]

Meine Frage ist auch, wie der Baum dann genau gespeichert sein soll. Als Array in implizitier Form?

Dann kann man ja mittels der Höhe und so die maximale Anzahl an Knoten ausrechnen und daraus die Größe des Arrays. Einfach maximale Größe und ungenutzte Knoten / Spaltschlüsselfelder einfach leer lassen.

Und dann einfach mal nen Graphen angucken. Auf der unteren Ebene ist ja, solange die Knoten maximal gefüllt sind, jedes bte Element nicht mehr als Spaltschlüssel in der untersten Ebene, sondern in der Ebene drüber. Für die gilt selbiges, immer der bte Schlüssel ist in der Ebene drüber.
So könnte man denke ich anfangen. Dabei halt immer Abfragen, wie groß das restliche Array ist. Solange noch "volle" Knoten erstellt werden können, also mit Ausgangsgrad b, einfach weitermachen, sobald das nicht mehr geht, halt aufpassen, dass beide Grad >= a haben.

Ich würde mal irgendwie so anfangen, hoffe mal, man versteht, wie ich das meine...

[Christian S.]

Meine Frage ist auch, wie der Baum dann genau gespeichert sein soll. Als Array in implizitier Form?

Dann kann man ja mittels der Höhe und so die maximale Anzahl an Knoten ausrechnen und daraus die Größe des Arrays. Einfach maximale Größe und ungenutzte Knoten / Spaltschlüsselfelder einfach leer lassen.

Und dann einfach mal nen Graphen angucken. Auf der unteren Ebene ist ja, solange die Knoten maximal gefüllt sind, jedes bte Element nicht mehr als Spaltschlüssel in der untersten Ebene, sondern in der Ebene drüber. Für die gilt selbiges, immer der bte Schlüssel ist in der Ebene drüber.
So könnte man denke ich anfangen. Dabei halt immer Abfragen, wie groß das restliche Array ist. Solange noch "volle" Knoten erstellt werden können, also mit Ausgangsgrad b, einfach weitermachen, sobald das nicht mehr geht, halt aufpassen, dass beide Grad >= a haben.

Ich würde mal irgendwie so anfangen, hoffe mal, man versteht, wie ich das meine...

Den Baum soll man afaik in der in der Vorlesung vorgestellten Struktur speichern (ABItems /ABTree). Wenn du das ganze von unten aufziehst bekommst du in bestimmten Fällen immer Probleme mit der Balancierung. Unser Tutor meinte man solle das ganze von oben aufziehen per geschickter Splitterwahl. Doch genau hier liegt mein Problem. Ich weiß nicht, wie ich aus log_b(n+1) und der (verbleibenden) Elementanzahl die Anzahl der Splitter pro Knoten bestimmen soll.

[Christian S.]

Hm, keiner eine Idee ?

[Thomas]

ne leider ist mir bis jetzt auch noch nix eingefallen, wär für nen tipp auch sehr dankbar. falls ich noch aus purem zufall nen geistesblitz haben sollte meld ich mich nochma^^

[Thomas]

ich glaube ich hab mittlerweile ne lösung gefunden aba leider keine ahnung wie ich das als pseudocode implementieren soll.
und zwar berechnet man zuerst die höhe des baumes. dann rechnet man (a+b)/h und rundet das ergebnis auf.
z.b. hat man 25 elemente und einen (2,4) baum und somit h = 3. dann erhält man für (a+b)/h = 2. d.h. man muss jedes 2. element als splitter benutzen.
hier wären das 2, 4 ,6 ,8 , 10, ... , 24. und hat dann 13 blätter. die 12 splitter speichert man in einem blatt und wiederholt den vorgang. man hat 12 elemente erhält eine höhe h = 2. (a+b)/2 = 3 jedes 3. element ergibt 6 12 18 und 24 wobei das letzte element eines ab-items nicht als splitter benutzt werden kann. also erhält man 6 12 18. da n nun 3 ist und 3 <= b-1 hat man die wurzel. der baum sähe dann so aus:
6|12|18
2|4 - 8|10 - 14|16 - 20|22|24
1 - 3 - 5 - 7 - 9 - 11 - 13 - 15 - 17 -19 - 21 -23 - 25

das ganze hab ich noch nicht wirklich oft getestet , aba bei nem (2,3) baum mit 12 elementen einem (4,7) baum mit 10 einem (3,6) mit 10 und einem (2,4) mit 25 hats mal geklappt. falls jemand nen tipp hat wie man das gescheit aufschreibt oder vllt nen fall findet wos nicht klappt fänd ichs super
Edit: habs grad noch mit nem (3,5)-baum mit 27 elementen getestet da hats auch geklappt, aba wie gesagt keine garantie, dass das ganze richtig is