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

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

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

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

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

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

Применение

• Базисное дерево используется, в частности, для синтаксического анализа естественных языков.
• Базисное дерево является одной из структур данных ядра Linux.

Ссылки

• Algorithms and Data Structures Research & Reference Material: PATRICIA, by Lloyd Allison, Monash University
• Patricia Tree, NIST Dictionary of Algorithms and Data Structures
• Crit-bit trees, by Daniel J. Bernstein
• Radix Tree API in the Linux Kernel, by Jonathan Corbet
• Kart (key alteration radix tree), by Paul Jarc