Cherrycoke
Mitglied
Hallo,
als Hausaufgabe soll ich eine Funktion schreiben, die eine maximale Blattiefe tmax eines Blattes im AVL-Baum bestimmt. Diese Funktion soll allerdings den Aufwand O(tmax) haben. Leider habe ich dummerweise noch nicht so ganz die Aufwandsgeschichte durchschaut.
Rein intuitiv würde ich die Funktion rekursiv für den linken Teilbaum und den rechten Teilbaum (von der Wurzel ausgehend) aufrufen und bei jedem Aufruf um +1 erhöhen. Danach würde ich das Maximum der beiden Teilbäume vergleichen.
Wie gesagt, ich verstehe noch nicht so recht, was das mit dem Aufwand bedeutet. Darf ich nur tmax Vergleiche benutzen, oder wie ist das zu verstehen? Sagen wir mal ich habe einen AVL-Baum der Höhe 3. Dann hat die Funktion dazu den Aufwand O(3). Was bedeutet das nun für die Funktion?
Danke!
als Hausaufgabe soll ich eine Funktion schreiben, die eine maximale Blattiefe tmax eines Blattes im AVL-Baum bestimmt. Diese Funktion soll allerdings den Aufwand O(tmax) haben. Leider habe ich dummerweise noch nicht so ganz die Aufwandsgeschichte durchschaut.
Rein intuitiv würde ich die Funktion rekursiv für den linken Teilbaum und den rechten Teilbaum (von der Wurzel ausgehend) aufrufen und bei jedem Aufruf um +1 erhöhen. Danach würde ich das Maximum der beiden Teilbäume vergleichen.
Wie gesagt, ich verstehe noch nicht so recht, was das mit dem Aufwand bedeutet. Darf ich nur tmax Vergleiche benutzen, oder wie ist das zu verstehen? Sagen wir mal ich habe einen AVL-Baum der Höhe 3. Dann hat die Funktion dazu den Aufwand O(3). Was bedeutet das nun für die Funktion?
Danke!
