Baumstruktur
Baumstruktur
Baumstruktur
Einleitung
Eine Baumstruktur ist in der Informatik eine hierarchische Datenstruktur. Sie besteht aus Knoten und Kanten. Bei einem gewurzelten Baum gibt es genau eine Wurzel. Jeder andere Knoten besitzt genau einen Elternknoten, kann aber mehrere Kinder haben. Dadurch lassen sich verzweigte Beziehungen übersichtlich darstellen.
Dieser aiMOOC richtet sich an Lernende der Sekundarstufe II und der beruflichen IT-Ausbildung. Du lernst die Grundbegriffe, den Binärbaum, den binären Suchbaum und wichtige Arten der Traversierung kennen.
Grundidee und Fachbegriffe
Ein Baum beginnt an der Wurzel und verzweigt sich über Kanten zu weiteren Knoten. Ein Knoten ohne Kinder heißt Blatt. Ein Knoten zusammen mit allen darunterliegenden Knoten bildet einen Teilbaum.
| Begriff | Bedeutung |
|---|---|
| Wurzel | Oberster Ausgangsknoten eines gewurzelten Baums |
| Elternknoten | Direkter Vorgänger eines Knotens |
| Kindknoten | Direkter Nachfolger eines Knotens |
| Blatt | Knoten ohne Kinder |
| Tiefe | Anzahl der Kanten von der Wurzel bis zu einem Knoten |
| Höhe | Länge des längsten abwärts führenden Pfads bis zu einem Blatt |
Baum und Teilbaum
Die Struktur ist rekursiv: Jeder Teilbaum ist selbst wieder ein Baum. Diese Eigenschaft macht Bäume besonders geeignet für rekursive Algorithmen. Ein Baum mit nur einem Knoten besteht ausschließlich aus seiner Wurzel.
Binärbaum
Ein Binärbaum ist ein Baum, bei dem jeder Knoten höchstens zwei Kinder besitzt. Meist spricht man vom linken und rechten Kind. Ein Binärbaum muss nicht vollständig und auch nicht automatisch sortiert sein.
Binärer Suchbaum
Ein binärer Suchbaum ergänzt den Binärbaum um eine Ordnungsregel. In einer üblichen Variante liegen kleinere Schlüssel im linken und größere Schlüssel im rechten Teilbaum. Dadurch kann die Suche nach einem Wert schrittweise auf einen Teilbaum eingeschränkt werden.
Für die Laufzeit ist die Höhe entscheidend. Suchen benötigt im Wesentlichen Zeit proportional zur Baumhöhe. Bei einem balancierten Suchbaum ist die Höhe typischerweise logarithmisch zur Anzahl der Knoten. Ein stark entarteter Baum kann dagegen nahezu wie eine Liste aussehen und eine lineare Suchzeit verursachen.
Traversierung
Unter Traversierung versteht man das systematische Besuchen aller Knoten eines Baums. Bei einem Binärbaum sind besonders vier Reihenfolgen wichtig:
| Verfahren | Reihenfolge | Idee |
|---|---|---|
| Preorder | Knoten – linker Teilbaum – rechter Teilbaum | Der aktuelle Knoten wird zuerst verarbeitet |
| Inorder | Linker Teilbaum – Knoten – rechter Teilbaum | Bei binären Suchbäumen entstehen die Schlüssel in sortierter Reihenfolge |
| Postorder | Linker Teilbaum – rechter Teilbaum – Knoten | Der aktuelle Knoten wird zuletzt verarbeitet |
| Levelorder | Ebene für Ebene | Die Suche erfolgt in die Breite |
Eine vollständige Traversierung besucht jeden Knoten. Für einen Baum mit n Knoten liegt der Aufwand deshalb in Θ(n).
Anwendungen
Baumstrukturen findest Du in vielen Bereichen der Informatik. Verzeichnisstrukturen werden häufig baumartig dargestellt. Auch das DOM einer Webseite, Syntaxbäume in Programmiersprachen, Entscheidungsbäume und verschiedene Datenbankindizes nutzen hierarchische oder baumartige Strukturen.
Warum Baumstrukturen nützlich sind
Bäume bilden Hierarchien direkt ab und erlauben oft effiziente Such-, Einfüge- und Löschoperationen. Die konkrete Effizienz hängt jedoch von der Baumart und ihrer Form ab. Deshalb gibt es balancierte Suchbäume wie AVL-Bäume oder Rot-Schwarz-Bäume sowie mehrwegige Strukturen wie B-Bäume.
Interaktive Aufgaben
Quiz: Teste Dein Wissen
Wie heißt der oberste Knoten eines gewurzelten Baums? (Wurzel) (!Blatt) (!Kante) (!Teilbaum)
Wie heißt ein Knoten ohne Kinder? (Blatt) (!Wurzel) (!Elternknoten) (!Suchpfad)
Wie viele Kinder kann ein Knoten in einem Binärbaum höchstens haben? (Zwei) (!Eins) (!Drei) (!Beliebig viele)
Wie viele Elternknoten besitzt jeder Nichtwurzelknoten in einem gewurzelten Baum? (Einen) (!Keinen) (!Zwei) (!Beliebig viele)
Welche Aussage beschreibt einen binären Suchbaum in einer üblichen Ordnung? (Kleinere Schlüssel liegen links und größere rechts) (!Alle Schlüssel liegen nur in den Blättern) (!Jeder Knoten besitzt genau zwei Kinder) (!Die Wurzel ist immer der kleinste Schlüssel)
Welche Traversierung besucht beim Binärbaum zuerst den linken Teilbaum, dann den Knoten und danach den rechten Teilbaum? (Inorder) (!Preorder) (!Postorder) (!Levelorder)
Welche Traversierung arbeitet Ebene für Ebene? (Levelorder) (!Inorder) (!Postorder) (!Preorder)
Wovon hängt die Suchzeit in einem binären Suchbaum wesentlich ab? (Von der Höhe des Baums) (!Von der Farbe der Knoten) (!Von der Bildschirmgröße) (!Von der Dateiendung)
Welchen Aufwand hat eine vollständige Traversierung mit n Knoten? (Linear) (!Konstant) (!Quadratisch) (!Unabhängig von der Knotenzahl)
Was ist ein Teilbaum? (Ein Knoten mit allen darunterliegenden Knoten) (!Nur die Wurzel ohne Nachfolger) (!Eine einzelne Kante) (!Eine sortierte Liste ohne Verzweigung)
Memory
| Wurzel | Oberster Ausgangsknoten |
| Blatt | Knoten ohne Kinder |
| Kante | Verbindung zwischen Knoten |
| Tiefe | Abstand eines Knotens von der Wurzel |
| Teilbaum | Hierarchie unterhalb eines gewählten Knotens |
| Traversierung | Systematisches Besuchen von Knoten |
Drag and Drop
| Ordne die richtigen Begriffe zu. | Beschreibung |
|---|---|
| Wurzel | Startpunkt eines gewurzelten Baums |
| Blatt | Endknoten ohne Kinder |
| Preorder | Knoten vor den beiden Teilbäumen |
| Inorder | Knoten zwischen linkem und rechtem Teilbaum |
| Postorder | Knoten nach den beiden Teilbäumen |
Kreuzworträtsel
| Wurzel | Wie heißt der oberste Knoten eines gewurzelten Baums? |
| Blatt | Wie heißt ein Knoten ohne Kinder? |
| Knoten | Wie heißt ein einzelnes Element eines Baums? |
| Kante | Wie heißt die Verbindung zwischen zwei Knoten? |
| Binärbaum | Wie heißt ein Baum mit höchstens zwei Kindern pro Knoten? |
| Traversierung | Wie heißt das systematische Besuchen aller Knoten? |
LearningApps
Lückentext
Offene Aufgaben
Leicht
- Baumdiagramm: Zeichne eine Baumstruktur mit mindestens acht Knoten und markiere Wurzel, Elternknoten, Kindknoten und Blätter.
- Dateisystem: Untersuche eine Ordnerstruktur auf Deinem Gerät und übertrage einen kleinen Ausschnitt als Baumdiagramm.
- Binärbaum: Erstelle einen Binärbaum aus frei gewählten Begriffen und prüfe, ob jeder Knoten höchstens zwei Kinder hat.
- Fachbegriffe: Gestalte eine Lernkarte, auf der Du Wurzel, Blatt, Tiefe, Höhe und Teilbaum mit eigenen Beispielen erklärst.
Standard
- Binärer Suchbaum: Füge die Werte 8, 3, 10, 1, 6, 14, 4 und 7 nacheinander in einen binären Suchbaum ein und dokumentiere jeden Schritt.
- Traversierung: Bestimme für Deinen Suchbaum Preorder, Inorder, Postorder und Levelorder und vergleiche die Ergebnisse.
- Algorithmus: Formuliere in Pseudocode eine rekursive Preorder-Traversierung und erläutere den Abbruchfall.
- Vergleich von Datenstrukturen: Vergleiche eine lineare Liste mit einem balancierten Suchbaum für die Aufgabe, häufig Werte zu suchen.
Schwer
- Laufzeitanalyse: Konstruiere zwei Suchbäume mit denselben Schlüsseln, aber sehr unterschiedlicher Höhe, und erkläre die Folgen für die Suche.
- AVL-Baum: Recherchiere, warum Balancierung bei Suchbäumen wichtig ist, und stelle das Prinzip eines AVL-Baums in einem eigenen Schaubild dar.
- DOM: Untersuche die DOM-Struktur einer einfachen Webseite mit Entwicklerwerkzeugen und dokumentiere einen Teilbaum mit mindestens drei Ebenen.
- Programmierung: Implementiere einen einfachen binären Suchbaum mit Einfügen, Suchen und Inorder-Traversierung in einer Programmiersprache Deiner Wahl.
|
|
Lernkontrolle
- Modellierung: Eine Schule möchte Fächer, Kurse und Lernmaterialien hierarchisch organisieren. Entwirf eine passende Baumstruktur und begründe Deine Wahl der Knotenebenen.
- Fehleranalyse: Ein Suchbaum enthält links von einem Knoten einen größeren Schlüssel. Erkläre, welche Eigenschaft verletzt ist und welche Folgen das für die Suche haben kann.
- Effizienz: Vergleiche einen balancierten und einen stark entarteten Suchbaum mit gleich vielen Knoten. Erkläre ohne konkrete Messung, warum sich Suchzeiten unterscheiden können.
- Traversierung: Wähle für das Ausgeben aller Schlüssel eines binären Suchbaums in aufsteigender Reihenfolge eine Traversierung und begründe Deine Entscheidung.
- Transfer: Erkläre an einem selbst gewählten Beispiel außerhalb der Informatik, welche Beziehungen sich sinnvoll als Baum darstellen lassen und wo das Modell an Grenzen stößt.
- Algorithmisches Denken: Beschreibe, wie eine Breitensuche und eine Tiefensuche denselben Baum unterschiedlich erkunden und nenne je eine passende Anwendungssituation.
Lernnachweis
Für einen Lernnachweis solltest Du zeigen, dass Du:
- die Grundbegriffe einer Baumstruktur sicher und an einem Diagramm erklären kannst,
- Binärbäume und binäre Suchbäume unterscheiden kannst,
- Suchpfade in einem binären Suchbaum nachvollziehen kannst,
- Preorder, Inorder, Postorder und Levelorder korrekt anwenden kannst,
- den Einfluss der Baumhöhe auf die Effizienz begründet einschätzen kannst,
- eine reale Hierarchie als Baum modellieren und die Grenzen des Modells benennen kannst.
OERs zum Thema
Verknüpfte Lernbereiche