Kurs:Algorithmen und Datenstrukturen/Kapitel 4

Dieses Kapitel gehört zum Kurs Algorithmen und Datenstrukturen des Fachbereichs Informatik.

Bäume

In diesem Kapitel geht es um eine der wichtigsten Datenstrukturen der Informatik - Bäume. Mit Bäumen ist es möglich Daten zu strukturieren und mit logischen Methoden auch wieder zu finden. Eine bekannte Anwendung für Bäume ist zum Beispiel ein Dateisystem. Dateisysteme weisen meist eine baumartige Struktur auf.

Binäre Suchbäume

Binäre Suchbäume sind eine knotenbasierte, baumartige, rekursive Datenstruktur mit den folgenden Eigenschaften:

• das linke Unterelement ist kleiner als das Elternelement (Knoten)
• das rechte Unterelement ist größer als das Elternelement (Knoten)
• sowohl der rechte als auch der linke Unterbaum

Daraus folgt, dass jeder Knoten einen eindeutigen Schlüssel hat bzw. darstellt.

Optimale und degenerierte Suchbäume

• Erklären, wie es zur degeneration kommen kann
• Erklären, wann ein Baum optimal ist
• Wieviele optimale Einfügereihenfolgen gibt es?

AVL-Bäume

B-Bäume

• Definition

Splay-Bäume

• Definition