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.