KIA:
Не правильно понимаете, в массиве элементы идут последовательно, память может быть фрагментирована. Выделить непрерывный кусок памяти и частями - это совершенно разные вещи.

Добавлено 09.08.21, 15:36

Да, именно дерево поиска. По упорядоченному списку не проблема в 1 проход построить дерево, достаточно положить элементы в порядке рекурсивного обхода будущего дерева. А как отсортировать таким образом список, это уже другой ворос. Так же можно, с помощью каких-то ухищрений за O(n) попробовать построить по просто отсортированному списку.

Но целевой вопрос, именно о построении дерева из неупорядоченного списка, то есть. это не 10 вставок + 10 балансировок, а сам процесс вставки приводит к построению сбалансированного дерева. Понятно, что в самом примитивном случае надо постоянно пробегать весь список в поисках медианы и просто включать её в новое дерево, но это сверхнеоптимально и не подходит.

https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850602