KIA: Есть какие-нибудь алгоритмы для быстрого построения абсолютно (всякие разновидности АВЛ используют свои понятия баланса) сбалансированного двоичного дерева из несортированного списка?
Количество элементов известно.
Не предлагать сначала отсортировать список, так как дерево по сути и является сортировкой элементов. Загонять список в масив, тоже нельзя (предполагается, что нет непрерывного пространства для выделения массива).

Если таких алгоритмов не существует, давайте начнём с сортировки в определённой последовательности и построении в 1 проход.

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