Число узлов в B-дереве

Question

Сколько узлов имеет результирующее B-дерево (минимальная степень 2), если я вставляю числа от 1 до n в порядке?

Я пробовал вставлять узлы от 1 до 20, была серия для числа узлов, но я не мог ее обобщить.

Может кто-нибудь, пожалуйста, помогите мне получить формулу для этого.

Answer 1

Это будет зависеть от порядка B-Tree. Порядок BTree - это максимальное количество дочерних узлов, которые может содержать нелистовой узел (что больше, чем минимальное количество ключей, которые может удерживать узел).

Согласно определению Кнута, В-дерево порядка т является дерево, которое обладает следующими свойствами:

1. Каждый узел имеет не более т детей.
2. Каждый нелистовой узел (кроме корня) имеет как минимум ⌈m/2⌉ детей.
3. Корень имеет не менее двух детей, если он не является листовым узлом.
4. Нелистный узел с k детьми содержит ключи k-1.
5. Все листья отображаются на одном уровне, а внутренние вершины не содержат никакой информации.

Так что в вашем случае, когда вы вставляете 20 ключей, если порядок равен m, тогда на основании указанных выше условий вы можете получить набор неравенств, описывающий возможное значение m. Но нет формулы равенства, в которой указано количество внутренних узлов в B-Tree.