Informatik Datenstrukturen – Tries und Präfixbäume
Tries sind baumartige Datenstrukturen für effizientes Speichern und Suchen von Strings mit gemeinsamen Präfixen. Nach dem Lernen dieser Karten kennst du Aufbau, Insert-, Search- und Delete-Operationen, Laufzeitkomplexitäten und typische Anwendungen wie Autovervollständigung und Wörterbücher.
Lernziele
Was du in dieser Lektion lernst
- Was ist ein Trie (Präfixbaum)?
- Wie ist ein Trie-Knoten typischerweise strukturiert?
- Was speichert die Wurzel eines Tries?
- Wie funktioniert das Einfügen eines Wortes in einen Trie?
Lerntipp
Zeichne einen Trie für 'Auto', 'Automat', 'Autobahn' von Hand – du erkennst sofort, wie sich gemeinsame Präfixe Knoten teilen und Speicher sparen.
Hinweis: Der Inhalt dieser Seite wurde mit einem KI-Modell erzeugt und nicht von Fachmenschen geprüft. Nutze die Karten als Lernhilfe und gleiche medizinische oder rechtliche Aussagen mit deinen Unterlagen ab.
Karteikarten
Alle 15 Lernkarten
Tippe auf eine Karte, um die Antwort aufzudecken
Häufige Fragen
Die wichtigsten Fragen zu Informatik Datenstrukturen – Tries und Präfixbäume
- Was ist ein Trie (Präfixbaum)?
- Ein Trie ist ein geordneter Baum, bei dem Kanten mit Zeichen beschriftet sind und jeder Pfad von der Wurzel einen String oder dessen Präfix repräsentiert.
- Wie ist ein Trie-Knoten typischerweise strukturiert?
- Ein Knoten enthält ein Array oder eine Map für Kindknoten (pro Alphabetzeichen) und ein boolesches Flag, das das Wortende markiert.
- Was speichert die Wurzel eines Tries?
- Die Wurzel entspricht dem leeren Präfix und speichert selbst kein Zeichen; ihre Kinder repräsentieren die ersten Zeichen aller eingefügten Wörter.
- Wie funktioniert das Einfügen eines Wortes in einen Trie?
- Man folgt ab der Wurzel den Kanten für jedes Zeichen; fehlende Knoten werden angelegt, am letzten Knoten wird das Wortende-Flag gesetzt.
- Wie lautet die Laufzeitkomplexität für Search und Insert in einem Trie?
- O(m) mit m als Länge des gesuchten oder eingefügten Wortes, unabhängig von der Anzahl gespeicherter Wörter.
Warum Atrio?
- FSRS-5 Spaced Repetition
- Der Algorithmus plant jede Wiederholung anhand deiner eigenen Lernhistorie und stellt Karten kurz bevor du sie vergisst – das reduziert unnötige Wiederholungen.
- KI-Import
- Notizen, Skripte und PDFs in Sekunden in Lernkarten verwandeln – genau wie diese Seite automatisch entsteht.
- Prüfungsplanung
- Termine hinterlegen und Atrio berechnet rückwärts, wie viele Karten du pro Tag lernen musst – ohne Stress.
Interaktiv lernen
Diese 15 Karten jetzt interaktiv in der Atrio-App lernen
Atrio zeigt dir jede Karte dann, wenn du sie fast vergessen hättest – damit bleibt genau das hängen, was du lernst.
Starter-Plan kostenlos – keine Kreditkarte erforderlich.