Префиксное дерево
Описываемая структура данных представляет собой корневое дерево T, хранящее множество ключей K и устроенное следующим образом:
- Каждая вершина x содержит следующие поля: префикс prefix(x) (возможно, пустой), массив E(x) из n(x) исходящих из неё рёбер, помеченных различными символами (упорядоченный в лексикографическом порядке), а также некоторые флаги (булевские переменные), например, final(x), который определяет, соответствует ли этой вершине какой-либо ключ. Флаги вершины будут описываться по мере их введения.
- Ребра e=(x,Li(x)) (будем обозначать Li(x) вершину, в которую ведёт i-е ребро из массива E(x)) помечены символами c(e). В данном случае мы не отличаем отдельные символы от строк и будем считать их строками единичной длины.
- Любой путь S(x1,xn)=x1e1x2e2…en-1xn в дереве задаёт строку s, которая получается из этого пути S конкатенацией строк s=prefix(x1)+c(e1)+prefix(x2)+c(e2)+…+c(en-1)+prefix(xn) Строка s, заданная путём S, принадлежит хранимому в дереве множеству ключей K в том и только в том случае, если конечная вершина xn пути S помечена флагом final(xn).
Отметим, что в общем случае некоторому множеству ключей K может соответствовать более одного дерева T, так как в дерево, содержащее хотя бы одну вершину, из которой исходят не все возможные рёбра, можно добавить вершину x’ с произвольным префиксом, не помеченную final(x’). Полученное дерево будет задавать то же самое множество ключей K. Поэтому введём дополнительное свойство, выполнения которого требовать мы не будем, позволяя реализовать тем самым отложенное удаление (которое будет обсуждаться ниже):
- Любая вершина x∈T, для которой n(x)≤1, помечена как final(x). Т.е. (единственному) пути, ведущему от корня к такой вершине соответствует ключ множества K.
Заметим, что при выполнении последнего свойства множество K однозначно задаёт дерево T. Доказательство этого факта не представляет сложности, однако выходит за рамки данной статьи.
Дерево T, для которого выполняется последнее свойство, будем называть минимальным. Кроме того, вершину x, для которой выполняется (не выполняется) условие n(x)≤1⇒final(x), будем называть неизбыточной (избыточной). В дальнейшем (если не оговорено обратного) будем рассматривать только минимальные деревья.
Заметим также, что для хранения мультимножества достаточно ввести дополнительный параметр вершины count(x)≥1, определённый только для вершин, для которых установлен флаг final(x).
