Trie (drzewo prefiksowe)
Ostatnia aktualizacja
Trie (czytaj „traj”), czyli drzewo prefiksowe, przechowuje zbiór napisów według ich znaków: każda krawędź ma etykietę w postaci znaku, a ścieżka od korzenia tworzy prefiks. Słowa o wspólnym prefiksie korzystają z tych samych węzłów, więc „car”, „card” i „care” używają tej samej ścieżki c-a-r. Naciśnij Odtwórz powyżej i zobacz, jak słowa są wstawiane znak po znaku i rozgałęziają się tylko tam, gdzie się różnią.
Wyszukiwanie przechodzi przez jeden węzeł na znak, więc znalezienie słowa o długości m zajmuje O(m) bez względu na to, ile słów zawiera trie. Dzięki temu trie świetnie nadaje się do autouzupełniania, sprawdzania pisowni i wyszukiwania po prefiksie.
Złożoność czasowa i pamięciowa
| Operacja | Złożoność | Uwagi |
|---|---|---|
| Wstawianie | O(m) | m = długość słowa |
| Wyszukiwanie | O(m) | Jeden krok na znak |
| Zapytanie o prefiks | O(m) | Przejście do węzła prefiksu |
| Pamięć | O(total chars) | Wspólne prefiksy przechowywane tylko raz |
Krok po kroku (wstawianie)
| Krok | Co się dzieje |
|---|---|
| 1 | Zacznij od korzenia. |
| 2 | Dla każdego znaku słowa szukaj pasującej krawędzi do dziecka. |
| 3 | Jeśli istnieje, przejdź po niej (korzystając ze wspólnego prefiksu). |
| 4 | Jeśli nie, utwórz nowy węzeł potomny dla tego znaku. |
| 5 | Po ostatnim znaku oznacz ten węzeł jako koniec słowa. |
Przykład krok po kroku
Wstawiamy ["car", "card", "care"] do pustego trie:
| Krok | Struktura | Działanie |
|---|---|---|
Wstaw car | root → c → a → r✓ | Nie ma pasujących dzieci, więc utwórz c, a, r i oznacz r jako koniec słowa. |
Wstaw card | root → c → a → r✓ → d✓ | Użyj istniejącej ścieżki c-a-r, potem utwórz jedno nowe dziecko d i oznacz je jako koniec słowa. |
Wstaw care | root → c → a → r✓ → {d✓, e✓} | Użyj c-a-r, odgałęź się od r nowym dzieckiem e i oznacz e jako koniec słowa. |
Szukaj care | root → c → a → r → e✓ | Przejdź przez c, a, r, e; ostatni węzeł jest oznaczony jako koniec słowa, więc care jest w trie. |
Szukaj ca | root → c → a | Ścieżka istnieje, ale a nie jest oznaczony jako koniec słowa, więc ca jest prefiksem, a nie zapisanym słowem. |
Kiedy używać trie
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Potrzebujesz zapytań o prefiks lub autouzupełniania w zbiorze napisów. | Wyszukujesz tylko całe klucze: tablica mieszająca jest szybsza i lżejsza. |
| Wiele zapisanych słów ma wspólne prefiksy, więc węzły są współdzielone. | Klucze są długie i rzadko się pokrywają, co marnuje jeden węzeł na znak. |
| Chcesz otrzymywać klucze w kolejności posortowanej przez przejście drzewa. | Pamięci jest mało: wskaźniki na dzieci w każdym węźle dodają spory narzut. |
| Koszt wyszukiwania ma zależeć od długości klucza, a nie od rozmiaru danych. | Alfabet jest ogromny (np. cały Unicode), a dzieci są przechowywane gęsto. |
Trie (Prefix Tree): kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Trie (Prefix Tree) w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Trie (Prefix Tree): kod (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): kod (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): kod (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): kod (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): kod (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: najczęstsze pytania
Do czego służy trie?
Trie napędza funkcje oparte na prefiksach: autouzupełnianie i podpowiedzi wyszukiwania, sprawdzanie pisowni, tablice routingu IP i wyszukiwanie w słownikach. Wszędzie tam, gdzie trzeba szybko odpowiadać na pytanie „czy któreś zapisane słowo zaczyna się od tego prefiksu?”, trie sprawdza się znakomicie.
Jaka jest złożoność czasowa trie?
Wstawianie, wyszukiwanie i zapytania o prefiks działają w czasie
O(m), gdzie m to długość słowa lub prefiksu, niezależnie od liczby zapisanych słów. Ceną jest pamięć: trie może zajmować dużo miejsca, choć wspólne prefiksy są przechowywane tylko raz.Czym różni się trie od tablicy mieszającej?
Tablica mieszająca oferuje średnio wyszukiwanie całych kluczy w
O(1), ale nie odpowie na zapytania o prefiks. Trie jest nieco wolniejsze przy pojedynczym wyszukiwaniu, za to naturalnie obsługuje wyszukiwanie po prefiksie, przechodzenie w kolejności i autouzupełnianie, dlatego to ono jest wybierane w takich zastosowaniach.Kiedy użyć trie zamiast drzewa BST?
Wybierz trie, gdy kluczami są napisy i potrzebujesz wyszukiwania po prefiksie: każda operacja kosztuje
O(m) względem długości klucza, a zrównoważone drzewo BST kosztuje O(m log n), bo każde porównanie przechodzi przez napis, a porównań jest log n. Drzewo BST jest lepszym wyborem, gdy klucze nie są napisami albo gdy narzut pamięci ma większe znaczenie niż szybkość wyszukiwania po prefiksie.Jak oznacza się koniec słowa w trie?
Każdy węzeł ma flagę końca słowa, ustawianą tylko wtedy, gdy w tym miejscu kończy się całe wstawione słowo. Bez niej nie da się odróżnić zapisanego słowa od samego prefiksu: na przykład po wstawieniu
card węzeł dla car istnieje, ale powinien być zgłoszony jako słowo tylko wtedy, gdy car też zostało wstawione.Czy trie zawsze oszczędza pamięć dzięki wspólnym prefiksom?
Nie zawsze. Współdzielenie pomaga tylko wtedy, gdy wiele kluczy się pokrywa; przy długich, różnych kluczach trie może zużyć znacznie więcej pamięci niż zbiór oparty na haszowaniu, bo każdy znak staje się osobnym węzłem ze wskaźnikami na dzieci. Jeśli liczy się pamięć, skompresowane drzewo radix scala łańcuchy węzłów z jednym dzieckiem i zmniejsza ten narzut.
Powiązane materiały
Więcej wizualizacji
