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

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

Альтернативные названия на русском — бор (первый перевод монографии Д. Кнута, Т. 3), луч (второй перевод монографии Д. Кнута, Т. 3), нагруженное дерево (книга Ахо и др. «Структуры данных и алгоритмы», с. 152), там же и происхождение названия. На английском — Trie.

См. также

• Алгоритм Ахо — Корасик
• Суффиксное дерево

Литература

• Knuth, Donald (1997). "6.3: Digital Searching". The Art of Computer Programming Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. p. 492. ISBN 0-201-89685-0.
• Edward Fredkin (1960). "Trie Memory". Communications of the ACM 3 (9): 490–499. doi:10.1145/367390.367400.

Ссылки

• Bentley, Jon; Sedgewick, Robert (1998-04-01). "Ternary Search Trees". Dr. Dobb's Journal (Dr Dobb's). Archived from the original on 2008-06-23.
• Tries // L. Allison
• Реализация префиксного дерева на Java

Для улучшения этой статьи желательно?: Проставив сноски, внести более точные указания на источники.