bäume < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:17 Sa 09.06.2007 | | Autor: | AriR |
| Aufgabe | Beweisen Sie: In einem vollständigen Binärbaum der Höhe h mit n = [mm] 2^{h+1}−1 [/mm] Knoten hat die
Summe der Höhen aller Knoten den Wert [mm] s_h [/mm] = n − h − 1 |
hey leute,
irgendwie komme ich mit der aufgabe nicht zurecht.
hab mir selber überlegt, dass die formel rekursiv so aussehen müsste
[mm] s_{h+1}=2*s_h+(h+1)
[/mm]
aber damit kann man für den induktionsbeweis acuh nicht viel anfangen, da dies wieder nur eine behauptung ist.
mein problem ist folgendes:
man muss die induktion ja über n oder h laufen lassen, und könnte dann mit hilfe der beziehung über n und h die in [mm] n=2^{h+1}-1 [/mm] gegeben ist, das n oder h aus [mm] s_h [/mm] bekommen.
der induktionsanfang ist dann auch noch klar nur was muss ich im induktionsschritt machen?
ich hab da ein [mm] s_{h+1} [/mm] stehen links vom gleichheitszeichen und rechts wieder was. was für eine gleichheit muss ich genau zeigen dann? ich hab ja für [mm] s_{h+1} [/mm] keinen konkreten wert.
wisst ihr ca was ich meine? wenn ja, könnt ihr mir bitte einen tip geben?
|
|
| |
|
Hallo,
was ein Binärbaum ist, weiß ich "irgendwie intuitiv".
Wenn ich dieses Wissen nutze, stelle ich fest, daß es nicht stimmt, daß
$ [mm] s_h [/mm] $ = [mm] n_h [/mm] − h − 1 ist.
Nehmen wir einen Baum der Höhe h=2. Er hat [mm] n_2=2^3-1=7 [/mm] Knoten.
Die Summe der Höhen aller Knoten [mm] s_2=0*2^0+1*2^1+2*2^2=10, [/mm] jedoch ist [mm] n_2 [/mm] − 2 − 1=7-2-1=4.
Und weil das so ist, nämlich die Angabe für [mm] s_h [/mm] verkehrt, kann die Induktion nicht klappen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:01 Sa 09.06.2007 | | Autor: | AriR |
die haben die höhe genau andersrum definiert :(
die blätter haben die höhe 0 und die wurzel hat die volle höhe.
dann passt das wieder
|
|
|
| |
|
> die haben die höhe genau andersrum definiert :(
>
> die blätter haben die höhe 0 und die wurzel hat die volle
> höhe.
Dann drehe ich meinen Zettel um und denke neu - obgleich ich's dämlich finde.
Wissen die nicht, daß Bäume in den Himmel wachsen. Nie draußen gewesen, was?
Gruß v. Angela
|
|
|
| |
|
Hallo,
na, wenn das so ist, dann stimmt's.
Und Du bist mit Deiner Überlegung
> $ [mm] s_{h+1}=2\cdot{}s_h+(h+1) [/mm] $
völlig richtig.
Natürlich mußt Du das beweisen. Was ist ein Beweis? Eine hieb- und stichfeste Begründung.
Induktionsanfang hast Du sicher.
Induktionsschluß:
Zu zeigen ist [mm] s_{h+1}=n_{h+1}-(h+1)-1.
[/mm]
Du mußt nun begründen, warum [mm] s_{h+1}=2\cdot{}s_h+(h+1) [/mm] gilt.
Das ist eine kleine Induktion in der Induktion (oder Du zeigst es als Vorüberlegung):
Die Behauptung [mm] s_{h}=2\cdot{}s_{h-1}+h [/mm] gilt stimmt für h=1.
Induktionsschluß:
Ein Binärbaum der Höhe h+1 besteht aus zwei Binärbäumen der Höhe h, welche durch die Wurzel in der Höhe h+1 verbunden werden. [Möglicherweise drücke ich mich nicht mathematisch richtig aus, zupf es ggf. zurecht.]
Daher ergibt sich [mm] s_{h+1} [/mm] zu [mm] s_{h+1}=2\cdot{}s_h+(h+1)*1=2\cdot{}s_h+(h+1).
[/mm]
Das kannst Du dann weiterverwenden:
[mm] s_{h+1}=2\cdot{}s_h+(h+1)=2*(Induktionsvoraussetzung)+(h+1).
[/mm]
So kommst Du zum Ziel.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:45 Sa 09.06.2007 | | Autor: | AriR |
ich versuchs mal :)
vielen dank mal wieder für die dauerbetreuung +g+
lieben gruß
|
|
|
|
