 Binärbäume |
as_string 
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
 |
|
Naja, in der Aufgabe steht ja schon: Wie könnte man fehlende Knoten repräsentieren?
Die Frage ist erstmal, ist Dir eigentlich klar, wie so ein Binärbaum funktioniert und wie man mit dem Array arbeitet, auch wenn er balanciert ist? Bzw.: Weißt Du, was ein balancierter Binärbaum ist und was ein unbalancierter?
Gruß
Marco
|
|
12.07.2017 16:04 |
|
|
Grünschnabel
unregistriert
|
|
also ja ich weis wie ein Binärbaum aussieht und wie man etwas einfügt und löscht.
was meint er genau mit fehlenden Knoten? habe im internet leider nicht ganz verstanden was mit balancierter Baum gemeint ist.
|
|
|
12.07.2017 19:32 |
|
|
as_string
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
|
|
Ah, ok, daran liegts.
Ideal ist es, wenn der Baum richtig "aufgefüllt" ist. Du brauchst ja mindestens eine bestimmte Höhe des Baumes für eine bestimmte Anzahl von Knoten. In Deinem Beispiel sind es z. B. 7 Knoten. Der Baum hat eine Höhe von 3.
Bei einem Baum mit Höhe 1 kannst Du nur einen Knoten unterbringen.
Bei einem Baum mit Höhe 2 kommen nochmal doppelt so viele (also 2) dazu, macht insgesamt 3.
Bei einem Baum mit Höhe 3 kommen nochmal doppelt so viele (also 4) dazu, macht insgesamt also 3+4=7
Bei einem Baum mit Höhe 4 kommt nochmal doppelt so viele (also 8) dazu, macht insgesamt 7+8 = 15.
Insgesamt hast Du also bei einem Baum mit Höhe h maximal Platz für log2(h)-1 Plätze.
Du könntest aber einen Baum auch so auffüllen, dass Du die Höhe nicht so gut ausnutzt: Stell Dir in Deinem Beispiel vor, dass der Knoten B und seine Kinder D und E gar nicht vorhanden wären und auch F fehlen würde. Dann wäre die Höhe immer noch 3 (von A bis G über C), aber insgesamt wären es nur 3 Knoten, die man auch in einen Baum mit Höhe 2 unterbringen könnte. Das wäre dann ein unbalancierter Baum.
Deutlicher wird es, wenn man einen größeren unbalancierten Baum betrachtet wie in https://de.wikipedia.org/wiki/Balancierter_Baum gleich das erste Bild.
Das Problem mit dem Array ist aber: Ein solcher Baum kann dazu führen, dass Du "Löcher" im Array hättest. Das Array muss ja immer eine Größe von 2^h-1 haben, also 1, dann 3, dann 7, dann 15, etc. Wenn Du aber nur 3 Elemente hast, dann sind ja 4 der sieben Plätze im Array unbelegt.
In unserem "entarteten" Beispiel, bei dem nur noch A, C und G übrig sind, müssten diese immer noch am selben Platz im Array sein, aber alle anderen Plätze müssten leer sein. Die Frage ist nun: Wie kann man diese leeren Plätze markieren?
Ich weiß nicht so genau, was die als Antwort da hören wollen. Man könnte sich ein ungültiges Zeichen überlegen, das man da rein schreibt. Aber welches Zeichen ist denn gültig, welche nicht? Das geht aus der Aufgabe nicht hervor. Wenn man ein char-Array hätte, könnte man z. B. eine 0 rein schreiben anstelle eines gültigen ASCII Werts oder so.
Das angesprochene Problem ist natürlich, dass man bei großen unbalancierten Bäumen dann eine Menge Stellen im Array unbelegt hätte und deshalb Speicherplatz verschwenden würde.
Gruß
Marco
|
|
|
12.07.2017 20:20 |
|
|
Grünschnabel
unregistriert
|
|
Vielen lieben Dank für diese aufwendige Erklärung. Erst durch deinen Text habe ich erst die Aufgabenstellung richtig verstanden 
|
|
|
12.07.2017 22:37 |
|
|
|
