Сжатое префиксное дерево

Базисное дерево (также компактное префиксное дерево, основное дерево, дерево остатков[1]) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел ${\displaystyle A}$, являющийся единственным потомком узла ${\displaystyle B}$, сливается с узлом ${\displaystyle B}$.

Базисное дерево
Тип	дерево
Год изобретения	1968
Автор	Дональд Р. Моррисон
Сложность в О-символике
В худшем случае Поиск ${\displaystyle O(k)}$ Вставка ${\displaystyle O(k)}$ Удаление ${\displaystyle O(k)}$
Медиафайлы на Викискладе

Пример базисного дерева для русского языка

Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как ${\displaystyle O(k)}$, где ${\displaystyle k}$ — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве.

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