Базисное дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Базисное дерево
Тип Дерево
Изобретено в 1968 году
Изобретено Дональд Р. Моррисон
Временная сложность
в О-символике
В среднем В худшем случае
Расход памяти
Поиск O(k)
Вставка O(k)
Удаление O(k)
Пример базисного дерева для русского языка

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

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

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

Применение[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. Структура Radix Tree для сжатия данных https://habrahabr.ru/post/141145/
  2. Pymorphy 2 https://m.habrahabr.ru/post/176575/
  3. Robert Love. Linux Kernel Development. Third Edition. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1

Ссылки[править | править вики-текст]