Стр. 52 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
50
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Примечание: отцовская страница потеряла ключ, следовательно, и там
необходимо провести анализ на переистощение.
(
Самостоятельно записать алгоритм удаления
)
4.6. Двоичные В-деревья (DВ - деревья)
Двоичными называют
В
-деревья порядка
n
= 1, то есть каждая страница
содержит 1 или 2 ключа. Поскольку кратность ветвления такого дерева низкая,
то число страниц будет большим и для поиска во внешней памяти такие
деревья непригодны. Зато, поскольку любые
В
-деревья сбалансированы по
определению, то у них все листья на одном уровне.
DВ
-деревья выгодно
использовать для поиска в оперативной памяти как альтернативу деревьев
бинарного поиска, поскольку в
DB
-дереве, как в любом
B
-дереве, все листья
расположены на одной высоте и поэтому не требуют балансировки.
В
-деревья
эффективней бинарных деревьев, если частота включений - исключений
заметно больше, чем частота простого поиска.
20
10,15
30
8
11, 12
16, 18
25
35, 40
Рис. 51. Пример
DB
-дерева
Если таблица содержит
k
ключей, то в худшем случае время поиска равно
высоте дерева и составит
k
2
log
, в лучшем случае
k
3
log
, когда каждая вершина
имеет 2 ключа и 3 сына.
?
Самостоятельно записать алгоритм поиска, включения - исключения
?
Примечание: для
DB
-деревьев понятие страницы непродуктивно.
Использование этого понятия выигрыша не дает. В программе вместо него
удобно использовать ссылку на брата.
