Andere Algorithmen auf Binärbäumen

Worum ging's nochmal?

Wir haben jetzt jede Menge Theorie gemacht und eine tolle Methode gefunden, um einzelne Datenobjekte effektiv zu finden, gesetzt den Fall wir haben hinreichend viel Arbeit ins Preprocessing gesteckt.

Aber wie sind wir überhaupt nochmal auf die Idee gekommen? Wir haben ganz am Anfang mal über unsere Hans-Wurst Schule gesprochen. Wir können dieser Schule jetzt mit ein bisschen Arbeit und ihrer Datenbank ein einfaches Tool geben, um ihre Schüler schnell in der Datenbank zu finden.

Aber was machen wir, wenn das nächste Jahr anfängt und die Schule neue Schüler kriegt? Was machen wir, wenn mitten im Schuljahr ein Schüler dazukommt oder aufhört?

Wir können natürlich jedesmal zur Schule laufen und alles von vorne laufen lassen, aber geht das nicht auch effizienter? Können wir den Lehrern nicht gleich auch einen Algorithmus zum Einfügen und Löschen von Schülern mitgeben? Möglichst einen, bei dem unser Baum nicht wieder von Grund auf aus einer Liste aufgebaut werden muss?

Wir wollen im Folgenden Algorithmen besprechen, die genau das für uns tun. Falls Du es dir zutraust, kannst Du vorher gerne versuchen, die entsprechenden Algorithmen selbst zu entwerfen. Wichtig ist dabei, dass Du erstmal nur auf die Binärbaumdefinition achtest und noch nicht auf Höhenbalance.