Вставка в 2-3-4 дерева числа узлов

Question

Я реализую 2-3-4 дерева для какого-то управления памятью. Во время инициализации моего приложения я хочу вставить туда некоторое число целых чисел (получить его в качестве входных данных - скажем, n) В чем сложность такой вставки? O(nloglog(п))?

Answer 1

Сложность вставки в дереве 2-3-4 составляет O(log(n)).

Мы можем увидеть квоту из Википедии

2–3–4 дерева являются B-деревьями порядка 4 (Knuth 1998)

Сложность вставки в B-дерево составляет O(log(n)), как и дерево 2-3-4. Повторяя вставку для инициализации дерева 2-3-4, мы можем сказать, что временная стоимость init равна O(n*log(n)). Но мы можем ожидать особый способ построения [ ссылка]:

В приложениях часто полезно создать B-дерево для представления большого существующего набора данных, а затем постепенно обновлять его, используя стандартные операции B-дерева. В этом случае наиболее эффективным способом построения начального B-дерева является не последовательная вставка каждого элемента в исходную коллекцию, а построение начального набора конечных узлов непосредственно из входных данных, а затем построение внутренних узлов из них. Такой подход к построению B-дерева называется объемной загрузкой. Первоначально каждый лист, кроме последнего, имеет один дополнительный элемент, который будет использоваться для построения внутренних узлов.

Стоимость времени может быть (n + n/4 + n/16 + ... + n/(4^ ч)). На основании суммы геометрической прогрессии. Я рассчитываю стоимость времени. Это меньше чем (4/3)*n.

Пожалуйста, укажите, есть ли у меня ошибка во время расчета.