4. Einfügen, Suchen, Löschen

Das ganze Kapitel 4 ist wörtlich aus der Vorlesung Theoretische Informatik übernommen. Wir werden es daher im Herbst 2023 überspringen. Ich habe es dennoch in das Vorlesungsskript übernommen, weil langfristig nicht klar ist, ob dieses Thema in Theoretische Informatik oder vielleicht nicht doch in Algorithmen und Komplexität gehört.

In den letzten beiden Kapiteln haben wir gelernt, wie man (2) Datenmengen effizient sortiert und (1) mittels binärer Suche effizient in ihnen sucht. Dies ist alles wunderbar, solange wir in unserer Anwendung eine Schreibphase haben, in welcher die Daten angehäuft werden, gefolgt von einer Lesephase, in welcher sich die Datenmenge nicht mehr ändert; in diesem Falle können wir nach Abschluss der Schreibphase sortieren. Komplizierter wird es, wenn Schreib- und Leseoperationen wild gemischt sind, in anderen Worten also die Datenmenge sich während der Nutzung weiter ändern kann. Dann brauchen wir dynamische Datenstrukturen.