Опредение

Бор, или префиксное дерево, - структура данных для эффективного хранения и обработки строк. Вершины в боре соответствуют отдельным символам. В каждой вершине хранится также числовое значение, обозначающее, сколько строк заканчиваются в этой вершине. Строки представляются в виде путей по бору от корня (пустой строки) до последнего символа.

Бор

В боре, изображённом выше, хранятся следующие строки:

  • “to” - 7 экземпляров
  • “tea” - 3 экземпляра
  • “ted” - 4 экземпляра
  • “ten” - 12 экземпляров
  • “A” - 15 экземпляров
  • “i” - 11 экземпляров
  • “in” - 5 экземпляров
  • “inn” - 9 экземпляров

Таким образом, в каждой вершине бора хранится количество строк, заканчивающихся в этой вершине, и указатели на дочерние вершины, каждая из которых соответствует определённому символу.

Реализация

При реализации бора используются указатели и динамическое выделение памяти. Предполагается владение этими концепциями языка C++.

Во всех предыдущих реализациях структур данных деревья представлялись или в виде массива с формулами перехода, или в виде списка смежности. Для реализации бора необходимо “реальное” представление деревьев, каждая вершина в которых - отдельный элемент, которому соответствует собственный тип данных. В каждой вершине хранится массив указателей на дочерние вершины.

Реализуем тип данных для представления вершин в дереве:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct node {
    node *next[26];     //Массив указателей на следующие вершины
                        //next[i] - указатель на следующую вершину, соответствующую символу ('a' + i)
                        //(предполагается, что используются только строчные латинские буквы)

    int strings;        //Количество строк, заканчивающихся в этой вершине.

    node() {
        for (int i = 0; i < 26; i++) {   //изначально заполняем next нулевыми указателями,
            next[i] = nullptr;           //так как следующие вершины ещё не созданы
        }

        strings = 0;
    }
};

Для добавления в бор очередной строки, нужно создать все необходимые вершины, если они ещё не созданы, и увеличить счётчик строк в последней вершине на \(1\):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
node *root = new node();     //корневая вершина бора, соответствующая пустой строке.

void add(const string& s) {
    node *cur_v = root;     //текущая вершина

    for (int i = 0; i < s.length(); i++) {
        char c = s[i];

        if (cur_v->next[c - 'a'] == nullptr) {
            cur_v->next[c - 'a'] = new node();
        }

        cur_v = cur_v->next[c - 'a'];
    }

    cur_v->strings++;
}

Проверки наличия в боре строки реализуется похожим образом:

1
2
3
4
5
6
7
8
9
10
11
12
bool has(const string& s) {
    node *cur_v = root;

    for (int i = 0; i < s.length(); i++) {
        cur_v = cur_v->next[s[i] - 'a'];
        if (cur_v == nullptr) {
            return false;
        }
    }

    return cur_v->strings > 0;
}

С бором можно выполнять множество операций, но большинство из них сводятся к обходу всех строк с помощью DFS. Для примера давайте реализуем функцию, выводящую все строки, содержащиеся в боре:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string cur_str = "";

void write(node *v = root) {
    for (int i = 0; i < v->strings; i++) {
        cout << cur_str << endl;
    }

    for (int i = 0; i < 26; i++) {
        if (v->next[i] != nullptr) {
            cur_str.push_back('a' + i);
            write(v->next[i]);
            cur_str.pop_back();
        }
    }
}

Применение

Бор является достаточно легко модифицируемой структурой данных, и в зависимости от значений, хранимых в вершинах, и способа обхода с его помощью можно реализовать множество различных операций. Конкретная реализация бора варьируется от задачи к задаче.

Бор также используется как вспомогательная структура данных для более сложных строковых алгоритмов, в частности, алгоритма Ахо-Корасик.