Berchnung mit einem Heap?

[Hans W. (Gast)]

Hi Leute!

Ich hab hier eine Aufgabe:

Zeigen Sie folgende Aussage, dass ein Heap mit n-Elementen hat höchstens 
{n/(2^(h+1))} (die geschweiften Klammern sollen Gaußklammern sein, die 
nach oben aufrunden!) viele Knoten der Höhe h hat.


Ich hab hierzu natürlich schon Überlegungen angestellt:

Ich hab mir in dieser Zeichnung 
(http://s7.directupload.net/file/d/2874/qh39mqm9_jpg.htm#) erst mal 
einen Heap aufgemalt. Dieser Heap hat 7 Elemente, 3 Zeilen und eine Höhe 
von 2.

Wenn ich diese Werte jetzt mal in die in der Aufgabenstellung gegebene 
Formel einsetze, dann komm ich auf 1 (gerundet). Das würde ja nun 
bedeuten, dass dieser Heap höchstens (!) 1 Knoten pro Höhe h hat. Aber: 
Wenn ich nun mal in die Höhe 1 des Heaps schaue, dann hat der Heap doch 
2 Knöten, nämlich 5 und 7, oder?

Irgendwie verstehe ich das noch nicht so ganz. Und vor allem wie zeigt 
man nun, dass diese gegebene Formel richtig ist?

[Florian (Gast)]

Hans Wurst schrieb:
> Wenn ich diese Werte jetzt mal in die in der Aufgabenstellung gegebene
> Formel einsetze, dann komm ich auf 1 (gerundet).

Dann solltest du das einfach nochmal nachrechnen.

Ich bin zuuversichtlich, daß du das schaffst! Auch wenns immerhin im 
Zahlenraum bis zehn ist!

[Hans W. (Gast)]

Hey, so hab ich gerechnet:

Aus dem Heap resultiert: n=7; k=3; h=2;

{n/(2^(h+1))}={7/(2^(2+1))}={7/(2^3)}={7/8}=1 Knoten


Ich weiß nicht, wo da jetzt der Fehler sein soll! Kannst du evtl. noch 
genauer drauf eingehen?

[D. I. (Gast)]

passt doch mit 1 Knoten.

Die Wurzel ist der einzige Knoten mit Höhe 2

[Hans W. (Gast)]

Ah, jetzt verstehe ich!!!

Man "zählt" quasi die Höhe von unten nach oben? Die Zeile mit den 4 
Blättern (1,2,7,2) hat also Höhe 0, die Zeile mit den 2 (Teil-)Knöten 
(5,7) hat dann die Höhe 1 und die Wurzel (23) ganz oben hat Höhe 2? Ist 
das so richtig?

Wenn das so stimmt, dann leuchtet natürlich das Ergebnis, welche meine 
Formel ausspuckt, ein.

In der Aufgabenstellung heißt es aber nun weiter, dass ich diese Formel 
"zeigen" soll. Wie macht man das jetzt?

Ich denke, man muss den Weg über eine Ungleichung nehmen. Denn, man muss 
ja diese Gauß-Rundungsklammern irgendwie zum Ausdruck bringen...

Könnt ihr mir da ein bisschen helfen?

[D. I. (Gast)]

Die Höhe eines Knoten in einem Binärbaum ergibt sich rekursiv aus

max(höhe(linker Baum), höhe(rechter Baum))+1

und es ist eine übliche Definition Blättern die Höhe 0 zu geben, bzw. 
dem leeren Baum -1

Um deine Formel zu zeigen musst du einen Beweis führen.

[Hans W. (Gast)]

D. I. schrieb:
> Die Höhe eines Knoten in einem Binärbaum ergibt sich rekursiv aus
>
> max(höhe(linker Baum), höhe(rechter Baum))+1

In meiner Vorlesung hab ich gelernt, dass sich die eine Höhe eines 
Baumes so berechnen lässt: h={lb(n)} (die geschweiften Klammerns sollen 
die Gauß-Abrundungsklammern sein!)

In meinem Beispiel Baum würde doch dann das so lauten:

max(lb(nl), lb(nr))+1





> und es ist eine übliche Definition Blättern die Höhe 0 zu geben, bzw.
> dem leeren Baum -1

Danke, das hab ich in der Tat nicht gewusst, bzw. ist bisher noch 
nirgends aufgetaucht.




> Um deine Formel zu zeigen musst du einen Beweis führen.

Was meinst du genau mit "Beweis"? Induktiv?

[Arc N. (arc)]

Hans Wurst schrieb:
>> Um deine Formel zu zeigen musst du einen Beweis führen.
>
> Was meinst du genau mit "Beweis"? Induktiv?

Richtig.
Stichwort: Vollständige Induktion.
Anfang: h=0, (d.h. entweder ist der Baum leer oder es ist die Wurzel, 
die keine(leere) Teilbäume hat)
Annahme: ...
Schluss: n -> n + 1

[D. I. (Gast)]

Hans Wurst schrieb:
> D. I. schrieb:
>> Die Höhe eines Knoten in einem Binärbaum ergibt sich rekursiv aus
>>
>> max(höhe(linker Baum), höhe(rechter Baum))+1
>
> In meiner Vorlesung hab ich gelernt, dass sich die eine Höhe eines
> Baumes so berechnen lässt: h={lb(n)} (die geschweiften Klammerns sollen
> die Gauß-Abrundungsklammern sein!)

Das gilt für einen vollbesetzten Binärbaum.

>
> In meinem Beispiel Baum würde doch dann das so lauten:
>
> max(lb(nl), lb(nr))+1

Nein. Meine Formel ist eine rekursive Herleitung zur Bestimmung der Höhe 
eines Knotens in einem beliebigen Binärbaum