Würde sich ein binärer Suchbaum anbieten? Gibt es nutzbare Implementierungen (@Namenloser, Deine inzwischen?)?
Ich habe das Projekt, wofür ich es brauchte, mehr oder weniger abgebrochen, und seitdem meine Implementierung nicht weiterverfolgt. Prinzipiell funktioniert sie, wirkt aber noch etwas unfertig. Ich wollte den Code eigentlich noch auf Generics umschreiben, wollte aber auch die Unterstützung für ältere Compiler ohne Generics nicht verlieren. Es stellte sich dann aber leider heraus, dass es selbst mit den cleversten Include-Hacks, die mir einfallen, wohl unmöglich ist, beides gleichzeitig zu supporten, ohne den Code zu duplizieren. Ungefähr da habe ich dann die Lust verloren
Aber wie dem auch sei, ich schmeiße es jetzt einfach mal so wie es ist auf Github:
https://github.com/Isopod/ABTrees. Wie gesagt, ich sehe es nicht als fertig an und übernehme keine Gewährleistung, aber vielleicht kann ja jemand was damit anfangen.
In src/abtrees kann man sehen, wie man sich einen eigenen Baum definiert. Wenn du Strings als Keys verwenden willst, müsstest du dann aber wohl TABKey als record definieren und den Vergleichsoperator überladen. Man kann natürlich mehrere Arten von Bäumen in einem Projekt haben, also z.B. einen, der Integers als Keys verwendet, einen, der Strings als Keys verwendet etc., man muss dann nur für jeden eine neue
Unit anlegen.
Wichtig zu beachten:
- Ein Key muss eindeutig sein, er darf nicht mehrfach im Baum vorkommen. Das heißt natürlich nicht, dass nicht mehrere Leute „Hans“ mit Vornamen heißen dürfen, man muss sich nur überlegen, wie man den Key definiert. Man könnte z.B. zu dem Record noch eine eindeutige ID hinzufügen, die man vergleicht, wenn die Vornamen gleich sind.
- Seek gibt immer den Eintrag zurück, der am nächsten am gesuchten Key liegt und dessen Key
kleiner oder gleich dem gesuchten Key ist. Es ist also kein "Find". Wenn die Einträge im Baum 1, 2, 3, 5, 6 lauten, dann gibt Seek(4) den Eintrag 3 zurück. Wenn man einen ganz bestimmten Eintrag sucht, muss man daher hinterher noch prüfen, ob der Key wirklich gleich ist.
Oder ist eine binäre Suche in einer Liste ohnehin fast gleich schnell?
Die Suche an sich ist schnell, aber wenn du viele Einträge löscht oder hinzufügst, könnte es langsam werden, da ja im Schnitt jedes mal die halbe Liste umkopiert wird.