PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Eigenschaften von Heaps... *netweiterkomm*


darph
2004-12-21, 09:46:17
:/

Hat ein Heap die Höhe h >= 0 so gilt für die Anzahl seiner Elemente :

2^h <= n <= 2^(h+1) - 1


Beweis durch Induktion:

Für h = 0 gibt es nur einen möglichen Heap: Der mit einem Root-Knoten ohne Children. n = 1.
also 2^0 <= 1 <=2^(0+1) - 1
entspricht 1 <= 1 <= 2-1
Stimmt.

Für h = 1 gibt es zwei mögliche Heaps: Der Root-Knoten mit 1 Child, der Root-Knoten mit 2 Children. also n = 2 oder 3.
also 2^1 <= 2;3 <= 2^(1+1) - 1
entspricht 2 <= 2;3 <= 4-1
Stimmt.

Für kleine h Stimmt das also.

Für beliebige h, also auch für h + 1:

Der Heap besteht aus einer Wurzel W (mit einem Element, dem Root) und zwei sub-Heaps, H-l und H-r (links und recht). Wegen der balancierenden Eigenschaften kann man davon ausgehen, daß H-l immer vollständig gefüllt ist, also die Höhe h hat. H-r hat dann ebenfalls die Höhe h (wenn der ganze Heap vollständig gefüllt ist) oder h-1. Hier muß man also eine Fallunterscheidung machen.

Jetzt komm ich nicht weiter.

Der Heap hat also die Höhe von H-l + W. Und da die Höhe von W = 1 ist, wäre das ganze ja rekursiv bewiesen, da man den Heap ja in immer kleinere Sub.Heaps aufteilen kann.

Aber wie mach ich den Induktionsbeweis weiter?

darph
2004-12-21, 10:01:00
Hm. Gesetzt den Fall, daß der rechte Teilbaum ebenfalls die Höhe h hat...


Da der linke Teilbaum vollständig gefüllt ist, ist die Anzahl der Elemente in ihm n = 2^(h+1) - 1 (der rechte Teil unserer Ungleichung).

der rechte Teilbaum hat n Elemente mit 2^h <= n <= 2^(h+1) - 1

also ist n = n-links + n-rechts + 1 (der Root).

2^(h+1) - 1 + 2^h + 1 <= n <= 2^(h+1) - 1 + 2^(h+1) - 1. + 1
= 2^h + 2^(h+1) <= n <= 2^(h+1) + 2^(h+1) - 1
= 2^h + 2^(h+1) <= n <= 2^(h+2) - 1


Korrekt?