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

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

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

Применение

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

Примечания

Ссылки

• , by Lloyd Allison, Monash University
• , NIST Dictionary of Algorithms and Data Structures
• , by Daniel J. Bernstein
• , by Jonathan Corbet
• , by Paul Jarc