Blatt 11.1

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Blatt 11.1
Hallo,

kann mir bitte einer erklären was die a) und b) bei der ersten Aufgabe zu bedeuten haben? Ein Binärbaum hat immer eine maximale Höhe, oder nicht? Wenn die maximale Höhe n-1 Kanten mit n Knoten ergibt, dann ist es immer der Fall und die Reihenfolge würde keine Rolle spielen. Und bei der minimalen Höhe verstehe ich das auch nicht. Eine minimale höhe mit log2n in diesem beispiel würde 2.4454… etwas ergeben, und das soll meine neue Höhe sein? Das wäre unmöglich um ehrlich zu sein.

Vielleicht versteh ich das ganze falsch und brauche dringend eine Erklärung.

Danke,
H

3

Ich glaube es ist so gemeint:
angenommen du hast nur einen knoten. dann hat der baum die max. höhe 0
bei 2 knoten ist die max höhe 1.
Bei 3 knoten kann die höhe zwar auch 1 sein, aber wenn man schlecht sortiert ergibt sich als max höhe:2
zB die zahlen 3,2,1 einfügen ergibt:
3
2
1
höhe:2

wenn du sie aber anders einfügst. z.B. 2,1,3

                            2
                         1     3

hat er nur höhe 1

4

Ja ist verständlich, aber was bedeutet dieses n-1 Kanten in den Vorlesungsfolien? Und nehmen wir an die Höhe würde man so berechnen dann hätte der Ergebnis Baum dieser Aufgabe mit irgendeiner Reihenfolge immer eine max höhe, nicht wahr? Und noch eine Frage, wenn das so wäre wie würde ein Baum mit min höhe aussehen? Der kann auch irgeneine Reihenfolge haben und es würde immer stimmen. Das Problem bei mir ist, erstens ich versteh die Aufgabenstellung nicht wirklich und zweitens fehlt da was in der Aufgabe, wie z.B. ob mein neuer Baum mit meiner neuen Reihenfolge eine bestimmte höhe haben soll.

5

ein baum mit n knoten hat n-1 kanten.
beispiel 1 knoten : 0 kanten.
Aber das ist für die aufgabe unwichtig.
wichtig ist, dass die maximale höhe eines binärbaumes mit n knoten auch n-1 ist.
wenn du also 3 knoten hast, dann kann der baum maximal die höhe 2 erreichen.
und die minimale höhe, die man mit 3 knoten erreichen kann ist log2(3) [abgerundet] = 1.

Nein, du siehst ja an meinem Beispiel, dass die unterschiedliche Einfügereihenfolge zu unterschiedlichen Höhen geführt hat

Das steht da.
bei b soll der baum maximale höhe haben.
bei c minimale höhe.

Es sind 8 Zahlen, die du hast. Also soll dein Baum in Aufgabe b die Höhe 7(max Höhe) haben
und in Aufgabe c soll er die Höhe 3 (min Höhe) haben.

6

Okay, jetzt habe ich es verstanden. Danke dir.