javascript-algorithms
Префиксное дерево
Префиксное дерево (также бор, луч, нагруженное или суффиксное дерево) в информатике - упорядоченная древовидная структура данных, которая используется для хранения динамических множеств или ассоциативных массивов, где ключом обычно выступают строки. Дерево называется префиксным, потому что поиск осуществляется по префиксам.
В отличие от бинарного дерева, узлы не содержат ключи, соответствующие узлу. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до некоторого выделенного узла.
Таким образом, в отличие от бинарных деревьев поиска, ключ, идентифицирующий конкретный узел дерева, не явно хранится в данном узле, а неявно задаётся положением данного узла в дереве. Получить ключ можно выписыванием подряд символов, помечающих рёбра на пути от корня до узла. Ключ корня дерева — пустая строка. Часто в выделенных узлах хранят дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья и, возможно, некоторые внутренние узлы.
На рисунке представлено префиксное дерево, содержащее ключи «A», «to», «tea», «ted», «ten», «i», «in», «inn».