Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis Anzahl Blätter vollständiger Binärer Baum » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Beweis Anzahl Blätter vollständiger Binärer Baum
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Ic3Cub3
Grünschnabel


Dabei seit: 05.08.2017
Beiträge: 6

Beweis Anzahl Blätter vollständiger Binärer Baum Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Meine Frage:
Hallo,

da ich neu in diesem Forum bin, bitte ich um Nachsicht, falls ich Fehler machen sollte smile

Aufgabe: Wie viele Blätter hat ein vollständiger binärer Baum der Höhe h? Beweis per vollständiger Induktion.



Meine Ideen:
Behauptung:
Baum der Höhe h hat 2^h Blätter

Induktionsanfang:
für h=0 --> 2^0=1 Blatt
stimmt.

Induktionsschritt:
T ist ein Baum der Höhe h
die Wurzel von T hat zwei Teilbäume als Söhne, die jeweils die Höhe h-1 haben
Diese Teilbäume haben eine Blätteranzahl von 2^(h-1)
Somit hat T 2*2^(h-1)=2^(h) Blätter.


Ich denke, dass die Grundidee hierbei richtig ist.
Allerdings glaube ich, dass dieser Beweis nicht vollständig ist. Z.B. weiß ich nicht, wie ich beweisen soll, dass die Teilbäume eine Blätternanzahl von 2^(h-1) haben.
Außerdem bin ich mir auch nicht sicher wie ich den Beweis formal korrekt aufschreiben soll...
Ich wäre sehr dankbar für eure Hilfe!

LG Ic3Cub3
05.08.2017 17:42 Ic3Cub3 ist offline Beiträge von Ic3Cub3 suchen Nehmen Sie Ic3Cub3 in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 400
Herkunft: Heidelberg

RE: Beweis Anzahl Blätter vollständiger Binärer Baum Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Zitat:
Original von Ic3Cub3
da ich neu in diesem Forum bin, bitte ich um Nachsicht, falls ich Fehler machen sollte smile

Willkommen im Informaitkerboard! Wink
Zitat:
Original von Ic3Cub3
Induktionsanfang:
für h=0 --> 2^0=1 Blatt
stimmt.

Ich würde nicht gerade mit der 0 anfangen, ich glaube sogar, dass dann der Beweis falsch wird:
Die Grundidee ist ja bei der vollständigen Induktion: Nimm einen konkreten Anfang, für den es i. A. ja einfach ist zu zeigen, dass die Bedingung erfüllt ist. Beweise dann mithilfe des Induktionsschritts, dass es für das darauf folgende und das dann darauf folgende und so weiter auch erfüllt ist.
Das bedeutet: Insbesondere musst Du natürlich mit dem Induktionsschritt vom Induktionsanfang auf das nächste zuerst einmal kommen können. Ein Baum mit 0 Knoten kann ich aber nicht so erweitern, dass ich danach dann doppelt so viele Blätter hätte.
So klar ist es ja auch erstmal nicht, dass irgendeine Zahl hoch 0 immer eine 1 ergibt. Wenn man mal von der Regel ausgeht, dass z. B. 2^n das Produkt aus n Zweien ist, dann kann man 2^0 so ja noch nicht ohne weiteres bestimmen. Letztlich ist es bei einer solchen Definition noch zwingend, dass der Exponent eine natürliche Zahl (ohne 0) ist. Erst wenn man das noch erweitert, kann man für den Exponenten reelle Zahlen verwenden.
Zitat:
Original von Ic3Cub3
Induktionsschritt:
T ist ein Baum der Höhe h
die Wurzel von T hat zwei Teilbäume als Söhne, die jeweils die Höhe h-1 haben
Diese Teilbäume haben eine Blätteranzahl von 2^(h-1)
Somit hat T 2*2^(h-1)=2^(h) Blätter.

