Eigenschaften von bestimmten Datenstrukturen
Von: , Frage gestellt am Mi, 5. Dez 2001
Hallo,
ich hätte mal eine Frage zu Heaps und AVL Bäumen.
Folgende Aussagen sollen mit Ja oder Nein beantwortet werde:
In einem Heap mit n Elementen kann das k-kleinste Element in O(log[2](k)) Zeit gefunden werden.
Also erstelle ich mal einen Heap als Beispiel:=[40,33,20,7,3,8,1]. Ich suche das 4-kleinste Element. Der Heap hat die Höhe 2(Wurzel hat die Höhe 0). Das 4-kleinste Element ist die 8 und die 8 ist in einem Heap ein Blatt. Also müssen 3 Vergleiche gemacht werden um die 4 zu finden. Das das ist aber nicht O(log[2](4)).Also ist die Antwort zu verneinen. Oder vertue ich mich da mit der Konstante in der O-Notation?
Ein AVL-Baum mit n Knoten hat im Durchschnitt O(log[2](n)) Blätter.
Diese Aussage ist ebenfalls falsch. Weil z.B. ein AVL-Baum mit 8 Knoten 4 Blätter hat. Nach der Aussage müsste der Baum höchstens 3 Blätter haben.
Hoffe, dass mir das jemand bestätigen kann.
Felix