286
правок
Изменения
Нет описания правки
== Структура ==
Свойства B<tex>^{+}</tex> дерева аналогичны [[B-дерево#Структура| свойствам B-дерева]](с учетом отличий описанных выше).
=== Структура узла ===
'''int''' t <span style="color:#008000"> // минимальная степень дерева</span>
'''Node''' root <span style="color:#008000"> // указатель на корень дерева</span>
== Оценка высоты дерева ==
{{Теорема|statement=Если <tex>n \geqslant 1</tex>, то для B<tex>^{+}</tex>-дерева c <tex>n</tex> узлами и минимальной степенью <tex>t \geqslant 2</tex>
:<tex>h \leqslant \log_t\dfrac{n}{2} + 1</tex>
|proof=
Так как <tex>n \geqslant 1</tex>, то корень B<tex>^{+}</tex>-дерева <tex>T</tex> содержит хотя бы один ключ, а все остальные узлы — хотя бы <tex>t - 1</tex> ключей. <tex>T</tex> имеет хотя бы <tex>2</tex> узла на высоте <tex>1</tex>, не менее <tex>2t</tex> узлов на глубине <tex>2</tex>, и так далее. То есть на глубине <tex>h</tex>, оно имеет хотя бы <tex>2t^{h-1}</tex> узлов. Так как сами ключи хранятся только в листах, а во внутренних вершинах лишь их копии, то для <tex>n</tex> ключей
<tex>n \geqslant 2t^{h-1}</tex>
:<tex>t^{h-1} \leqslant \dfrac{n}{2}</tex>
:<tex>h-1 \leqslant \log_t\dfrac{n}{2}</tex>
:<tex>h \leqslant \log_t\dfrac{n}{2} + 1</tex>
}}
Как можно заметить, высота B<tex>^{+}</tex>-дерева не более чем на 1 отличается от [[B-дерево#Высота|высоты B-дерева]], то есть хранение значений только в листах почти не ухудшает эффективность дерева
== Примeчания ==
<references/>
