CLRS 18-2.4 Предположим, что мы вставляем ключи {1,2,…,n} в пустое B-дерево с минимальной степенью 2. Сколько узлов имеет итоговое B-дерево?

Мы знаем, что каждый узел, кроме корня, должен иметь не менее t−1=1 ключей и не более 2t−1=3 ключей. Окончательное дерево может иметь не более n−1 узлов, если n≥2. Если n=1, никогда не может быть n узлов, поскольку мы вставляем ключ только в непустой узел, поэтому всегда будет хотя бы один узел с двумя ключами. Затем обратите внимание, что у нас никогда не будет более одного ключа в узле, который не является правым стержнем нашего B-дерева. Это связано с тем, что каждый ключ, который мы вставляем, больше, чем все ключи, хранящиеся в дереве, поэтому он будет вставлен в правый стержень дерева. Наименьшее возможное количество узлов возникает, когда каждый узел, кроме самого глубокого узла в правом сплайне, имеет 2 ключа, а самый глубокий узел в правом сплайне имеет 3 ключа. Итак, на высоте 1 — 1 узел, на высоте 2 — 3 узла, …, на уровне h — 2^h−1 узла. В этом случае n = 2^(h+1)−1, где h — высота B-дерева, а количество узлов в B-дереве равно #nodes = 2^(h+1)−2−h = n−lg(n+1). Таким образом, для любого n окончательное B-дерево должно иметь n−⌊lg(n+1)⌋≤#nodes≤n−1 (если n≥2).