Базисное дерево (Шаблон:Lang-en, также компактное префиксное дерево, основное дерево, дерево остатков[1]) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел <math>A</math>, являющийся единственным потомком узла <math>B</math>, сливается с узлом <math>B</math>.
Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как <math>O(k)</math>, где <math>k</math> — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве.
В отличие от обычных префиксных деревьев, узел базисного дерева может быть помечен как одним элементом (символом, битом и т. д.), так и последовательностью элементов. Это делает базисное дерево более эффективным для небольших наборов строк (особенно если сами строки достаточно длинные), и также для наборов, имеющих небольшое количество длинных префиксов.
Применение
Базисное дерево используется, в частности, для синтаксического анализа естественных языков[2].
Базисное дерево является одной из структур данных ядра Linux[3].
