Overview
Ein Trie (Präfixbaum) speichert Strings über gemeinsame Präfixe und ermöglicht O(k) Einfügen, Suche und Präfixsuche.
Analogy
Wörterbuch nach Buchstaben: Ast bei 'a', dann 'ap', dann 'app', dann 'apple'.
Step-by-step
- Jeder Knoten hat children-Dict (oder Array mit 26 Einträgen) und is_end-Flag.
- Einfügen: für jedes Zeichen, bewege zu/erstelle Kind-Knoten; markiere letzten als Ende.
- Exakte Suche: Zeichen traversieren; is_end am letzten Knoten prüfen.
- Präfixsuche: Präfix traversieren; True wenn alle Zeichen gefunden (kein is_end nötig).
Visual
Einfügen 'cat','cap': root→c→a→t(end), root→c→a→p(end); gemeinsamer Präfix 'ca'.
Common mistakes
- is_end nur am letzten Zeichen setzen (korrekt), nicht an Zwischenknoten.
- Löschen aus Trie erfordert sorgfältige Behandlung – gemeinsame Präfixknoten nicht löschen.
Practice questions
- Autocomplete implementieren: alle Wörter mit gegebenem Präfix zurückgeben.
- Trie für Suche nach längstem Wort in Wörterbuch verwenden.
Time
O(k) pro Operation (k = Wortlänge)
Space
O(ALPHABET × n × k) worst-case