Kurze Zwischenfrage: Müssen die Elemente eigentlich sortiert sein? Braucht man doch gar nicht so häufig.
Nunja, Einfügen in sortierter Reihenfolge ist eben je nach Containern-Implementierung gern mal 3x so schnell
wie Einfügen in chaotischer Reihenfolge.
Dann kennst Du aber Dictionaries schlecht. Die sind O(1), im Gegensatz zu den hier vorgestellten Strukturen, deren Einfügeverhalten vom Aufwand O(log n) ist. Auch Suchen, Löschen etc. ist bei Dictionaries O(1), würde also alle hier vorgestellten Strukturen um *Längen* schlagen. Es ist übrigens -gut programmiert- vollkommen egal, ob man 1000 oder 100.000.000.000 Elemente in einer Dictionary vorhält (solange der
RAM das aushält). Der Aufwand ist immer gleich, die Teile sind also immer gleich schnell. Ein Baum wächst und somit wird das Laufzeitverhalten auch immer schlechter, ist zwar sublinear, also log n, aber immer noch schlechter als gar keine Verlangsamung.
Nebenbei kannst Du hier keine Faktoren angeben, denn z.B. das Einfügen in eine sortierte Liste ist (ggü einer unsortierten Liste) nicht gerne mal 3x so schnell, sondern -je nach Anzahl- auch ruhig mal 10000000000x so schnell.
Damit kann man dem Container eine Lieblings-Reihenfolge einprogrammieren,
die dann schneller funktioniert.
Wenn man den Container auch noch an die speziellen Bedürfnisse anpassen muss, taugt so ein Container ja nur bedingt.
Die Frage lautet also: Wozu muss die Liste sortiert sein? Der Namenlose hat den B+-Baum im Rahmen einer Lehrveranstaltung Programmiert (klasse), aber im Allgemeinen haben diese Strukturen keine sonderliche Verbreitung, weil man eben nicht sonderlich oft sortierte Listen benötigt.
Ach, wurde ein (binomial) Heap schon probiert? Müsste ich mal raussuchen...