Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Binäre Suchbäume
Einleitung Binäre Suchbäume
[Bearbeiten]Auf dieser Seite werden die binären Suchbäume behandelt. Er ermöglicht einen schneller Zugriff auf Daten mit dem Aufwand O(log n) unter geeigneten Voraussetzungen. Des weiteren ermöglicht er effiziente Sortierung von Daten, durch Heapsort und effiziente Warteschlangen. Der binäre Suchbaum dient als Datenstruktur für kontextfreie Sprachen. In der Computergrafik sind Szenengraphen oft (Beinahe-)Bäume. Bei Informationssysteme dienen binäre Suchbäume zur Datenindizierung und Anfrageoptimierung.
Operationen
[Bearbeiten]Auf Suchbäumen können die Operationen Suchen von Elementen, Einfügen von Elementen und Entfernen von Elementen angewandt werden, wobei letztere zwei voraussetzen, dass die Ordnung der Schlüssel erhalten bleibt.
Literatur
[Bearbeiten]Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14 zu finden.