Что такое Префиксное дерево? Значение термина Префиксное дерево

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

У префиксного дерева есть альтернативные русские названия – бор, луч, нагруженное дерево.