Описание тега prefix-tree

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