Сжатое префиксное дерево
Базисное дерево | |||||||||
---|---|---|---|---|---|---|---|---|---|
Тип | дерево | ||||||||
Год изобретения | 1968 | ||||||||
Автор | Дональд Р. Моррисон | ||||||||
Сложность в О-символике | |||||||||
|
|||||||||
![]() |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/40/Radix-tree-ru.png/220px-Radix-tree-ru.png)
Базисное дерево (англ. radix tree, также компактное префиксное дерево, основное дерево, дерево остатков[1]) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел , являющийся единственным потомком узла , сливается с узлом .
Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как , где — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве.
В отличие от обычных префиксных деревьев, узел базисного дерева может быть помечен как одним элементом (символом, битом и т. д.), так и последовательностью элементов. Это делает базисное дерево более эффективным для небольших наборов строк (особенно если сами строки достаточно длинные), и также для наборов, имеющих небольшое количество длинных префиксов.
Применение
[править | править код]- Базисное дерево используется, в частности, для синтаксического анализа естественных языков[2].
- Базисное дерево является одной из структур данных ядра Linux[3].
Примечания
[править | править код]- ↑ Структура Radix Tree для сжатия данных https://habrahabr.ru/post/141145/ Архивная копия от 20 декабря 2016 на Wayback Machine
- ↑ Pymorphy 2 https://m.habrahabr.ru/post/176575/ Архивная копия от 19 июня 2017 на Wayback Machine
- ↑ Robert Love. Linux Kernel Development. Third Edition. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Архивная копия от 15 декабря 2015 на Wayback Machine
Ссылки
[править | править код]- 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
Это заготовка статьи по информатике. Помогите Википедии, дополнив её. |