---

Geschrieben von Speedyspin am 15.07.2011 um 01:18:

  zwei 2-4 Bäume zusammenfügen

Hallo!

Ich suche eine Möglichkeit zwei 2-4 Bäume mit jeweils n und m Elementen zu einem neuen 2-4 Baum in O(n+m) zusammenzufügen. Offenbar geht das mit Fingersuche. Muss ich dann bei der Fingersuche den Zeiger auf mein kleinstes Element setzen und immer das nächstgrößere suchen?

Eine weitere Möglichkeit, die ich mir überlegt habe, ist ein Mergesort auf die beiden Zahlenfolgen. Also nicht von Beginn an, sondern quasi nur der letzte Schritt davon.

Danke für eure Hilfe!

---

Geschrieben von lol am 20.06.2012 um 23:05:

 

Gibts hier eine Antwort drauf? :/

---

Geschrieben von 3FingerbreitNougat am 11.07.2012 um 16:41:

 

Du Nimmst immer ein Element aus dem alten Baum und fügst es in den neuen ein. Wenn der Baum sich beim einfügen sortiert, funktioniert das so