313
правок
Изменения
Бор
,→Использование бора в качестве ассоциативного массива
==Использование бора в качестве ассоциативного массива==
Мы можем ввести для каждой вершины поле <tex>\mathtt{value} \</tex>. Например, мы имеем <tex>\mathtt{map}</tex><tex><</tex><tex>\mathtt{string}\ , \mathtt{type}\ </tex><tex>></tex>. Будем искать ключ, спускаясь по бору. Соответственно, если на какой-то вершине нет пометки, что вершина является концом слова, то объекта в <tex>\mathtt{map}</tex> нет. Если хотим добавить его, то ставим в вершину флаг конца слова и заносим значение.
Работать такой алгоритм будет за <tex>O(k)</tex>, где <tex>k</tex> {{---}} максимальная длина слова.
