Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850627 Tue, 10 Aug 2021 04:26:45 +0000 Сбалансированное двоичное дерево из несортированного списка. https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850627 Цитата KIA @
в массиве элементы идут последовательно, память может быть фрагментирована. Выделить непрерывный кусок памяти и частями - это совершенно разные вещи.

Я не знаю, кто Вам такой ерунды наговорил, что массив непременно занимает непрерывный блок памяти. Простейший пример - массив строк переменной длины. Какой там вообще может быть непрерывный кусок? будь так - увеличение длины первого элемента на байт приводило бы к копированию всего массива.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850611 Mon, 09 Aug 2021 17:56:24 +0000 Сбалансированное двоичное дерево из несортированного списка. https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850611 Цитата KIA @
Выделить непрерывный кусок памяти и частями - это совершенно разные вещи.

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

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

Зачем там ухищрения? Просто строишь рекурсивно, вызывая функцию построения для левой и правой половины массива.]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850602 Mon, 09 Aug 2021 15:25:33 +0000 Сбалансированное двоичное дерево из несортированного списка. https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850602 Цитата Akina @

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

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

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

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

Но целевой вопрос, именно о построении дерева из неупорядоченного списка, то есть. это не 10 вставок + 10 балансировок, а сам процесс вставки приводит к построению сбалансированного дерева. Понятно, что в самом примитивном случае надо постоянно пробегать весь список в поисках медианы и просто включать её в новое дерево, но это сверхнеоптимально и не подходит.]]> KIA Алгоритмы https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850593 Mon, 09 Aug 2021 13:35:54 +0000 Сбалансированное двоичное дерево из несортированного списка. https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850593 Цитата KIA @
Загонять список в масив, тоже нельзя (предполагается, что нет непрерывного пространства для выделения массива).

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

Или я что-то не так понимаю?]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850574 Mon, 09 Aug 2021 11:41:46 +0000 Сбалансированное двоичное дерево из несортированного списка. https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850574 Цитата KIA @
абсолютно

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

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

Цитата KIA @
Количество элементов известно.

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

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

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

Скрытый текст
зы: балансировка, ИМХО, тяжелая операция и раскуривать ее нужно достаточно долго. Рекурсия вносит тяжесть жесткую в понимании. Ну, кому-то она кажется простой, мне таковой не кажется, лол
]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850547 Sun, 08 Aug 2021 22:27:55 +0000 Сбалансированное двоичное дерево из несортированного списка. https://forum.sources.ru/index.php?showtopic=422332&view=findpost&p=3850547 Количество элементов известно.
Не предлагать сначала отсортировать список, так как дерево по сути и является сортировкой элементов. Загонять список в масив, тоже нельзя (предполагается, что нет непрерывного пространства для выделения массива).

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