3. Einfügen, Suchen, Löschen

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.