Der Testcode ist ziemlich hässlich und mit heißer Nadel gestrickt, aber gut:
Eben. Gut
Du testest mit Sonderbedingungen (aufsteigend, absteigend einfügen). Da wirst Du -zumindest im AVL und RB- eine Worst Case erwischen. Die müssen ja beinahe bei jedem Einfügen ausbalanciert werden.
Hmmm... oder gleicht sich das aus?
Teste doch mal zusätzlich mit Random-Werten. Achtung: Die Skiplist ist nicht ohne weiteres geeignet zur Aufnahme identischer Werte, müsstest du prüfen. Alternativ erstellst Du dir eine Liste mit 1Mio Einträgen, mischst die mit Fisher-Yates und fügst dann die Werte ein. Ist ja auch Random.
Ich teste jedenfalls immer so.