(a,b) Bäume versus Binäre Suche
Verfasst: So 2. Aug 2009, 21:10
Hallo alle zusammen!
Noch eine Frage bezüglich binärer Suche in einer sortierten Liste.
Warum baut man sich einen komplizierten (a,b) Baum auf, wenn man nicht einfach eine sortiere Liste
benutzt, dort einfach jede Operation mit binärer Suche kombiniert? Dadruch garantiert man O(log n) Laufzeit.
Wenn man ein Element einfügen will ruft man einfach, locate(k) auf. Verfolgt das ganze mit binärer Suche
und fügt das ganze an die entsprechende Stelle ein. Das einfügen dauert dann O( log n), da man lediglich
2 Zeiger ändern muss plus die binäre Suche. (Vorausgesetzt die Liste ist doppeltverkettetet)
Übserseh ich hier irgendwas?
Vielen Dank!
Noch eine Frage bezüglich binärer Suche in einer sortierten Liste.
Warum baut man sich einen komplizierten (a,b) Baum auf, wenn man nicht einfach eine sortiere Liste
benutzt, dort einfach jede Operation mit binärer Suche kombiniert? Dadruch garantiert man O(log n) Laufzeit.
Wenn man ein Element einfügen will ruft man einfach, locate(k) auf. Verfolgt das ganze mit binärer Suche
und fügt das ganze an die entsprechende Stelle ein. Das einfügen dauert dann O( log n), da man lediglich
2 Zeiger ändern muss plus die binäre Suche. (Vorausgesetzt die Liste ist doppeltverkettetet)
Übserseh ich hier irgendwas?
Vielen Dank!