Hallo, folgendes Problem:
wie lässt sich ein 2-3-Baum rekursiv erstellen?
Genauer gesagt ich gebe in den Konstruktor der Klasse ein sortiertes Array(z.B int a[] = {1,2,3,4,5,6,7,8,9,10}) und daraus soll dann der Konstruktor den Baum erstellen.
Zum 2-3-Baum:
Datensätze befinden sich nur in Blättern
Alle Nodes über den Blättern tragen Keys anstatt Datensätze
Jede Node kann bis zu 3 Keys tragen und min 2 und max 3 Kinder haben
Das Problem an der ganzen Sache ist das wir keine insert-Funktion implementieren sollen, was ich zunächst erstmal komisch finde.
Im Anhang liegt der skizzierte Baum vor der aus obigen Array entehren würde bei korrekter Implementerung.
Wäre nice wenn mir jemand Gedankenanstöße geben könnte wie man an diese Sache rangeht, ich möchte mir auch nicht die Lösung irgendwie erschleichen oder so, ich bin eigentlich ziemlich ehrgeizig was solche Datenstrukturen angeht aber momentan hab ich in der Sache gar kein Durchblick.
Normale Trees und Binary Search Trees sind mir geläufig, falls das irgendwie hilft.
Ich hätte hier noch ne Auflistung des Baumes in preOrder mit Blättern in <> geschrieben und Nodes mit Keys in () geschrieben:
(5,10)
(2,5)
(1,2)
<1>
<2>
(3,4,5)
<3>
<4>
<5>
(7,10)
(6,7)
<6>
<7>
(8,9,10)
<8>
<9>
<10>
wie lässt sich ein 2-3-Baum rekursiv erstellen?
Genauer gesagt ich gebe in den Konstruktor der Klasse ein sortiertes Array(z.B int a[] = {1,2,3,4,5,6,7,8,9,10}) und daraus soll dann der Konstruktor den Baum erstellen.
Zum 2-3-Baum:
Datensätze befinden sich nur in Blättern
Alle Nodes über den Blättern tragen Keys anstatt Datensätze
Jede Node kann bis zu 3 Keys tragen und min 2 und max 3 Kinder haben
Das Problem an der ganzen Sache ist das wir keine insert-Funktion implementieren sollen, was ich zunächst erstmal komisch finde.
Im Anhang liegt der skizzierte Baum vor der aus obigen Array entehren würde bei korrekter Implementerung.
Wäre nice wenn mir jemand Gedankenanstöße geben könnte wie man an diese Sache rangeht, ich möchte mir auch nicht die Lösung irgendwie erschleichen oder so, ich bin eigentlich ziemlich ehrgeizig was solche Datenstrukturen angeht aber momentan hab ich in der Sache gar kein Durchblick.
Normale Trees und Binary Search Trees sind mir geläufig, falls das irgendwie hilft.
Ich hätte hier noch ne Auflistung des Baumes in preOrder mit Blättern in <> geschrieben und Nodes mit Keys in () geschrieben:
(5,10)
(2,5)
(1,2)
<1>
<2>
(3,4,5)
<3>
<4>
<5>
(7,10)
(6,7)
<6>
<7>
(8,9,10)
<8>
<9>
<10>