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

Материал из Википедии — свободной энциклопедии

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