(a,b) Bäume versus Binäre Suche

[Cauchy]

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!

[Romeo]

Hi!

Das Problem bei der Sache ist denke ich, dass du keinen O(1)-wahlfreien Zugriff hast. Wenn du deinen Bereich eingegrenzt hast, dann musst du ja erst zum entsprechenden Glied in der Liste laufen. Das geht nicht wie beim Array direkt über den Index, sondern du musst eben "zählen" wie viele Schritte du schon gemacht hast.

Ich kann das jetzt leider nicht formal beweisen, aber wenn das Erreichen des mittleren Elements O(n/2) Zeit braucht, dann braucht das nächste O(n/4) usw. Das gibt grob gepeilt einen Gesamtaufwand von O(n) (wegen der "-Summe).

Die Idee hört sich zwar toll an, aber ich fürchte, das wird wohl nicht funktionieren.
Oder habe ich deine Idee jetzt gerade missverstanden?

Grüße
Roland

[Cauchy]

Edit:
Um auf das mittlere Element zuzugreifen, muss man ja die ganze Liste bzw. die halbe traversieren! Das ist es!
Vielen Dank Wieder was gelernt!

Grüße,
Cauchy!