Описание
Бор - структура данных для эффективного хранения набора слов конкретного алфавита. Обычно его пишут на ориентированном ацикличном дереве, одна вершинка обозначается корнем, из каждой вершины могут выходить ребра, на которых написан символ алфавита, некоторые вершины помечены терминальными, бор содержит слово w, если есть путь из корня в терминальную вершину, такой, что если сконкатенировать символы на ребрах, то мы получим слово w.
Этот бор содержит слова:
- he
- she
- his
- hers
Зачем он нужен
Бор позволяет вам максимально сжать данные, если две строчки в боре имеют одинаковый префикс, то для их префиксов не будет создано копий, что позволит вам сэкономить память, если у вас маленький алфавит. Также бор легко решает проблему быстрой проверки наличия слова в алфавите, это можно сделать за проходом от корня.
Примечание
Бор является примитивным случаем более сложной структуры данных - детерменированных конечных автоматов, все что верно для них, верно и для бора.