Grundlegendes Niveau (Grundkurs und Leistungskurs)
- lineare Listen:
- objektorientierte Modellierung
- Algorithmen zum Durchlaufen, Einfügen, Löschen und Aktualisieren von Knoten
- Stapel und Warteschlange
Qualifikationsphase Q1 · Themenfeld Q1.4
Q1.4 – Höhere Datenstrukturen
Modellieren, operieren, deuten und vergleichenDie Darstellungen dieser Seite werden aus denselben Renderern erzeugt wie die Werkzeuge für lineare Datenstrukturen und Bäume.
Jeder Abschnitt folgt dem Lernmuster Modell → Beispiel → Darstellung → Deutung → Vergleich, damit die Visualisierung fachlich eingebettet bleibt.
Kerncurriculum kompakt
Anforderungen nach Kursniveau
Kerncurriculum kompakt
Anforderungen nach Kursniveau
Anforderungen nach Kursniveau
Erhöhtes Niveau (Leistungskurs)
- binäre Bäume:
- objektorientierte Modellierung
- Algorithmen zum Durchlaufen, Einfügen, Löschen und Aktualisieren von Knoten
Anforderungen an eine Datenstruktur
Leitfragen zu Zugriff, Änderung und Speicherorganisation
Anforderungen an eine Datenstruktur
Leitfragen zu Zugriff, Änderung und Speicherorganisation
Leitfragen zu Zugriff, Änderung und Speicherorganisation
Problemsituation: Eine Lerngruppe sammelt Quellenkarten für ein Referat. Karten werden fortlaufend ergänzt, teils neu einsortiert und später in einer festen Arbeitsreihenfolge abgearbeitet. Genau daraus entsteht die Strukturfrage: Welche Operationen müssen häufig, sicher und effizient möglich sein?
Größe / Kapazität
Ist die Menge begrenzt (feste Kapazität) oder wächst sie dynamisch? Diese Entscheidung wirkt direkt auf Speicherstrategie und Wartungskosten.
Organisationsprinzip
Linear, hierarchisch oder mit Zugriffsbeschränkung (Stack/Queue): Das Prinzip legt fest, welche Wege für Algorithmen erlaubt sind.
Zugriff und Änderung
Indexzugriff, Traversieren oder Endenzugriff bestimmen, wie Einfügen, Löschen, Aktualisieren und Auslesen fachlich umgesetzt werden.
Zeit + Speicher
Entscheidend ist die Kombination aus Laufzeitidee (z. B. O(1) vs. O(n)) und Speicherbedarf (zusammenhängende Felder vs. Referenzaufwand).
Folgerung für die Strukturwahl
Erst das Operationsprofil führt zur passenden Struktur: Viele get(i)-Zugriffe sprechen für ein Array; häufiges Einfügen/Löschen entlang eines Pfads spricht für Referenzstrukturen; disziplinierte Abarbeitung für Stack/Queue.
Lineare Liste als abstraktes Modell (ADT)
Abstrakte Operationen vs. konkrete Implementierung
Lineare Liste als abstraktes Modell (ADT)
Abstrakte Operationen vs. konkrete Implementierung
Abstrakte Operationen vs. konkrete Implementierung
Die lineare Liste ist zuerst ein abstrakter Datentyp (ADT): Sie definiert Reihenfolge und erlaubte Operationen – noch ohne technische Festlegung auf Array oder Verkettung.
Modell-Ebene (fachlich)
init, length, isEmpty, find, get, set, insert, remove, traverse beschreiben was an der Liste möglich ist.
Implementierungs-Ebene (technisch)
Ob intern ein Array oder Knoten mit Referenzen genutzt werden, ist die zweite Entscheidung. Sie bestimmt Laufzeiten, Speicherbedarf und lokale/globalen Änderungsaufwand.
Array-basierte Liste
Direktzugriff und Verschiebungskosten
Array-basierte Liste
Direktzugriff und Verschiebungskosten
Direktzugriff und Verschiebungskosten
Array-basierte Listen nutzen zusammenhängende Zellen. Dadurch ist get(i) direkt: Der Speicherort ergibt sich rechnerisch aus Startadresse + Offset.
Beispiel: Einfügen an Position 1
Strukturierte Auswertung der Grafik
- Schrittfolge: Zum Einfügen an Position 1 werden zuerst die Werte rechts davon (40, 30, 20) verschoben.
- Strukturregel: Positionen bleiben geordnet, daher sind alle nachfolgenden Indizes betroffen (globaler Eingriff).
- Kostenidee:
get(i)meist O(1), Einfügen/Löschen in der Mitte typischerweise O(n). - Speicherdeutung: Freie Plätze sind Reserve (Vorteil), können aber bei falscher Schätzung zu Verschwendung oder Reallokation führen (Nachteil).
Wann ist ein Array sinnvoll?
Wenn häufig gelesen, indiziert oder überschrieben wird und Einfügen/Löschen in der Mitte selten vorkommt – z. B. Tabellenzeilen mit stabilem Umfang.
Verkettete Liste
Referenzmodell und lokale Operationen
Verkettete Liste
Referenzmodell und lokale Operationen
Referenzmodell und lokale Operationen
Im Referenzmodell enthält jeder Knoten value (Inhalt) und next (Verweis auf Nachfolger). Zeiger wie head, current und tail steuern den Algorithmuszustand.
Strukturmodell
Was man lernen soll: Reihenfolge entsteht durch Pfeile, nicht durch Speicherlage. Dadurch kann ein Knotenwert geändert werden, ohne die Struktur umzubauen.
Traversieren statt Direktzugriff
Bei current = current.next wird der Zugriffspfad explizit verlängert. Position entsteht erst durch Durchlaufen; daher hängen die Kosten von der Weglänge ab (typisch O(n)).
Lokales Einfügen hinter current
Zuerst übernimmt new.next den alten Nachfolger, danach wird current.next = new gesetzt. Diese Reihenfolge verhindert Informationsverlust und hält den Rest der Liste erreichbar.
Lokales Löschen hinter current
Deutung
Beim Löschen wird die Verbindung über den Nachfolger „hinweg“ gesetzt. Der entfernte Knoten verschwindet logisch aus der Struktur, ohne globales Verschieben.
Gegenbeispiel: Aktualisieren
set(current, neuerWert) verändert nur value. Das ist bewusst ein Gegenfall zur Strukturänderung: Inhalt ändert sich, Referenzgraph bleibt gleich.
Stack (LIFO)
Push/Top/Pop am selben Zugriffspunkt
Stack (LIFO)
Push/Top/Pop am selben Zugriffspunkt
Push/Top/Pop am selben Zugriffspunkt
Ein Stack besitzt genau einen aktiven Zugriffspunkt (top). Einfügen und Entfernen erfolgen an derselben Seite.
Deutung des LIFO-Prinzips
Weil push und pop zwingend am selben Ende arbeiten, entsteht LIFO nicht zufällig, sondern aus der Zugriffstopologie.
Anwendungsdeutung
Balancierte Klammern: Öffnende Klammern werden gepusht, bei schließender Klammer muss genau das zuletzt offene Symbol passen. Gleiches Prinzip trägt den Call-Stack.
Queue (FIFO)
Enqueue am tail, Dequeue am head
Queue (FIFO)
Enqueue am tail, Dequeue am head
Enqueue am tail, Dequeue am head
Eine Queue besitzt zwei definierte Enden: Einfügen hinten (tail), Entnehmen vorne (head).
Deutung des FIFO-Prinzips
FIFO entsteht durch getrennte Enden: hinten rein, vorne raus. Die Zugriffsbeschränkung ist die eigentliche Strukturidee – nicht „nur eine andere Liste“.
Anwendungsdeutung
Warteschlangen, CPU-Scheduling oder Topologie-Verfahren (Knoten mit Grad 0 zuerst): Die Queue hält die faire Abarbeitungsreihenfolge stabil.
Bäume und binäre Suchbäume
Hierarchie, Traversierung und BST-Operationen
Bäume und binäre Suchbäume
Hierarchie, Traversierung und BST-Operationen
Hierarchie, Traversierung und BST-Operationen
Warum Bäume?
Hierarchien wie Organigramme sind nicht sinnvoll linear darstellbar: Unterordnung, Zuständigkeiten und Eskalationswege benötigen Verzweigung statt bloßer Reihenfolge.
Grundbegriffe
Wurzel (kein Vorgänger), innere Knoten (mit Kindern), Blätter (ohne Kinder), Kanten (Verbindung): Diese Begriffe sind nötig, um Baumalgorithmen präzise zu formulieren.
Strukturparameter und algorithmische Bedeutung
Grad, Pfad, Tiefe und Ebenen beschreiben den Suchraum: tiefe Bäume verlängern Pfade, breite Ebenen erhöhen parallelen Bearbeitungsaufwand.
Teilbäume und Rekursion
Jeder Teilbaum ist wieder ein Baum. Genau diese Selbstähnlichkeit trägt rekursive Verfahren wie Traversierung, Suche und Aggregation.
Binäre Bäume und Traversierung
Binäre Bäume beschränken auf linken/rechten Teilbaum. Dadurch werden Preorder, Inorder, Postorder algorithmisch eindeutig definierbar.
Merksatz: Inorder (links–Knoten–rechts) liefert im BST sortierte Werte, weil links stets kleiner und rechts stets größer ist.
BST-Ordnungsregel und Operationen
BST-Ordnungsregel: links kleiner, rechts größer. Diese Invariante verkleinert den Suchraum nach jedem Vergleich und erklärt die Effizienzidee gegenüber unsortierten Strukturen.
Suche: Jeder Vergleich am aktuellen Knoten entscheidet links/rechts und verwirft den jeweils anderen Teilbaum vollständig.
Einfügen: Es ist immer eine Suche nach einem freien Kind entlang des Pfads; deshalb endet Einfügen als neuer Blattknoten.
Löschen: Fallidee
Blatt: direkt entfernen. Ein Kind: Kind hochziehen. Zwei Kinder: über Inorder-Nachfolger/-Vorgänger ersetzen, weil sonst die Ordnungsregel brechen würde.
Mini-Anwendung
Ein BST eignet sich für Wörterbücher oder Ranglisten, in denen Schlüssel dynamisch eingefügt und gesucht werden.
Vergleichsfläche: linear vs. nicht-linear
Systematischer Vergleich der Strukturen
Vergleichsfläche: linear vs. nicht-linear
Systematischer Vergleich der Strukturen
Systematischer Vergleich der Strukturen
Der Vergleich ist wichtig, weil Datenstrukturen nicht isoliert „gut“ oder „schlecht“ sind. Entscheidend ist die Passung zwischen Operationsprofil und Strukturprinzip.
Merksatz 1
Direktzugriff (Array) vs. Traversieren (Liste/Baum) ist eine Grundentscheidung zwischen schneller Positionsadressierung und flexibler Strukturänderung.
Merksatz 2
Lineare Folge organisiert Reihenfolge, Hierarchie organisiert Über-/Unterordnung; Stack/Queue erzwingen zusätzlich eine Zugriffsdisziplin.
| Kriterium | Array-Liste | Verkettete Liste | Stack / Queue | Allgemeiner Baum | Binärer Suchbaum |
|---|---|---|---|---|---|
| Struktur | linear, positionsbasiert | linear, referenzbasiert | linear mit Enden-Regel | hierarchisch, verzweigt | hierarchisch + geordnet |
| Zugriff | Index, direkt | Traversieren über next | nur an Enden | pfadbasiert über Ebenen | pfadbasiert mit </> |
| Stärken | schnelles Lesen per Index | lokale Strukturänderungen | klare Ablaufdisziplin | Abbildung komplexer Hierarchien | dynamische sortierte Suche |
| Typische Kosten | Verschieben beim Einfügen/Löschen | kein Direktzugriff auf Positionen | eingeschränkter Zugriff | Pfadlänge abhängig von Tiefe | bei Unbalance längere Pfade |