Бор

Бор – это структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Для построения используется корневое дерево, где каждое ребро подписано соответсвующей буквой, а там где кончается строка надо поставить метку.

Асимпттотика поиска, добавления, удаления строки S:
O(|S|) , т.е. за длину строки.

Бор для набора строк {the, there, their, answer, any, bye}:


 
Префиксное дерево или бор - структура данных в виде дерева, в котором путь до любой вершины - префикс какой-либо строки. Реализуется при помощи указателей. Автор сего текста написал бор, зная только его определение. А вы сможете?