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

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

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

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

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

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

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

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

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

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

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 (префиксное дерево): когда применять?

Эти формулировки в условии ведут сюда:

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

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

• Хеш-множество / словарь (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: Trie заранее обрезает обход сетки.
• Наибольший общий префикс: Спускайтесь, пока потомок ровно один.
• Максимальный XOR двух чисел: Двоичный trie, построенный по битам.
• Система автодополнения: Ранжируйте слова, лежащие под узлом префикса.

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

O(len) per op

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