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

Trie (prefix tree)

O(len) per op

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

Elman HuseynovОбновлено 17 окт. 2026 г.

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

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

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

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

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

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

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

Источники: Википедия: Префиксное дерево, Fredkin (1960), Trie memory (англ.)

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

Вставка и поиск слов в префиксном дереве

insert("car"), insert("cat"), insert("dog"), search("cat"), search("ca"), search("cow")

на ребре буква, в узле префикс, набранный от корня, ✓ = isEnd (здесь кончается целое слово)

word = ""node = -search = -

Сохраняем ["car", "cat", "dog"], чтобы искать их буква за буквой. Корень означает пустой префикс.

1 / 23

Trie (префиксное дерево): шаблон кода

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;
    }
}

class TrieNode {
    children = new Map<string, TrieNode>();
    isEnd = false;
}

class Trie {
    private root = new TrieNode();

    insert(word: string): void {
        let node = this.root;
        for (const c of word) {
            let next = node.children.get(c);
            if (!next) {
                next = new TrieNode();
                node.children.set(c, next);
            }
            node = next;
        }
        node.isEnd = true;
    }

    search(word: string): boolean {
        let node = this.root;
        for (const c of word) {
            const next = node.children.get(c);
            if (!next) return false;
            node = next;
        }
        return node.isEnd;
    }
}

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

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;
    }
}

    public static class TrieNode {
        public Map<Character, TrieNode> children = new HashMap<>();
        public boolean isEnd = false;
    }

    public static class Trie {
        private final TrieNode root = new TrieNode();

        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new TrieNode());
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.get(c);
                if (node == null) return false;
            }
            return node.isEnd;
        }
    }

    public class TrieNode {
        public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
        public bool isEnd = false;
    }

    public class Trie {
        private readonly TrieNode root = new TrieNode();

        public void Insert(string word) {
            var node = root;
            foreach (char c in word) {
                if (!node.children.ContainsKey(c)) node.children[c] = new TrieNode();
                node = node.children[c];
            }
            node.isEnd = true;
        }

        public bool Search(string word) {
            var node = root;
            foreach (char c in word) {
                if (!node.children.TryGetValue(c, out var next)) return false;
                node = next;
            }
            return node.isEnd;
        }
    }

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

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

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

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

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

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

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 (префиксное дерево)» нужен, когда в условии есть слова «автодополнение или typeahead по множеству строк», «самый длинный общий префикс среди слов» или «вставка, поиск и проверка префикса в наборе слов». Решение на нём обычно укладывается в O(len) per op.

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Trie (префиксное дерево)» чаще всего путают с этими паттернами: Хеш-множество / словарь, Двоичное дерево поиска, Поиск слова в матрице (DFS/backtracking по сетке) и DP на строках (word break).

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

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

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

Паттерн «Trie (префиксное дерево)» решает такие задачи с собеседований: Реализация trie, Замена слов корнями, Добавление и поиск слов, Поиск слов в сетке II, Наибольший общий префикс, Максимальный XOR двух чисел и Система автодополнения.

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