#1 30. August 2012 Höhe eines Heaps bzw baums die Höhe eines binären heaps ist ja Log2(n) und die Höhe des k-Heaps ist Logk(n) jedoch komme ich bei der herleitung nicht auf das ergebnis. weiss jemand wir ich darauf komme? mfg allstar + Multi-Zitat Zitieren
#2 3. September 2012 Zuletzt bearbeitet: 3. September 2012 AW: Höhe eines Heaps bzw baums Ich weiß nicht, wieso die höhe eines Baums mit einer Log-Funktion berechenbar sein sollte. Du kannst den Aufwand für Such-, Einfüge-, und Löschfunktionen mit einer Logarithmusfunktion abschätzen, aber die Höhe eines Baums ist definiert als natürliche Zahl(die Länge des längsten Pfades von der Wurzel zum Blatt). Vielleicht verstehe ich einfach nur deine Frage nicht... mehr Kontext oder eine Umformulierung der Frage wäre nett und in deinem eigenen Interesse. EDIT: Ein Heap ist entweder links-, oder rechtsbündig aufgefüllt. Bei einem linksbündigen kannst du immer den linken childnode entlanggehen. Der letzte Knoten hat dann automatisch den längsten Abstand zum rootnode. Du kannst dir für diesen Aufwand eine Zahlenreihe erstellen: für k = 2: n=1 Aufwand = 1; n=2 Aufwand = 2; n=3 Aufwand = 2; n=4 Aufwand = 3; usw. Für diese Zahlenfolge gibt es sicher eine Summenformel, um den Aufwand für n-> unendl. abzuschätzen. Der Beweis dafür findet sich sicher irgendwo in deinen Unterlagen/Literatur. Wofür brauchst du das: diese Vorraussetzungen helfen dir, mittels Vollst.Induktion zu beweisen, dass log k(n) gilt. Du weißt, dass k=2 gilt (dank deiner summenformel, deren Beweis du hoffentlich findest) und kannst dann k+1 beweisen. Sollte k=2 als vorraussetzung nicht ausreichen, dann kannst du noch k=1 (eine Liste) betrachten. + Multi-Zitat Zitieren