Ich würde noch vergleichen, wie sich die Strukturen bei kleineren Datenmengen verhalten. Hier macht sich der generelle Overhead stärker bemerkbar. Bei sehr kleinen Listen ist ein einfaches sortiertes Array oft schneller als ein Baum, weil eigentlich kein Overhead vorhanden ist.
Man muss wirklich aufpassen ob und wann man diese 'Ungetüme' (300+ Zeilen für eine 'einfache Liste' ist schon happig) verwenden sollte und wann nicht.
Alzaimar hat ja
hier einen ganz netten Vergleich geschrieben, der das Verhalten bei kleineren Datenmengen analysiert, da kommt sogar der AVL-Baum und die Skplist vor. Allerdings ist dort die Skiplist viel schneller als der AVL-Baum. Vielleicht, weil es auch viel weniger Daten sind(?)