Дерево префиксов (Trie)
Последнее обновление
Trie (произносится «трай»), или дерево префиксов, хранит множество строк по их символам: каждое ребро помечено символом, а путь от корня складывается в префикс. Слова с общим префиксом разделяют одни и те же узлы, поэтому «car», «card» и «care» повторно используют путь c-a-r. Нажмите «Воспроизвести» выше, чтобы увидеть, как слова вставляются по одному символу за раз, ветвясь только там, где различаются.
Поскольку поиск проходит по одному узлу на символ, поиск слова длины m занимает O(m) независимо от того, сколько слов хранит дерево. Это делает деревья префиксов идеальными для автодополнения, проверки орфографии и поиска по префиксу.
Сложность по времени и памяти
| Операция | Сложность | Примечания |
|---|---|---|
| Вставка | O(m) | m = длина слова |
| Поиск | O(m) | Один шаг на символ |
| Запрос префикса | O(m) | Пройти до узла префикса |
| Память | O(total chars) | Общие префиксы хранятся один раз |
Шаг за шагом (вставка)
| Шаг | Что происходит |
|---|---|
| 1 | Начните с корневого узла. |
| 2 | Для каждого символа слова ищите подходящее дочернее ребро. |
| 3 | Если оно есть, следуйте по нему (повторно используя общий префикс). |
| 4 | Если нет, создайте новый дочерний узел для этого символа. |
| 5 | После последнего символа отметьте этот узел как конец слова. |
Разобранный пример
Вставка ["car", "card", "care"] в пустое дерево:
| Шаг | Структура | Действие |
|---|---|---|
Вставить car | root → c → a → r✓ | Подходящих дочерних узлов нет, поэтому создайте c, a, r и отметьте r как конец слова. |
Вставить card | root → c → a → r✓ → d✓ | Повторно используйте существующий путь c-a-r, затем создайте один новый дочерний узел d и отметьте его как конец слова. |
Вставить care | root → c → a → r✓ → {d✓, e✓} | Повторно используйте c-a-r, ответвитесь от r новым дочерним узлом e и отметьте e как конец слова. |
Найти care | root → c → a → r → e✓ | Пройдите c, a, r, e; последний узел отмечен как конец слова, значит care присутствует. |
Найти ca | root → c → a | Путь существует, но a не отмечен как конец слова, поэтому ca — это префикс, но не сохранённое слово. |
Когда использовать дерево префиксов
| Использовать, когда | Избегать, когда |
|---|---|
| Нужны запросы по префиксу или автодополнение по множеству строк. | Нужен только поиск целых ключей — хеш-таблица быстрее и легче. |
| Многие хранимые слова имеют общие префиксы, поэтому узлы переиспользуются. | Ключи длинные и редко пересекаются, тратя по узлу на каждый символ. |
| Нужно возвращать ключи в отсортированном порядке через обход. | Память ограничена — указатели на детей у каждого узла дают значительные накладные расходы. |
| Стоимость поиска должна зависеть от длины ключа, а не от размера набора данных. | Алфавит огромен (например, весь Unicode), а дети хранятся плотно. |
Код Trie (Prefix Tree)
Чистая, готовая к запуску реализация Trie (Prefix Tree) на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Trie (Prefix Tree) на 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) на 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) на 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) на 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) на 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}Часто задаваемые вопросы о деревьях префиксов
Для чего используется дерево префиксов?
Деревья префиксов обеспечивают функции на основе префиксов: автодополнение и подсказки поиска, проверку орфографии, таблицы IP-маршрутизации и словарные запросы. Везде, где нужно быстро отвечать на вопрос «начинается ли какое-либо хранимое слово с этого префикса?», trie проявляет себя лучше всего.
Какова временная сложность дерева префиксов?
Вставка, поиск и запросы префикса выполняются за
O(m), где m — длина слова или префикса, независимо от того, сколько слов хранится. Компромисс — память: дерево может занимать много места, хотя общие префиксы хранятся только один раз.В чём разница между деревом префиксов и хеш-таблицей?
Хеш-таблица даёт в среднем поиск целых ключей за
O(1), но не может отвечать на запросы по префиксу. Trie немного медленнее при поиске, но естественно поддерживает поиск по префиксу, упорядоченный обход и автодополнение — по этой причине его предпочитают для таких случаев.Когда стоит использовать дерево префиксов вместо двоичного дерева поиска?
Используйте trie, когда ключи — это строки и нужны поиски по префиксу: оно работает за
O(m) на операцию по длине ключа, тогда как сбалансированное BST стоит O(m log n), потому что каждое сравнение просматривает строку, а таких сравнений log n. BST — лучший выбор, когда ключи не строкового вида или когда накладные расходы на память важнее скорости работы с префиксами.Как обрабатывается конец слова в дереве префиксов?
Каждый узел несёт флаг конца слова, который устанавливается только тогда, когда там заканчивается полностью вставленное слово. Без него нельзя отличить хранимое слово от простого префикса — например, после вставки
card узел для car существует, но должен считаться словом только если car тоже было вставлено.Всегда ли деревья префиксов экономят память за счёт разделения префиксов?
Не всегда. Разделение помогает лишь тогда, когда многие ключи пересекаются; с длинными различными ключами trie может использовать намного больше памяти, чем хеш-множество, поскольку каждый символ становится отдельным узлом с указателями на детей. Если проблема в памяти, сжатое radix-дерево объединяет цепочки с единственным ребёнком, чтобы уменьшить эти накладные расходы.
Связанные ресурсы
Больше визуализаций
