Hat noch keiner einen AVL-Baum ausprobiert?
Der ist beim Einfügen und beim Suchen recht schnell.
Ich habe zwar keinen AVL-Baum getestet, aber ich habe mal eine Zeigerliste gegen TStringlist mit 1.000.000 20stelligen Zufallsstrings antreten lassen (unsortiert) und dabei in den Listen den vorletzten String gesucht. Die zeigerverkettete Liste ist rund sechsmal schneller.
Das wundert mich ehrlich gesagt. Linked-Lists sollten bei sequenzieller Suche in etwa gleich schnell sein wie ein Array (bzw. eine intern als Array implementierte List).