Изменения

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

*<tex>\Sigma</tex> {{---}} используемый алфавит;*<tex>P = \{P_1,\ldots,P_k\} </tex> — {{---}} набор строкнад <tex>\Sigma</tex>, называемый словаремсловарём;*<tex>n = \sum_{i=1}^{k|P_i|}\limits |P_i|</tex>{{---}} сумма длин строк. Бор храним как набор вершин, у каждой из которых есть метка, обозначающая, является ли вершина терминальной и указатели (рёбра) на другие вершины или на ''NULL''.   '''struct''' vertex: '''vertex''' next[<tex>| \Sigma |</tex>] '''bool''' isTerminal 

#Начинаем с *Начало.*'''Шаг 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(k| \Sigma |)</tex> памяти, то использование памяти есть <tex>O(nkn| \Sigma |)</tex>.

===Другие модификацииСуффиксный бор==={{main|Суффиксный бор}}Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | поиска подстроки в строке]], если построить его на множестве суффиксов исходной строки.<ref>Сжатое суффиксное дерево</ref>

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

==Использование бора=====Поиск строки в бору===

Требуется найти слово <tex>S</tex> в словаре.

Начинаем в корнеПри решении этой задачи, идем обход бора совершается из его корня по [[Основные определения теории графов | рёбрам]], отмеченным символами строки <tex>S</tex>, пока возможно.Если с последним символом <tex>S</tex> мы приходим в терминальную вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.

===Использование бора в качестве ассоциативного массива===Существует множество реализаций Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, начиная от обычного массива (храним массив в отсортированном состояниикогда требуется такая структура, при добавлении элементато используют [[Дерево поиска, все элементы с большим значением сдвигаются) и заканчивая наивная реализация | двоичное дерево поиска]] или [[Хеш-таблица | хеш-таблицами таблицу]]. ====Достоинства====Бор объединяет некоторые преимущества этих структур данных и деревьями поиска. Ещё одну реализацию можно сделать используя бор или сжатый борпозволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.Начнём с очевидных минусов{| class="wikitable" style="width:10cm" border=1|+| || '''Бор''' || '''Дерево''' || '''Хеш-таблица'''|-|-align="center" bgcolor=#FFFFFF| ''Добавление элемента'' | align="center" style="background: #ddffdd;" | <tex>O(|S|)</tex>| align="center" style="background: #ffdddd;" |<tex>O(|S|\log k)</tex> | align="center" style="background: #ddffdd;" | <tex>O(|S|)</tex>|-align="center" bgcolor=#FFFFFF| ''Получение всех ключей в отсортированном порядке'' | align="center" style="background: #ddffdd;" | <tex>O(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> действий в худшем случае (например хранятся слова <tex>"a", "aa", "aaa", "aaaa", ...</tex>памяти), где <tex>n</tex> - количество словПлюсы:# Достаточно простая реализация.# Операции добавления имеют меньшую константу (из-за отсутствия всевозможных операций балансировки), чем у двоичных деревьев поиска, поэтому в среднем данная реализация может работать быстрее.# Сортировка элементов гарантируется уже самим построением бора.