Trie (Präfixbaum)
Zuletzt aktualisiert
Ein Trie (ausgesprochen „trai"), oder Präfixbaum, speichert eine Menge von Zeichenketten anhand ihrer Zeichen: Jede Kante ist mit einem Zeichen beschriftet, und ein Pfad von der Wurzel buchstabiert ein Präfix. Wörter mit gemeinsamem Präfix teilen sich dieselben Knoten, sodass „car", „card" und „care" alle den Pfad c-a-r wiederverwenden. Drücke oben auf Abspielen, um zu sehen, wie Wörter Zeichen für Zeichen eingefügt werden und sich nur dort verzweigen, wo sie sich unterscheiden.
Da Suchvorgänge einen Knoten pro Zeichen durchlaufen, dauert die Suche nach einem Wort der Länge m O(m), unabhängig davon, wie viele Wörter der Trie enthält. Das macht Tries ideal für Autovervollständigung, Rechtschreibprüfung und Präfixsuche.
Zeit- und Speicherkomplexität
| Operation | Komplexität | Anmerkungen |
|---|---|---|
| Einfügen | O(m) | m = Länge des Worts |
| Suchen | O(m) | Ein Schritt pro Zeichen |
| Präfixabfrage | O(m) | Bis zum Präfixknoten laufen |
| Speicher | O(total chars) | Gemeinsame Präfixe werden nur einmal gespeichert |
Schritt für Schritt (Einfügen)
| Schritt | Was passiert |
|---|---|
| 1 | Beginne beim Wurzelknoten. |
| 2 | Suche für jedes Zeichen des Worts nach einer passenden Kind-Kante. |
| 3 | Wenn sie existiert, folge ihr (und verwende das gemeinsame Präfix wieder). |
| 4 | Wenn nicht, erstelle einen neuen Kindknoten für dieses Zeichen. |
| 5 | Markiere den Knoten nach dem letzten Zeichen als Wortende. |
Durchgerechnetes Beispiel
Einfügen von ["car", "card", "care"] in einen leeren Trie:
| Schritt | Struktur | Aktion |
|---|---|---|
car einfügen | root → c → a → r✓ | Es gibt keine passenden Kinder, also erstelle c, a, r und markiere r als Wortende. |
card einfügen | root → c → a → r✓ → d✓ | Verwende den vorhandenen Pfad c-a-r wieder, erstelle dann ein neues Kind d und markiere es als Wortende. |
care einfügen | root → c → a → r✓ → {d✓, e✓} | Verwende c-a-r wieder, verzweige von r mit einem neuen Kind e und markiere e als Wortende. |
care suchen | root → c → a → r → e✓ | Laufe c, a, r, e ab; der letzte Knoten ist als Wortende markiert, also ist care vorhanden. |
ca suchen | root → c → a | Der Pfad existiert, aber a ist nicht als Wortende markiert, also ist ca ein Präfix, aber kein gespeichertes Wort. |
Wann man einen Trie verwendet
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Du Präfixabfragen oder Autovervollständigung über eine Menge von Zeichenketten brauchst. | Du nur Suchen nach ganzen Schlüsseln brauchst - eine Hashtabelle ist schneller und leichter. |
| Viele gespeicherte Wörter gemeinsame Präfixe teilen, sodass Knoten wiederverwendet werden. | Die Schlüssel lang sind und sich selten überschneiden, wodurch pro Zeichen ein Knoten verschwendet wird. |
| Du willst, dass Schlüssel per Durchlauf in sortierter Reihenfolge zurückgegeben werden. | Der Speicher knapp ist - Kind-Zeiger pro Knoten verursachen erheblichen Mehraufwand. |
| Die Suchkosten von der Schlüssellänge abhängen sollen, nicht von der Datensatzgröße. | Das Alphabet riesig ist (z. B. das gesamte Unicode) und Kinder dicht gespeichert werden. |
Trie (Prefix Tree)-Code
Eine saubere, lauffähige Trie (Prefix Tree)-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Trie (Prefix Tree)-Code in Python
Python
1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_word = False5
6
7class Trie:8 def __init__(self):9 self.root = TrieNode()10
11 def insert(self, word):12 node = self.root13 for ch in word:14 node = node.children.setdefault(ch, TrieNode())15 node.is_word = True16
17 def search(self, word):18 node = self._walk(word)19 return node is not None and node.is_word20
21 def starts_with(self, prefix):22 return self._walk(prefix) is not None23
24 def _walk(self, s):25 node = self.root26 for ch in s:27 if ch not in node.children:28 return None29 node = node.children[ch]30 return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35 trie.insert(word)36
37print("search(card): ", trie.search("card"))38print("search(ca): ", trie.search("ca"))39print("starts_with(ca): ", trie.starts_with("ca"))40print("starts_with(do): ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))Trie (Prefix Tree)-Code in JavaScript
JavaScript
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEnd = false;5 }6}7
8class Trie {9 constructor() {10 this.root = new TrieNode();11 }12
13 insert(word) {14 let node = this.root;15 for (const ch of word) {16 if (!node.children[ch]) node.children[ch] = new TrieNode();17 node = node.children[ch];18 }19 node.isEnd = true;20 }21
22 // Walk the prefix; null when a character is missing23 findNode(prefix) {24 let node = this.root;25 for (const ch of prefix) {26 node = node.children[ch];27 if (!node) return null;28 }29 return node;30 }31
32 search(word) {33 const node = this.findNode(word);34 return node !== null && node.isEnd;35 }36
37 startsWith(prefix) {38 return this.findNode(prefix) !== null;39 }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));Trie (Prefix Tree)-Code in Java
Java
1public class Main {2 static class Node {3 Node[] children = new Node[26];4 boolean isWord;5 }6
7 static Node root = new Node();8
9 static void insert(String word) {10 Node cur = root;11 for (char c : word.toCharArray()) {12 int i = c - 'a';13 if (cur.children[i] == null) cur.children[i] = new Node();14 cur = cur.children[i];15 }16 cur.isWord = true;17 }18
19 // Follow the path for s; null means no word has this prefix20 static Node walk(String s) {21 Node cur = root;22 for (char c : s.toCharArray()) {23 cur = cur.children[c - 'a'];24 if (cur == null) return null;25 }26 return cur;27 }28
29 static boolean search(String word) {30 Node node = walk(word);31 return node != null && node.isWord;32 }33
34 static boolean startsWith(String prefix) {35 return walk(prefix) != null;36 }37
38 public static void main(String[] args) {39 insert("code");40 insert("coder");41 insert("cool");42 System.out.println("search code: " + search("code"));43 System.out.println("search cod: " + search("cod"));44 System.out.println("startsWith cod: " + startsWith("cod"));45 System.out.println("startsWith cat: " + startsWith("cat"));46 }47}Trie (Prefix Tree)-Code in C++
C++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6 std::unordered_map<char, TrieNode*> children;7 bool isEnd = false;8};9
10struct Trie {11 TrieNode* root = new TrieNode();12
13 void insert(const std::string& word) {14 TrieNode* node = root;15 for (char c : word) {16 if (!node->children.count(c)) node->children[c] = new TrieNode();17 node = node->children[c];18 }19 node->isEnd = true;20 }21
22 // Follow the path for s; nullptr if a link is missing23 TrieNode* walk(const std::string& s) const {24 TrieNode* node = root;25 for (char c : s) {26 auto it = node->children.find(c);27 if (it == node->children.end()) return nullptr;28 node = it->second;29 }30 return node;31 }32
33 bool search(const std::string& word) const {34 TrieNode* node = walk(word);35 return node != nullptr && node->isEnd;36 }37
38 bool startsWith(const std::string& prefix) const {39 return walk(prefix) != nullptr;40 }41};42
43int main() {44 Trie trie;45 for (const std::string& word : {"car", "card", "care", "dog"}) {46 trie.insert(word);47 }48 std::cout << std::boolalpha;49 std::cout << "search(card): " << trie.search("card") << "\n";50 std::cout << "search(ca): " << trie.search("ca") << "\n";51 std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52 std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53 return 0;54}Trie (Prefix Tree)-Code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6 struct TrieNode* children[26];7 bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11 return calloc(1, sizeof(TrieNode)); // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15 for (; *word; word++) {16 int i = *word - 'a';17 if (root->children[i] == NULL) root->children[i] = newNode();18 root = root->children[i];19 }20 root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25 for (; *s; s++) {26 root = root->children[*s - 'a'];27 if (root == NULL) return NULL;28 }29 return root;30}31
32bool search(TrieNode* root, const char* word) {33 TrieNode* node = walk(root, word);34 return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38 return walk(root, prefix) != NULL;39}40
41int main(void) {42 TrieNode* root = newNode();43 const char* words[] = {"car", "card", "care", "dog"};44 for (int i = 0; i < 4; i++) insert(root, words[i]);45 printf("search(card): %s\n", search(root, "card") ? "true" : "false");46 printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47 printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48 printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49 return 0;50}Trie-FAQ
Wofür wird ein Trie verwendet?
Tries treiben präfixbasierte Funktionen an: Autovervollständigung und Suchvorschläge, Rechtschreibprüfung, IP-Routing-Tabellen und Wörterbuchsuchen. Überall, wo du schnell beantworten musst „beginnt ein gespeichertes Wort mit diesem Präfix?", glänzt ein Trie.
Wie ist die Zeitkomplexität eines Tries?
Einfügen, Suchen und Präfixabfragen laufen alle in
O(m), wobei m die Länge des Worts oder Präfixes ist - unabhängig davon, wie viele Wörter gespeichert sind. Der Kompromiss ist der Speicher: Ein Trie kann viel Platz beanspruchen, obwohl gemeinsame Präfixe nur einmal gespeichert werden.Was ist der Unterschied zwischen einem Trie und einer Hashtabelle?
Eine Hashtabelle bietet durchschnittlich
O(1)-Suche nach ganzen Schlüsseln, kann aber keine Präfixabfragen beantworten. Ein Trie ist pro Suche etwas langsamer, unterstützt aber von Natur aus Präfixsuche, geordneten Durchlauf und Autovervollständigung - der Grund, warum er dafür bevorzugt wird.Wann sollte ich einen Trie statt eines binären Suchbaums verwenden?
Verwende einen Trie, wenn deine Schlüssel Zeichenketten sind und du Präfixsuchen brauchst: Er läuft in
O(m) pro Operation über die Schlüssellänge, während ein balancierter BST O(m log n) kostet, weil jeder Vergleich die Zeichenkette durchläuft und es log n davon gibt. Ein BST ist die bessere Wahl, wenn die Schlüssel nicht zeichenkettenartig sind oder der Speicheraufwand wichtiger ist als die Präfixgeschwindigkeit.Wie behandelt man das Ende eines Worts in einem Trie?
Jeder Knoten trägt eine Wortende-Markierung, die nur gesetzt wird, wenn dort ein vollständig eingefügtes Wort endet. Ohne sie könntest du ein gespeichertes Wort nicht von einem bloßen Präfix unterscheiden - nach dem Einfügen von
card existiert der Knoten für car, sollte aber nur dann als Wort gemeldet werden, wenn car ebenfalls eingefügt wurde.Sparen Tries durch das Teilen von Präfixen immer Speicher?
Nicht immer. Das Teilen hilft nur, wenn sich viele Schlüssel überschneiden; bei langen, unterschiedlichen Schlüsseln kann ein Trie weit mehr Speicher verbrauchen als eine Hash-Menge, da jedes Zeichen zu einem eigenen Knoten mit Kind-Zeigern wird. Wenn der Platz das Problem ist, führt ein komprimierter Radix-Baum Ketten mit einem einzigen Kind zusammen, um diesen Mehraufwand zu senken.
Verwandte Ressourcen
Mehr Visualisierungen