Auch das würde ich anders machen. Du gehst ja quasi von einem größeren Baum aus und halbierst den dann. Das mag zwar letztlich auch funktionieren indem Du das Ergebnis dann quasi rumdrehst, aber da bin ich mir nicht ganz sicher.
Eigentlich musst Du ja von einem Baum mit Tiefe h (zuerst mit einem Knoten, also h=1, dann aber für alle folgenden) auf einen Baum mit Tiefe h+1 kommen.
Da an jedes Blatt des Baumes mit Tiefe h jeweils zwei neue Knoten angehängt werden, die dann zu den neuen Blättern werden, ist es klar, dass sich bei h -> h+1 auch die Blattzahl verdoppeln muss, also b -> 2*b.
Hier siehst Du vielleicht dann auch nochmal meine Bauchschmerzen mit Deinem Induktionsanfang: Wenn ich mit 0 Knoten anfange, dann kann ich an kein Blatt zwei weitere Blätter anhängen. Ich komme so nie mit meinem Induktionsschritt vom Induktionsanfang auf die nächste Baumtiefe.

Zitat:
Original von Ic3Cub3
Außerdem bin ich mir auch nicht sicher wie ich den Beweis formal korrekt aufschreiben soll...

Mit dem Formalen hatte ich auch immer meine Probleme... Vielleicht versuchen wir das gleich mal gemeinsam.

Gruß
Marco
06.08.2017 10:19 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 400
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo nochmal!

Ich glaube, ich habe einen Fehler gemacht: Dein Baum der Höhe 0 hat ja schon einen Knoten. Das entspricht ja gerade dann dem, was ich eigentlich machen wollte, nur dass ich anders zu Zählen angefangen habe.
Dann ist Dein Induktionsanfang doch richtig! Tut mir Leid wegen der Verwirrung!

Gruß
Marco
06.08.2017 10:45 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Ic3Cub3
Grünschnabel


Dabei seit: 05.08.2017
Beiträge: 6

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo Marco,

Vielen Dank für deine Antwort!

Zitat:
Auch das würde ich anders machen. Du gehst ja quasi von einem größeren Baum aus und halbierst den dann. Das mag zwar letztlich auch funktionieren indem Du das Ergebnis dann quasi rumdrehst, aber da bin ich mir nicht ganz sicher.
Eigentlich musst Du ja von einem Baum mit Tiefe h (zuerst mit einem Knoten, also h=1, dann aber für alle folgenden) auf einen Baum mit Tiefe h+1 kommen.
Da an jedes Blatt des Baumes mit Tiefe h jeweils zwei neue Knoten angehängt werden, die dann zu den neuen Blättern werden, ist es klar, dass sich bei h -> h+1 auch die Blattzahl verdoppeln muss, also b -> 2*b.
Hier siehst Du vielleicht dann auch nochmal meine Bauchschmerzen mit Deinem Induktionsanfang: Wenn ich mit 0 Knoten anfange, dann kann ich an kein Blatt zwei weitere Blätter anhängen. Ich komme so nie mit meinem Induktionsschritt vom Induktionsanfang auf die nächste Baumtiefe.


bei h=0 hat der Baum genau h^0=1 Knoten, was ich im IA gezeigt habe.
Ich beziehe mich auf deine Idee und gehe eine Ebene tiefer auf h+1.
Die Knoten verdoppeln sich, also habe ich 2*1=2 Blätter.
h+2<=>h=2: 2*2*1=2^2 Blätter
h+3<=>h=3: 2*2*2*1=2^3 Blätter
.
.
.

h: 2^h Blätter

--> ein vollständiger binärer Baum hat 2^h Blätter

Ist das was du meinst? Und könntest du mir bei der Formailtät helfen? :)

Vielen Dank im Voraus!
LG Ic3Cub3

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Ic3Cub3: 06.08.2017 16:01.

06.08.2017 16:00 Ic3Cub3 ist offline Beiträge von Ic3Cub3 suchen Nehmen Sie Ic3Cub3 in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 400
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo!

Also ich würde schreiben:

