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.
Ich hatte deswegen auch erst überlegt, einfach ein Array zu nehmen. Aber dann kam der Perfektionist in mir wieder durch und dachte sich, es wäre doch schön, wenn trotzdem garantiert wäre, dass die asymptotische Laufzeit nicht aus dem Ruder läuft. Hab mir dann erst überlegt, ob man das Array vielleicht irgendwie erweitern könnte, aber habe dann nach einer Weile gemerkt, dass ich eigentlich gerade Bäume neu erfinde... und dann habe gedacht, okay, dann kann ich auch gleich die richtigen Dinger implementieren. Dachte anfangs auch nicht, dass das so aus dem Ruder läuft, denn auf den Folien sah das nach einem sehr einfachen Konzept aus. Ist es ja eigentlich auch. Aber wenn man es dann implementiert, tun sich doch plötzlich Sonderfälle auf, die man durch bloßes Draufschauen niemals gesehen hätte... und auf einmal ist der Code viel länger als man gedacht hätte.
Zum Glück sind bei Pascal die Kompilierzeiten kurz, da kann man sich solche „Ungetüme“ wenigstens noch leisten...