Базисное дерево | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | дерево | |||||||||||||||
Изобретена в | 1968 | |||||||||||||||
Создатель | Дональд Р. Моррисон | |||||||||||||||
Сложность в О-символике | ||||||||||||||||
|
Базисное дерево (также компактное префиксное дерево, основное дерево, дерево остатков[1]) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел , являющийся единственным потомком узла , сливается с узлом .
Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как , где — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве.
В отличие от обычных префиксных деревьев, узел базисного дерева может быть помечен как одним элементом (символом, битом и т. д.), так и последовательностью элементов. Это делает базисное дерево более эффективным для небольших наборов строк (особенно если сами строки достаточно длинные), и также для наборов, имеющих небольшое количество длинных префиксов.
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .