SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Так и поступлю, если решу ещё две структуры описать. Хотя сложно утверждать. Я понимаю, что в основном критика уместна, но когда ты бесплатно описываешь то, над чем ломал голову кучу времени, а тебя не поняли, «переменные не так назвал», замеры делай — не весело, лень берёт верх)

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

То есть «нет»?) По логике моего алгоритма — да…

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

«На всякий случай» я делаю по 2(не помню, сейчас вот удалил нижний upd() — тоже работает), но с точки зрения алгоритма достаточно одного.
По примеру — внесли 16 элементов (2 по 8) и полностью досортированный результирующий массив (1 по 16) нам понадобится когда насобираем ещё 16 элементов. На самом деле нам не хватает одного шага слияния, ведь когда придёт 16-й элемент, оба 8-ми элементных массива уже должны быть пусты, а 16-ти элементный должен быть на сл. уровне, но на 16 шаге перенос указателя на сл.уровень ещё не произойдёт, поэтому 1 дополнительное слияние мы делаем ещё и в момент создания временного массива.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

А здесь на каждом шаге, но тоже логарифм, ибо нужно сделать по одному шагу слияния на каждый уровень, а количество уровней, как и в дереве, описывается логарифмом.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

При каждом добавлении элемента мы плавно пошагово готовим все уровни по одному значению на уровень.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

массив 1: 2 4 6 8
массив 2: 1 3 5 7
Один шаг слияния — это когда мы берём одно значение из массива 1 или 2 в зависимости от того какой текущий элемент сравнения меньше. За один шаг в результирующий массив дописывается только одно значение из уж сформированных отсортированных массивов. Не слияние в принципе, а только один шаг — одно значение.

Пример.
Пусть мы внесли 16 значений. Это будет означать, что первые 3 уровня пусты, в 4-м содержится 2 полностью заполненных и отсортированных 8-ми элементных массива. Чтобы слить их в 16-ти элементный массив, необходимо 16 шагов слияния. А сколько нужно вписать новых элементов, чтобы получить новый уровень — тоже 16. В этом и состоит отложеность слияния.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

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

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Идеально для файловых структур, когда в пределах одного кластера может находится куча актуальных данных)

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Я к тому, что с рост количества вставок для «предсказуемого момента» зависит от количества уровней и далеко не линейно.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Да, при вставке нового значение происходит по шагу слияния на каждом уровне. — Что и при вставке в дерево, когда нужно перебалансировать его и поэтому мы делаем повороты «всплывая» или наоборот. В этом случае наоборот.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Я к тому, что когда у нас заполнены пусть 5 уровней, пара лишних одноэлементных массива не слишком тянут на худший перерасход памяти. В принципе вы правы, просто я исхожу относительно текущего N.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Почему не выглядит если вот же — результирующий массив в 2 раза больше обоих исходных. После заполнения мы его пробрасываем в сл. уровень. Там происходит то же самое, только len там удвоенная от первоначального…
keyResult=new unsigned int[len*2];
valResult=new unsigned int[len*2];

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Аллоцированы все массивы? Каждую вторую вставку? Аллоцированы будут все 2 массива следующего уровня каждую вторую вставку. А следующего — каждую его вторую вставку, но так как в него вставка происходит через раз, то это каждая четвёртая вставка, 3 уровень — восьмая и остальные степени двойки.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Так скорее всего может показаться из-за того, что для наглядности я вызываю upd с каждой вставкой. Но первое условие проверяет готов ли массив к слиянию — если под result память не выделена, то пытаемся спустится на уровень ниже, но здесь ничего не произойдёт.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Заданная периодичность звучит будто через каждые N вставок. Но тут опять же логарифмическая зависимость. А так да, появление этого случая предсказуемо.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Откуда… мы храним ключ — 4 байт + значение — 4 байта + 2 ссылки на лево-право + балансирующий параметр, иногда родителя хранят. Здесь только ключ и значение, хотя, конечно, в 2 местах.
Слияние происходит по одному элементу на каждом уровне за одну вставку и происходит оно только после того, как оба подмассива полностью заполнены. Результирующий массив отправляется на уровень ниже и просто висит там, пока в этот уровень не придёт ещё один аналогичный по размеру массив. На 1 уровне 2 одноэлементных массива. На втором — 2 двухэлементных. На третьем 2 четырёх элементных. С каждым уровнем размерность массива удваивается относительно предыдущего. Если бы размерность не менялас, то для чего бы я вводил свойство класса len?

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

И опять же, здесь двойной расход памяти — худший случай. А лучший случай — +1 временное пустое. А в дереве оверхед на ссылки-балансирующие данные гарантированы.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Насчёт двойного расхода памяти я в курсе. В дереве тройное-четверное для аналогичных типов данных.
Не слияние, а шаг слияния — это копирование одного значения. В деревьях для балансировки при вставке происходят «повороты», не считали сколько это?
Линейно — это же вроде хуже, чем логарифмически… в любом случае каждый следующий уровень в 2 раза больше предыдущего, а значит с каждым новым уровнем для создания следующего нужно будет внести столько же элементов, сколько уже внесено. Это не логарифм?

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Слева нулевой уровень, справа первый.
Каждая строка отображает значения после вставки.

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Окей, сейчас даже графически нарисую «блуждание» по структуре)