Binärbäume

Neue Frage »

Auf diesen Beitrag antworten »
Motze Binärbäume

Meine Frage:
Hallo Leute, ich habe eine Aufgabe von meinem Professor bekommen und diese Aufgabe kommt exakt so in der Klausur dran. Lösen müssen wir es aber selber. Kann einer von euch mir dabei helfen? Komme damit gar nicht klar :-(




Meine Ideen:
Ich habe leider keinen Ansatz wie ich anfangen soll, da ich ziemliche Probleme mit diesem Fach habe.
 
Auf diesen Beitrag antworten »
as_string RE: Binärbäume

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
Auf diesen Beitrag antworten »
Grünschnabel RE: Binärbäume

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.
Auf diesen Beitrag antworten »
as_string

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
 
Auf diesen Beitrag antworten »
Grünschnabel

Vielen lieben Dank für diese aufwendige Erklärung. Erst durch deinen Text habe ich erst die Aufgabenstellung richtig verstanden unglücklich
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »