3.3 best case von insert() bei AVL-Trees
Dirk Lehmann
heute im Tutorium wurden ja in Aufgabe 3.3 unter anderem die Komplexitäten
von Bäumen besprochen. Da kam auch die Angabe für den best case bei
AVL-Bäumen mit O(1) vor. Allerdings war ich erstaunt, als irgendwann gesagt
wurde, dass diese Komplexität auch für insert() gilt. Mein Tutor konnte mich
davon nicht überzeugen, deswegen wollte ich hier nochmal nachfragen:
Standpunkt Tutor:
Im besten Fall ist der AVL-Baum leer und man braucht einen Schritt um ein
Element einzufügen.
Mein Standpunkt:
Im besten Fall hat der AVL Baum eine maximale Unausgewogenheit (d.h. für
jeden Teilbaum gilt, dass er Quasivoll ist) und es wird ein Element in ein
Blatt mit der kürzesten Pfadlänge eingefügt. Das wäre ein Aufwand von
A=0.44*log_2(n+1), glaube ich. Somit wäre A \in O(log_2(n)). Also ist
insert() auch im best case von n abhängig. Nach der Erklärung meines Tutors
wurde im best case n=0 gesetzt! Darf man das?
Im Web habe ich dazu nichts auf seriösen Seiten gefunden. Also, was haltet
ihr davon?
CU Dirk.
Dirk Lehmann
das 0pf4
fall eines baumes ( oder auch generell bei listen ) is ein leerer baum
( leere liste). in diesem fall muss das entsprechende element nur
eingefügt werden, ohne das ein vergleich nötig wäre.
dass ein leerer baum auch die bedingungen erfüllt, lässt sich sehr
leicht zeigen
Dirk Lehmann
news:1133180222.1...@g43g2000cwa.googlegroups.com...
> im best case geht man immer von einfachstem fall aus .. der einfachste
> fall eines baumes ( oder auch generell bei listen ) is ein leerer baum
> ( leere liste). in diesem fall muss das entsprechende element nur
> eingefügt werden, ohne das ein vergleich nötig wäre.
Aber O bzw. Theata ist doch eine Abbildung von n --> O(n)! Und was du jetzt
behauptest ist: Best case ist O(n=0). Und das ist das, was ich nicht
einsehen will. Tut mir leid, aber diese Argumentation lasse ich nicht
gelten.
Ich weiß zwar, dass best case vielleicht nicht einer Diskusion würdig ist,
aber nach dem derzeitigen Stand würde ich in einer Klausur zu diesem Punkt
nicht O(1) hinschreiben; und wenn mir dabei ein Punkt flöten geht.
CU Dirk.
Günther Brammer
> Aber O bzw. Theata ist doch eine Abbildung von n --> O(n)! Und was du jetzt
> behauptest ist: Best case ist O(n=0). Und das ist das, was ich nicht
> einsehen will. Tut mir leid, aber diese Argumentation lasse ich nicht
> gelten.
Der beste Fall für n ist 0, der beste Fall für Aufwand in
Abhängigkeit von n ist ein maximal unausgewogener Baum mit
einzufügendem Element an einem kurzen Ast. Das widerspricht sich doch
nicht. Man muss nur drauf achten, was gefragt ist.
Günther
Dirk Lehmann
news:pan.2005.11.29....@gmx.de...
Hmmm, na gut... Ich nehme es mal einfach so hin.
CU Dirk.
Dirk Lehmann
news:dm76ig$jac$03$1...@news.t-online.com...
>
> Mein Standpunkt:
> Im besten Fall hat der AVL Baum eine maximale Unausgewogenheit (d.h. für
> jeden Teilbaum gilt, dass er Quasivoll ist) und es wird ein Element in ein
> Blatt mit der kürzesten Pfadlänge eingefügt. Das wäre ein Aufwand von
> A=0.44*log_2(n+1), glaube ich. Somit wäre A \in O(log_2(n)). Also ist
> insert() auch im best case von n abhängig. Nach der Erklärung meines
> Tutors
> wurde im best case n=0 gesetzt! Darf man das?
>
Jou, ich mal wieder ;)
also, um den Thread jetzt abzuschließen; für alle gespannt wartenden Leser
zu diesem hoch spannenden Thema :P
Die Aussage zu O(1) wurde heute im Tutorium revidiert mit der Begründung:
Die Abschätzungen gelten für n --> unendlich. Somit besteht eine
Abhängigkeit von n, und die ist O(log(n)) ...
*JOUPIIE*
CU Dirk.