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

возможные варианты

1. хранить глубину в каждом узле, значит переиндексировать всё дерево при удалении ... в худшем случае корня

2. вычислять путь до корня при каждом новом добавлении и помечать как лист нижнего уровня?

3. проверять соседей до первого, у которого есть потомки, и НЕ помечать как лист нижнего уровня?

4. истина где-то рядом? :) мой кругозор на этом заканчивается

идеи? критика? поможите, люди добрые...

это на 100% совпадает с механизмом,
реализованым в СУБД "CACHE" (или M3-LITE - бесплатный)

например, там сразу на каждом узле дерева уже есть признак
- он самый нижний или еще нет

и ряд эффективных команд для
сшивания-раскраивания-анализа-навигации деревьев

могу помочь c Вашей конкретной задачей

mx@enters.eu

man_555 niknameГде поддерживать? В памяти, в БД?

Пока что я выбрал путь поддержки и хранения сего "хозяйства" в памяти, а точнее, нацелился на Boost Graph Library . Основные причины: уже реализованные некоторые алгоритмы на графах, и однопользовательское приложение. Хотя, может быть я и не прав, и стоит повнимательней присмотреться к СУБД... или.. к XML? ;) Идея с БД, конечно, интересная, но в любом случае, важна эффективность.

Насколько я понял Cache предоставляет свой собственный яп? Насколько сложно проходить в глубину граф при помощи SQL, или вообще, реализовывать некий алгоритм X на SQL? При всём этом БД предоставит единое хранилище для всех графов, тогда по мере роста объёма, насколько усложняться по времени алгоритмы?

LordMADМожет стоить просто выбрать такой из стандартных способов хранения дерева, при котором получение данной информации (последний ли уровень) - является тривиальной операцией.

Например? Поиск, операция, конечно, важная, но не за счёт полиномиального 'О ' остальных операций.

CACHE работает на глубину 64 уровня
сотня деревьев до миллиона ветвей в каждом -
проблем точно не будет по скорости

дальше - не особо тестили

язык CACHE - стандартный MUMPS
например - взять следующую справа ПОЛНУЮ ветвь :
i=$q(@i)
где i - текущая ветвь

man_555 LordMADнапиши о своей задаче подробнее.

задача в целом такова: имеем граф, состоящий из трёх подграфов, два из них - т-арные деревья с одним предком у каждого узла, и связаные с третьим подграфом через вершины на самом нижнем уровне ;-)

Таким образом, деревьев два, и расти они могут как в ширину, так и в глубину. Третий подграф явл. ориентированным, но допускает в себе циклы, петли и параллельные дуги. Кроме того вершины могут иметь некоторые свойства вроде веса, итп.

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

Кол-во вершин ~ 3-5K, но ничего неизвестно об их конфигурации

если CACHE - то все просто - я живу в Лиепае
9416382

man_555спасибо, MX -- ALEX, но проект некоммерческий :-)

не проблема