Префиксное дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Trie example.svg

Префиксное дерево (также бор[1], луч[2], нагруженное дерево[3], англ. trie) — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. В отличие от бинарных деревьев, ключ, идентифицирующий конкретный узел дерева, не хранится в данном узле, а определяется положением данного узла в дереве. Значение ключа можно получить просмотром всех родительских узлов, каждый из которых хранит один или несколько символов алфавита. Корень дерева связан с пустой строкой. Таким образом, потомки узла имеют общий префикс. Значения, связанные с ключом, обычно не связаны с каждым узлом, а только с листьями и, возможно, некоторыми внутренними узлами.

Структура широко применяется в алгоритмах поиска, в частности, в некоторых из них используется суффиксное дерево — префиксное дерево, содержащее все суффиксы для некоторой заданной строки, а в алгоритме Ахо — Корасик в префиксное дерево объединяются несколько строк поиска.

Примечания[править | править вики-текст]

  1. В первом переводе монографии Кнута
  2. В последующих переводах монографии Кнута
  3. Ахо. «Структуры данных и алгоритмы», с. 152

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]