---
title: "Trie (префиксное дерево)"
url: https://algopath.pro/ru/patterns/trie
language: ru
summary: "Слова с общим префиксом делят между собой один и тот же путь от корня. Поиск стоит ровно столько, какова длина этого слова."
updated: 2026-08-24
---

# Trie (префиксное дерево)

Слова с общим префиксом делят между собой один и тот же путь от корня. Поиск стоит ровно столько, какова длина этого слова.

## Trie (префиксное дерево): как это работает?

Корень означает пустой префикс. Своего символа он не несёт.

Каждое ребро хранит один символ. Путь от корня складывается в префикс.

Вставка идёт по слову символ за символом. Отсутствующий потомок создаётся по дороге.

Последний узел слова получает флаг. Без него префикс выглядел бы как сохранённое слово.

Поиск идёт тем же путём вниз. Отсутствующий потомок означает, что слова нет.

Запрос по префиксу останавливается раньше и сообщает успех. Всё под этим узлом начинается с префикса.

- `корень в c` Вставляем car и cat. Первый символ создаёт одного потомка.
- `c, a, r с флагом` Три узла и один флаг конца складываются в car.
- `вставка cat: c и a уже есть` Общий префикс проходится, а не строится заново.
- `a в t с флагом` На второе слово добавляется всего один узел.
- `поиск ca: флага нет` Узел существует, но словом не является. Это только префикс.

## Trie (префиксное дерево): когда применять?

- автодополнение или typeahead по множеству строк
- самый длинный общий префикс среди слов
- вставка, поиск и проверка префикса в наборе слов
- сопоставление с большим фиксированным словарём по префиксу

## Trie (префиксное дерево): с чем путают?

- **Хеш-множество / словарь** - Словарь сравнивает только целые ключи. Trie отвечает ещё и на запросы по префиксу.
- **Двоичное дерево поиска** - Дерево поиска сравнивает целые ключи и выбирает сторону. Trie идёт по одному символу.
- **Поиск слова в матрице (DFS/backtracking по сетке)** - Поиск многих слов в сетке использует trie для обрезки. Та страница про сам обход сетки.
- **DP на строках (word break)** - Разбиение на слова использует trie для проверки куска. Решение о разрезе лежит в таблице.

## Trie (префиксное дерево): сложность по времени и памяти

Слово длины m стоит O(m) на вставку или поиск. Память O(суммы символов) по всем словам.

## Trie (префиксное дерево): разбор примера

### Замена слов их корнями

Дан словарь корней и предложение. Замените каждое слово самым коротким корнем, с которого оно начинается.

Слово без подходящего корня остаётся как есть.

Сначала вставьте все корни в trie.

Потом ведите каждое слово вниз по дереву. Останавливайтесь на первом флаге конца, это и есть кратчайший корень.

```javascript
function replaceWords(dictionary, sentence) {
    const root = { children: {} };

    for (const word of dictionary) {
        let node = root;
        for (const c of word) {
            node.children[c] = node.children[c] ?? { children: {} };
            node = node.children[c];
        }
        node.end = true; // this node closes a real word
    }

    return sentence
        .split(" ")
        .map((word) => {
            let node = root;
            let prefix = "";

            for (const c of word) {
                if (!node.children[c]) return word; // no root matches
                node = node.children[c];
                prefix += c;
                if (node.end) return prefix; // the first flag is the shortest root
            }

            return word;
        })
        .join(" ");
}
```

## Trie (префиксное дерево): частые ошибки

- **Не ставят флаг конца** Тогда сохранённый префикс не отличить от сохранённого слова. Любой поиск превращается в запрос по префиксу.
- **Смешивают флаг с потомками** Флаг под ключом, похожим на букву, портит дерево. Держите потомков в отдельном словаре.
- **Строят его ради горстки слов** Trie тратит память на каждый символ. До нескольких тысяч слов проще множество.
- **Считают алфавит фиксированным** Массив на 26 ячеек ломается на цифрах и диакритике. Берите словарь, если вход не из обычных букв.

## Trie (префиксное дерево): задачи с собеседований

- **Реализация trie** Вставка, поиск и запрос по префиксу.
- **Замена слов корнями** Обход останавливается на первом флаге конца.
- **Добавление и поиск слов** Точка означает перебор всех потомков на уровне.
- **Поиск слов в сетке II** Trie заранее обрезает обход сетки.
- **Наибольший общий префикс** Спускайтесь, пока потомок ровно один.
- **Максимальный XOR двух чисел** Двоичный trie, построенный по битам.
- **Система автодополнения** Ранжируйте слова, лежащие под узлом префикса.

## JavaScript

```javascript
class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}
class Trie {
    constructor() { this.root = new TrieNode(); }
    insert(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) node.children.set(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
    }
    search(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) return false;
            node = node.children.get(c);
        }
        return node.isEnd;
    }
}
```

## Python

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end
```

## PHP

```php
class TrieNode {
    public array $children = [];
    public bool $isEnd = false;
}
class Trie {
    private TrieNode $root;
    public function __construct() { $this->root = new TrieNode(); }
    public function insert(string $word): void {
        $node = $this->root;
        foreach (str_split($word) as $c) {
            $node->children[$c] ??= new TrieNode();
            $node = $node->children[$c];
        }
        $node->isEnd = true;
    }
    public function search(string $word): bool {
        $node = $this->root;
        foreach (str_split($word) as $c) {
            if (!isset($node->children[$c])) return false;
            $node = $node->children[$c];
        }
        return $node->isEnd;
    }
}
```