Базисное дерево (, также компактное префиксное дерево, основное дерево, дерево остатковСтруктура Radix Tree для сжатия данных https://habrahabr.ru/post/141145/ ) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел , являющийся единственным потомком узла , сливается с узлом .
Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как , где — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве.
В отличие от обычных префиксных деревьев, узел базисного дерева может быть помечен как одним элементом (символом, битом и т. д.), так и последовательностью элементов. Это делает базисное дерево более эффективным для небольших наборов строк (особенно если сами строки достаточно длинные), и также для наборов, имеющих небольшое количество длинных префиксов.
Применение Базисное дерево используется, в частности, для синтаксического анализа естественных языковPymorphy 2 https://m.habrahabr.ru/post/176575/ . Базисное дерево является одной из структур данных ядра LinuxRobert Love. Linux Kernel Development. Third Edition. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 .
Примечания
Ссылки 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
Категория:Строковые алгоритмы Категория:Деревья (структуры данных)