2-3-4 Baum Top-Down

[undercover]

Hi Leute,
hab mal eine Frage.
Ich tue mich relativ schwer mit dem 2-3-4 Baum nach der Top Down Methode. Einen Binären Baum zu erstellen fällt mir nicht schwer, allerdings der 2-3-4 Baum umso mehr.
Wenn ich von einem leeren Baum ausgehe und als Input die Zahlen in folgender Reihenfolge einlese 4,3,5,1,2,7,9,11,8 wie würde der dazugehörige Baum aussehn?
Die meisten Beispiele Zeigen das einfügen in einen gefüllten Baum, nicht im leeren.

Gruß

 

[Kababär]

Es spielt keine wesentliche Rolle ob man einen leeren Baum oder einen gefüllten Baum vor sich hat, da die Prozedur die gleiche bleibt.

Es gibt viele verschiedene Varianten für einen 2-3-4 Baum und die Fragen, die man sich stellen muss sind:
1. Wann werden Knoten aufgeteilt? Bei 3 oder 4?
2. Wie teile ich Knoten auf?

Ich teile einen Knoten a b c immer auf, sobald er drei Elemente enthält.
Dabei setze ich b als Elternknoten, und setze a als linken und c als rechten Kindknoten von b.
Wichtig hierbei Ist, dass die Werte stets sortiert bleiben.
Ein Anfang wäre
1. 4
2. 3 4
3. 3 4 5 //teile
4. 4
/ \
3 5

Nachteil: die 4er-Grenze wird nicht benutzt.
Aber ein 2-3-4 Baum muss nicht die 4er-Grebze verwenden.
Alternativ zur obigen Vorgehensweise kannst du die Knoten ganz normal auffüllen, bis sie 4 Elemente haben. Danach einfach die zwei größten Elemente nehmen und sie in einen neuen Nachbarknoten einfügen.

 

[JStein52]

als Input die Zahlen in folgender Reihenfolge einlese 4,3,5,1,2,7,9,11,8 wie würde der dazugehörige Baum aussehn?

Könnte so aussehen:
level=0 child=0 /4.0/7.0/
level=1 child=0 /1.0/2.0/3.0/
level=1 child=1 /5.0/
level=1 child=2 /8.0/9.0/11.0/

 

[JStein52]

Oder hättest du das Ganze lieber Schrittweise:

Enter value to insert: 4
level=0 child=0 /4.0/
Enter value to insert: 5
level=0 child=0 /4.0/5.0/
Enter value to insert: 3
level=0 child=0 /3.0/4.0/5.0/
Enter value to insert: 1
level=0 child=0 /4.0/
level=1 child=0 /1.0/3.0/
level=1 child=1 /5.0/
Enter value to insert: 2
level=0 child=0 /4.0/
level=1 child=0 /1.0/2.0/3.0/
level=1 child=1 /5.0/
Enter value to insert: 7
level=0 child=0 /4.0/
level=1 child=0 /1.0/2.0/3.0/
level=1 child=1 /5.0/7.0/
Enter value to insert: 9
level=0 child=0 /4.0/
level=1 child=0 /1.0/2.0/3.0/
level=1 child=1 /5.0/7.0/9.0/
Enter value to insert: 11
level=0 child=0 /4.0/7.0/
level=1 child=0 /1.0/2.0/3.0/
level=1 child=1 /5.0/
level=1 child=2 /9.0/11.0/
Enter value to insert: 8
level=0 child=0 /4.0/7.0/
level=1 child=0 /1.0/2.0/3.0/
level=1 child=1 /5.0/
level=1 child=2 /8.0/9.0/11.0/

Edit: Das Einfügen geschieht nach folgenden Regeln (von Wikipedia):

• Ein Knoten wird mit Elementen aufgefüllt, bis er drei Elemente enthält (vgl. B im Beispiel).
• Wenn ein viertes Element aufgenommen werden soll, wird der Knoten gespalten (engl. split) in einen Knoten mit zwei Elementen (J K im Beispiel), einen Knoten mit einem Element (M im Beispiel) und ein mittleres Element (L im Beispiel), das in den Elterknoten aufgenommen wird (vgl. Schritt 2 im Beispiel).
• Ist der Elterknoten voll besetzt, wird das Element im Baum weiter nach oben gereicht. Erreicht das Element die Wurzel des Baumes und ist dieser schon mit drei Elementen besetzt, wird eine neue Wurzel nach gleicher Aufteilungsregel erzeugt

 

[undercover]

Vielen Dank für die Ausführliche Hilfe, konnte damit nun den Baum erstellen