Induktionshypothese:
Sei h die Höhe eines vollständigen Binärbaums T und b die Anzahl seiner Blätter. Dann gilt
[latex]b(h) = 2^h[/latex]

Induktionsanfang:
Ein Baum mit Höhe 0 hat nur einen einzigen Wurzelknoten, der auch gleichzeitig das einzige Blatt ist.
Der Induktionsanfang
[latex]b(0) = 1 = 2^0[/latex]
ist also erfüllt.

Induktionsschritt:
Wenn man bei einem vollständigen Binärbaum seine Höhe h um eins erhöht, bekommt jedes bisherige Blatt zwei neue Kinder, die jeweils zu neuen Blättern werden. Die Anzahl der Blätter verdoppelt sich also.
[latex]b(h+1) = 2\cdot b(h) = 2\cdot 2^h = 2^{h+1}[/latex]
Beim zweiten Gleichheitszeichen hab ich die Induktionshypothese verwendet, indem ich b(h) durch 2^h ersetzt habe.

Gruß
Marco
07.08.2017 08:08 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Ic3Cub3
Grünschnabel


Dabei seit: 05.08.2017
Beiträge: 6

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo Marco,

vielen Dank für deine Antwort. Ist anschaulich und verständlich! Danke.

LG Ic3Cub3
07.08.2017 20:35 Ic3Cub3 ist offline Beiträge von Ic3Cub3 suchen Nehmen Sie Ic3Cub3 in Ihre Freundesliste auf
Ic3Cub3
Grünschnabel


Dabei seit: 05.08.2017
Beiträge: 6

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo nochmal,

ich habe da noch eine Frage. Sollte sich der Induktionsschritt nicht auf den Induktionsanfang beziehen, da falls man sich auf die Induktionshypothese bezieht und diese falsch ist man sozusagen in eine Schleife mit Fehlern gerät?

LG Ic3Cub3
07.08.2017 20:40 Ic3Cub3 ist offline Beiträge von Ic3Cub3 suchen Nehmen Sie Ic3Cub3 in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 400
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Hallo!

Nein, das ist schon richtig.

Die Idee ist, dass man im Induktionsschritt beweist: falls (angenommen) für h die Hypothese schon erfüllt wäre, beweise, dass sie für h+1 auch noch stimmt. Das allerdings allgemein für alle h ab dem Induktionsanfang. Damit hast Du ja viel mehr gezeigt, als nur den Schritt von h=0 auf h=1.
Umgekehrt ausgedrückt: mit dem Induktionsschritt hast Du auch das schon bewiesen, wie Du vom Induktionsanfang eins erhöhst. Du kannst ja einfach für h eine 0 einsetzen. Dann wäre b(0) laut Hypothese gerade 1 und ich zeige, wenn das tatsächlich der Fall ist, dann ist b(0+1) = 2.
Dass das für b(0) der Fall ist, zeige ich separat mit dem Induktionsanfang.
Jetzt kann ich meinen Induktionsschritt aber nochmal verwenden, ich hab ja b(1) = 2 schon bewiesen. Daraus kann ich dann auch b(2) = 4 zeigen und so weiter für jedes h. Hätte ich für meinen Induktionsschritt nur h = 0 verwendet, würde ich ja immer nur auf h = 1 kommen und nicht weiter bewiesen haben. Ich hab im Induktionsschritt bewiesen, dass für alle Schritt von h auf h +1 die Kette noch stimmt, Du hättest viel weniger bewiesen, nämlich nur für den ersten Schritt.

Gruß
Marco
08.08.2017 08:03 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Ic3Cub3
Grünschnabel


Dabei seit: 05.08.2017
Beiträge: 6

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Alles klar! Vielen Dank! :)
08.08.2017 17:58 Ic3Cub3 ist offline Beiträge von Ic3Cub3 suchen Nehmen Sie Ic3Cub3 in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Beweis Anzahl Blätter vollständiger Binärer Baum