Бор

Материал из Algocode wiki
Перейти к: навигация, поиск

Префиксное дерево

Префиксное дерево или бор (англ. trie) — это структура данных для компактного хранения строк.

Он устроен в виде дерева, где на ребрах между вершинами написана символы, а некоторые вершины помечены терминальными. Бор хранит ровно те строки, которые получаются, если выписать подряд все буквы на путях от корня до терминальных вершин. Trie example.png

Бор можно удобно использовать для разных задач:

  • Хранение строк — занимает гораздо меньше места, чем массив или сет строк.
  • Сортировка строк — по бору можно пройтись dfs-ом и вывести все строки в лексикографическом порядке.
  • Сет строк — как мы увидим, в нем легко добавлять и удалять слова, а также проверять, если ли слово в боре.

Реализация

Бор состоит из ссылающихся друг на друга вершин. В вершине обычно хранится такая информация:

  • терминальная ли вершина,
  • ссылки на детей,
  • возможно, какая-нибудь дополнительная зависящая от задачи информация о слове, если вершина терминальная. Например, количество таких слов — так можно реализовать мультисет.
const int k = 26;

struct Vertex {
    Vertex* to[k] = {0};
    bool terminal = 0;
};

Vertex *root = new Vertex();

Чтобы добавить слово в бор, нужно пройти от корня по символам слова. Если перехода по для очередного символа нет — создать его, иначе пройти по уже существующему. Последнюю вершину нужно пометить терминальной.

void add_string (string &s) {
    v = root;
    for (char c : s) {
        c -= 'a';
        if (!v->to[c]) 
            v->to[c] = new Vertex();
        v = v->to[c];
    }
    v->terminal = true;
}

Чтобы проверить, есть ли слово в боре, нужно пройти от корня по символам слова. Если в конце оказались в терминальной вершине — то есть. Если оказались в нетерминальной или когда-нибудь потребовалось пройтись по несуществущей ссылке — то нет.

Удалить слово можно лениво, просто дойдя до него и убрав флаг терминальности.

Как хранить ссылки

Хранить ссылки на детей не обязательно в массиве. Возможно, наш алфавит большой — у нас тогда просто не хватит памяти инициализировать столько массивов, большинство из которых будут пустыми.

В этом случае можно придумать какой-нибудь другой способ хранить отображение из символа в ссылку на вершину, например бинарном дереве (map) или хэш-таблице (unordered_map). Они будут работать дольше (но лишь в константу раз), но зато потребление памяти в них будет линейным. У map-а есть ещё одно преимущество, что он хранит ссылки уже отсортированными по символам — так можно отсортировать строки, например.

Учитывайте, что писать бор можно по-разному, особенно когда решаете задачи с жестокими ограничениями.

Полезные улучшения