105
правок
Изменения
Бор
,ё
===Обозначения===
Введем следующие обозначения:
*<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>0</tex>''NULL''.
'''struct''' vertex:
'''vertex''' next[n + 1<tex>| \Sigma |</tex>]
'''bool''' isTerminal
**Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новое ребро и вершину для символа строки <tex>P_i</tex>.
*Конец.
Поскольку на каждую вершину приходится <tex>O(1| \Sigma |)</tex> памяти, то использование памяти есть <tex>O(n| \Sigma |)</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(kn|S\Sigma |)</tex> памяти).
==См. также==
