Informatik Datenstrukturen – Tries und Präfixbäume
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist ein Trie (Präfixbaum)? · Wie ist ein Trie-Knoten typischerweise strukturiert?
Karten
15 KartenWas ist ein Trie (Präfixbaum)?
Rückseite
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?
Rückseite
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?
Rückseite
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?
Rückseite
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?
Rückseite
O(m) mit m als Länge des gesuchten oder eingefügten Wortes, unabhängig von der Anzahl gespeicherter Wörter.
Wie funktioniert die Lösch-Operation in einem Trie?
Rückseite
Man sucht das Wort, setzt das Wortende-Flag zurück und entfernt rekursiv Knoten ohne Kinder und ohne Wortende-Flag vom Blatt zur Wurzel.
Wie hoch ist die Speicherkomplexität eines Tries?
Rückseite
O(n × k) mit n als Anzahl der Wörter und k als durchschnittliche Wortlänge; bei vielen gemeinsamen Präfixen deutlich weniger als n × k Knoten.
Wie ermöglicht ein Trie effiziente Präfixsuche für Autovervollständigung?
Rückseite
Man navigiert zum Knoten des Präfixes und traversiert rekursiv alle Nachkommen, um alle Wörter mit diesem Präfix zu sammeln.
Was ist ein komprimierter Trie (Radix Tree / Patricia Trie)?
Rückseite
Ein Trie, in dem Ketten von Knoten mit nur einem Kind zu einer einzelnen Kante mit einem String-Label zusammengefasst werden, was Speicher spart.
Was unterscheidet einen Ternary Search Trie (TST) von einem Standard-Trie?
Rückseite
Ein TST nutzt binäre Suchbäume pro Knoten (drei Kinder: kleiner, gleich, größer) statt Arrays, was bei großen Alphabeten speichereffizienter ist.
Wann ist ein Trie einer Hash-Tabelle für String-Suche überlegen?
Rückseite
Bei Präfixsuche, lexikographischer Sortierung und wenn viele Strings gemeinsame Präfixe teilen; Hash-Tabellen unterstützen Präfixoperationen nicht nativ.
Wie nutzt man einen Trie als Wörterbuch für Rechtschreibprüfung?
Rückseite
Alle gültigen Wörter werden eingefügt; bei Prüfung sucht man das Wort – fehlt das Wortende-Flag, ist es unbekannt; Nearby-Wörter lassen sich über Präfixe finden.
Was ist der Zusammenhang zwischen Trie und Suffixbaum?
Rückseite
Ein Suffixbaum ist ein komprimierter Trie aller Suffixe eines Strings; er ermöglicht substring-Suche in O(m) statt O(n×m).
Wie wirkt sich die Alphabetgröße auf die Trie-Performance aus?
Rückseite
Große Alphabete (z. B. Unicode) erhöhen den Speicherbedarf pro Knoten stark; TSTs oder komprimierte Tries sind dann oft besser geeignet.
Was ist der Unterschied zwischen Trie und DAWG (Directed Acyclic Word Graph)?
Rückseite
Ein DAWG ist ein minimierter, deterministischer Automat, der äquivalente Teilbäume eines Tries zusammenfasst und damit noch speichereffizienter ist.