Изменения
Бор
,Нет описания правки
==Поиск строки в бору==
Поиск строки <tex>S</tex> в бору: начинаем в корне, идем по ребрам[[Основные определения теории графов | рёбрам]], отмеченным символами <tex>S</tex>, пока возможно.
Если с последним символом <tex>S</tex> мы приходим в вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.
Если в какой-то момент [[Основные определения теории графов | ребра]], отмеченного нужным символом, не находится, то строки <tex>S</tex> в словаре нет.
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.
Сжатый бор — структура данных для хранения набора строк, отличающаяся от бора
следующим улучшением: если у некоторой вершины исходящая степень равна 1, то эту
вершину, [[Основные определения теории графов | ребро]], входящее в нее, и [[Основные определения теории графов | ребро]], исходящее из нее, можно объединить в одно[[Основные определения теории графов | ребро ]] с более чем одним символом.
==См. также==
