Оптимизация доступа к данным в деревьях

[Аватар]

Изыму из детей родителя Москвы ссылку на нее. В детей Австралии вставлю. В самой Москве ссылку на родителя поменяю. Все. А вот поиск по наименованию при любой организации проблемен. Вот нашел две Австралии без дополнительной инфы. И что?

[Utkin]

Изыму из детей родителя Москвы ссылку на нее.

Стоп! Как нашли родителя Москвы? Он что у Вас на дороге валяется?

В детей Австралии вставлю.

Стоп! Как Австралию нашли? Где Вы ее вообще взяли?

Вот нашел две Австралии без дополнительной инфы. И что?

В моем случае это все по-другому смотрится. Я же пути задаю (я же писал вроде ранее) Планета-Континенты-Европа-Москва переместить в Планета-Континенты-Австралия. Какие тут две Австралии? Даже если будет Планета-Континенты-Европа-Москва переместить в Планета-Австралия-Австралия-Австралия-Австралия проблем нет никаких. Главное чтобы на Континенте только одна Австралия была, а в глубину пофиг или там в соседних ветвях...

[Pavia]

Да блин это и есть рекурсия типичная. То есть медленно.

Предрассудки. Медленно это линейный поиск.

В данном случае это одно и тоже.

Невежество. Это разные вещи по определению. Почитайте что такое массив. И что такое дерево.

В дереве? Ага, размечтались.

В дереве которое хранится в массиве. Доступ через массив.
Но доступ это не поиск.
А вот поиск быстрее через дерево O(Log(N)).
А доступ к предку вы получаете за O(1) извлекая его порядковый номер из узла и подставляя его в массив. Или через указатель, что тоже самое.

[evg_m]

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

И там же говорилось, чтобы использовать "быстрые" алгоритмы поиска элемента массива с ЗАДАННЫМ идентификатором,
надо ДЕРЖАТЬ массив УПОРЯДОЧЕННЫМ по этим идентификаторам.
Либо иметь для вспомогательный массив ссылок на ЭЛЕМЕНТы массива (аналогично индексам в БД).

[Utkin]

И там же говорилось, чтобы использовать "быстрые" алгоритмы поиска элемента массива с ЗАДАННЫМ идентификатором,
надо ДЕРЖАТЬ массив УПОРЯДОЧЕННЫМ по этим идентификаторам.

Хорошо как упорядочить-то? Каждый раз элементы физически перемещать?

Либо иметь для вспомогательный массив ссылок на ЭЛЕМЕНТы массива (аналогично индексам в БД).

Вот я и хочу как-то придумать что-то типа того. Пока придумал группировать по уровню узла. В начале корень, затем в отдельной группе (массиве, списке - пофиг) его детей (с именами разумеется), в третьей группе внуков и т.д. Пока придумал только это. Потому и пришел за подсказкой.

[Pavia]

Вот я и хочу как-то придумать что-то типа того. Пока придумал группировать по уровню узла. В начале корень, затем в отдельной группе (массиве, списке - пофиг) его детей (с именами разумеется), в третьей группе внуков и т.д. Пока придумал только это. Потому и пришел за подсказкой.

Как по мне вы ввели лишнюю сущность, лишний слой которая вас только тормозит. Выкинуть её. ОЗУ вам хватит что-бы держать ваши данные. Вот когда не хватит её придётся ввести. Вот тогда деревья-Б+ и система кэшей и периодическая перестройка дерева для оптимизации. Но проще использовать готовую БД/СУБД.

[Utkin]

Как по мне вы ввели лишнюю сущность, лишний слой которая вас только тормозит. Выкинуть её. ОЗУ вам хватит что-бы держать ваши данные. Вот когда не хватит её придётся ввести. Вот тогда деревья-Б+ и система кэшей и периодическая перестройка дерева для оптимизации. Но проще использовать готовую БД/СУБД.

Вы видите проблему или нет? Я дал конкретную задачу:
Есть 2 пути - источник Планета-Континенты-Европа-Москва, приемник Планета-Континенты-Австралия. Перенесите Москву в Австралию. Когда поэтапно будете это делать - увидите что мне не нравится.

периодическая перестройка дерева для оптимизации.

Даже для ляма узлов мне видится это очень-очень-очень сомнительной идеей.

[evg_m]

вспомогательный массив в виде дерева.
группировать не по уровням, а по частичным идентификаторам.
частично отсортированный массив узлов
12.23
12.35
12.12
12.76
-----
34.98
34.08
34.67
34.17
-----
14.67
14.32
14.98
14.09

вставка занимает ЧИСЛО ГРУПП операций перемещения элемента массива. (3 группы 12/14/34)
поиск занимает длина несортированной группы (4 элемента в группе)

+ массив сортированых начал (и возможно окончания группы) и желательно сортированный для быстрого выбора группы.
12 ->от ... до ...
14 ->от ... до ...
34 ->от ... до ...
идеально длина группы =1 и полностью произвольный массив узлов, но тогда большой массив групп =исходному массиву.

[Utkin]

группировать не по уровням, а по частичным идентификаторам.

Подробней, я не совсем въехал по примеру.

[waleri]

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