Последовательность вставок при генерации дерева B-Tree / 2-3-4

Question

Кто-нибудь знает о том, как важна последовательность вставок для 2-3-4 деревьев? Или B-деревья?

Кажется, формула для минимальной высоты - это log_m(k + 1), где m - это максимальное нет. детей и к количество ключей

И формула для максимальной высоты: log_n((k + 1) / 2) где n - это минимальное число. детей может иметь внутренний узел.

Но какая последовательность вставок фактически дает эти результаты?! Я не знаю.

Было предложено минимизировать высоту дерева 2-3-4, вы бы взяли медиану линейной последовательности, например. 1,2,3,4,5,6,7,8, и вставьте его перед повторным полосканием, повторяя для подсписков по обе стороны от медианы. Это правда? И если да, то какая последовательность максимизирует высоту?

Answer 1

Да, последовательность вставок имеет значение. Очевидно, что дерево будет выше для того же количества ключей, если больше узлов являются 1-узлами. Их способ максимизировать количество 1-узлов в дереве - это непрерывно расширять одну ветвь дерева до 4-узлов, увеличивая высоту дерева, оставляя множество узлов в качестве 1-узлов. По сути, вставьте предварительно отсортированные ключи. 1,2,3,.., к. Для дерева с минимальной высотой вы хотите равномерно развернуть все ветви, чтобы заполнить каждый слой дерева. Таким образом, вы вставляете медиану клавиш, разделяете список вставок в этой клавише, а затем вставляете медианы из двух половин списка и т. Д.