Сбалансированное двоичное дерево из несортированного списка.

[KIA]

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

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

Сообщение отредактировано: KIA - 08.08.21, 22:29

[FasterHarder]

Цитата KIA @ 08.08.21, 22:27

абсолютно

в теории это вроде как "идеально" ---> идеально сбалансированное дерево

из постановки непонятно, речь про дерево ПОИСКА или просто дерево, ну, например, двоичные деревья бывают поиска и НЕ поиска. По дефалту считаем, что ты имел в виду поисковое деревце!

Цитата KIA @ 08.08.21, 22:27

Количество элементов известно.

следовательно, можно как минимум знать, сколько будет уровней у будущего сбалансированного дерева, но от этого не легче, ну, да)

а насчет балансировки, ИМХО, это одна из сложнейших операций в древовидных структурах, основанная на поворотах, производится при вставке и может РЕКУРСИВНО затрагивать/перестраивать множество узлов дерева

ты хочешь за 1 прогон по списку (ЛОС) построить сбалансированное дерево, не знаю, без балансировки дерева после включения узла ничего не знаю, ну то есть по классике работать

Скрытый текст

зы: балансировка, ИМХО, тяжелая операция и раскуривать ее нужно достаточно долго. Рекурсия вносит тяжесть жесткую в понимании. Ну, кому-то она кажется простой, мне таковой не кажется, лол

[Akina]

Цитата KIA @ 08.08.21, 22:27

Загонять список в масив, тоже нельзя (предполагается, что нет непрерывного пространства для выделения массива).

Ну вообще-то если дерево помещается, то массив всяко дело поместится. А если не хватит на то и другое одновременно - так ведь можно сразу сделать болванку под дерево без связей, отсортировать как массив, и потом бинарно расставить связи.

Или я что-то не так понимаю?

[KIA]

Цитата Akina @ 09.08.21, 13:35

Ну вообще-то если дерево помещается, то массив всяко дело поместится.

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

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

Цитата FasterHarder @ 09.08.21, 11:41

а насчет балансировки, ИМХО, это одна из сложнейших операций в древовидных структурах, основанная на поворотах, производится при вставке

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

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

[OpenGL]

Цитата KIA @ 09.08.21, 15:25

Выделить непрерывный кусок памяти и частями - это совершенно разные вещи.

В чём проблема выделять не непрерывный кусок? Вон std::deque в плюсах, например, с индексацией и без непрерывного расположения в памяти.

Цитата KIA @ 09.08.21, 15:25

Так же можно, с помощью каких-то ухищрений за O(n) попробовать построить по просто отсортированному списку.

Зачем там ухищрения? Просто строишь рекурсивно, вызывая функцию построения для левой и правой половины массива.

[Akina]

Цитата KIA @ 09.08.21, 15:25

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

Я не знаю, кто Вам такой ерунды наговорил, что массив непременно занимает непрерывный блок памяти. Простейший пример - массив строк переменной длины. Какой там вообще может быть непрерывный кусок? будь так - увеличение длины первого элемента на байт приводило бы к копированию всего массива.