Изменения

'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') — {{---}} структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево]] с символами на [[Основные определения теории графов | рёбрах]]. Строки получаются прохождением из корня по последовательной записью всех символов, хранящихся на [[Основные определения теории графов | рёбрамрёбрах]], записывая соответствующие им символы, до между корнем бора и терминальной вершинывершиной. Размер бора линейно

Бор для набора образцов <tex> \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} </tex>:<br />

Пусть ===Обозначения===Введем следующие обозначения:*<tex>\Sigma</tex> {{---}} используемый алфавит;*<tex>P = \{P_1,...\ldots,P_k\} </tex> — {{---}} набор строкнад <tex>\Sigma</tex>, называемый словаремсловарём;*<tex>n = \sum_{i=1}^{k}\limits |P_i|</tex> {{---}} сумма длин строк.

Пусть <tex>n = \sum_{i=1}^{k|P_i|}\limits</tex>Бор храним как набор вершин, у каждой из которых есть метка, обозначающая, является ли вершина терминальной и указатели (рёбра) на другие вершины или на ''NULL''.

#Начинаем с *Начало.*'''Шаг 1.''' Создадим [[Дерево, эквивалентные определения | деревадерево]] из одной вершины (в нашем случае корня).#*'''Шаг 2.''' Добавление элементов в дерево.**Добавляем шаблоны <tex>P_i</tex> один за другим.#Следуем из корня по [[Основные определения теории графов | рёбрам]], отмеченным буквами из <tex>P_i</tex>, пока возможно.#**Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex> и отмечаем вершину <tex>v</tex> как терминальную.#**Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра новое ребро и вершины вершину для всех оставшихся символов символа строки <tex>P_i</tex>.*Конец.Построение занимает, очевидно, <tex>O(|P_1| + \ldots + |P_k|) = O(n)</tex> времени, так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>.

Это занимает, очевидно, Поскольку на каждую вершину приходится <tex>O (|P_1| + \ldots + |P_kSigma |) = </tex> памяти, то использование памяти есть <tex>O (n| \Sigma |)</tex> времени.

===Суффиксный бор==={{main|Суффиксный бор}}Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | поиска подстроки в строке]], если построить его на множестве суффиксов исходной строки. ===Цифровой бор==={{main|Сверхбыстрый цифровой бор}} ==Использование бора=====Поиск строки в бору===Поиск строки {{Задача|definition = Требуется найти слово <tex>S</tex> в бору: начинаем в корнесловаре.}}При решении этой задачи, идем обход бора совершается из его корня по [[Основные определения теории графов | рёбрам]], отмеченным символами строки <tex>S</tex>, пока возможно.Если с последним символом <tex>S</tex> мы приходим в терминальную вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.

==Сжатый бор=Использование бора в качестве ассоциативного массива===Сжатый Благодаря тому, что бор — позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура данных для хранения набора строк, отличающаяся от бораследующим улучшением: если у некоторой вершины исходящая степень равна 1, то этувершину, используют [[Основные определения теории графов Дерево поиска, наивная реализация | ребродвоичное дерево поиска]], входящее в нее, и или [[Основные определения теории графов Хеш-таблица | реброхеш-таблицу]]. ====Достоинства====Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, исходящее которые каждая из нее, можно объединить в одно[[Основные определения теории графов | ребро]] с более чем одним символомструктур не может делать по отдельности.

{| class="wikitable" style=Использование бора в качестве "width:10cm" border=1|+| || '''Бор''' || '''Дерево''' || '''Хеш-таблица'map''|-|-align="center" bgcolor=#FFFFFF| ''Добавление элемента'' Мы можем ввести для каждой вершины поле | align="center" style="background: #ddffdd;" | <tex>valueO(|S|)</tex>. Например, мы имеем | align="center" style="background: #ffdddd;" |<tex>O(|S|\log k)</tex>map| align="center" style="background: #ddffdd;" | <string, value.typetex>O(|S|)</tex>. Будем искать ключ, спускаясь по бору. Соответственно, если на какой|-то вершине нет пометки, что вершина является концом слова, то объекта align="center" bgcolor=#FFFFFF| ''Получение всех ключей в отсортированном порядке'' | align="center" style="background: #ddffdd;" | <tex>mapO(k)</tex> нет. Если хотим добавить его, то ставим в вершину флаг конца слова и заносим значение.Работать такой алгоритм будет за | align="center" style="background: #ddffdd;" | <tex>O(k)</tex>, где | align="center" style="background: #ffdddd;" | <tex>O(k\log k)</tex> - количество добавленных |} ====Недостатки====Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.#Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у словнет пересечений по префиксу, тогда бор будет использовать <tex>O(n| \Sigma |)</tex> памяти).