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?
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?