Wie ist man auf diese Lösung kommen ( Baum so strukturen, dass er minimale Tiefe/Höhe hat)?
Was ich nicht verstehe, das Schema ist, mittleres Element aufgerundet nehmen, das dann immer halbieren.
Also z. B. 8,4,2,1. Danach kapiere ich habe nicht. Wie kam man drauf die 657, dann 12,10,9, 11,14,13 und 15 zu nehmen?
1 Antwort
Ich nehme an, es geht nicht um selbst-balancierende Binärbäume, sondern welche, die neue Werte anhand der Regeln für Binärbäume einfügen, selbst wenn diese dadurch degenerieren.
Um in dem Fall einen Binärbaum minimaler Höhe zu erzeugen, musst du aus der Folge immer die Mitte einfügen, damit sich die nächsten Werte entsprechend gleichmäßig links und rechts verteilen.
Nehme wir an, du hast 15 Werte:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Dann wählst du die Mitte, 8, und fügst sie dem Baum hinzu. Es bildet die Wurzel. Werte kleiner 8 werden links hinzugefügt, Werte größer 8 rechts.
Es bleiben die Werte
[1, 2, 3, 4, 5, 6, 7] und [9, 10, 11, 12, 13, 14, 15]
Jetzt fügst du wieder jeweils das mittlere Element hinzu, 4 uns 12. Welches du zuerst nimmst, ist nicht relevant.
Dadurch hast du einen Baum mit Wurzel 8, darunter 4 und 12. Es bleiben
[1, 2, 3] [5, 6, 7], [9, 10, 11], [13, 14, 15]
Auch hier wieder das selbe Spiel, wenn du jedes Mal den mittlere Wert nimmst, wird bei deinem bestehenden Baum an den Blättern immer je ein Wert links und rechts hinzugefügt und der Baum bleibt balanciert (und damit auf minimaler Höhe).
Danke! Noch verständlicher, als der von der Musterlösung, aus meiner Sicht! Danke dir vielmals!