Мы разделяем полные узлы на пути к целевой позиции, потому что мы не знаем, нужно ли нам «возвращаться назад». Вы можете делать это так, как вы думаете, когда мы спускаемся к целевому узлу, разделяем его, а затем вставляем медиану разделения в родительский узел, рекурсивно разделяя узлы по мере необходимости. Но это требует от нас перехода от корня к цели и обратно, потенциально до самого корня снова. Это может быть нежелательно, например, если доступ к узлам дважды будет слишком дорогим. В этом случае может быть лучше пойти за один проход прямо вниз, где вы разделите все полные узлы до , ожидая необходимости в большем количестве места.
Для демонстрации вы можете попробовать вставить 10 в деревья посередине и внизу рисунка. Дерево в нижней части, нерасщепленное, должно быть полностью разделено до корня так же, как и среднее дерево, потому что двухпроходный алгоритм не оставлял места. В среднем дереве вставка 10 по-прежнему вызывает разделение, но не расширяется до конца, потому что два верхних слоя дерева очень просторные.
Однако есть важное предупреждение. Пусть t будет минимальным количеством детей на узел. Для двухпроходного алгоритма максимальное число дочерних элементов, которое может иметь узел, должно быть не менее u = 2t - 1. Если оно меньше, например, 2t - 2, то разделение полного узла (2t - 3 элементов), даже с добавлением дополнительного элемента, не сможет создать два недефицитных узла. Алгоритм одного прохода требует более высокого максимума, u = 2t. Это связано с тем, что в двухпроходном алгоритме всегда имеется элемент для устранения ровно одного недостатка. У однопроходного алгоритма такой способности нет, так как он иногда разбивает узлы без необходимости, поэтому он не может вставить элемент, который он содержит, в один из недостатков. Это может не принадлежать там.