Berchnung mit einem Heap?

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!

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?

passt doch mit 1 Knoten.

Die Wurzel ist der einzige Knoten mit Höhe 2

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?

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.

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?

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