Алгоритмы многомерных деревьев

[ReMaRk]

Алгоритмы многомерных деревьев

Может быть кто-нибудь сталкивался с многомерными деревьямии - теория, практика и тому подобное?
Если да, то расскажите плиз!

З.Ы. Под многомерным деревом понимается следующее:
отношение родителей к потомкам как многие ко многим.

 

[Crazy]

Это уже не дерево. Это ориентированный граф.

 

[ReMaRk]

Автор оригинала: Crazy
Это уже не дерево. Это ориентированный граф.

А нельзя ли по подробнее?
Есть ли реализация этого алгоритма на СУБД?

 

[Valentin]

На теории, советую найти в сети книгу Кнута "Искусство программирования". Если осилишь всю её глубину глубин, то респект Там про всё: и про динамические структуры данных. Раздел с деревьями там отдельно, или даже глава я не помню...

В гугл!!!
Knut_-_Iskusstvo_programmirovaniya_-_Tom_1.djvu
Knut_-_Iskusstvo_programmirovaniya_-_Tom_2.djvu
Knut_-_Iskusstvo_programmirovaniya_-_Tom_3.djvu

-~{}~ 06.07.05 01:24:

Автор оригинала: ReMaRk
А нельзя ли по подробнее?
Есть ли реализация этого алгоритма на СУБД?

Есть. Есть небольшая библиотека на PHP. Вроде называецца treeDB, или что-то в этом роде. На сайте зайди в статьи, там есть один очерк про обход дерева, а в коментариях несколько ссылок на эту "вроде treeDB" и "ultratree"

 

[robocomp]

Re: Алгоритмы многомерных деревьев

Автор оригинала: ReMaRk
З.Ы. Под многомерным деревом понимается следующее:
отношение родителей к потомкам как многие ко многим.

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

как бы нам это сделать? вот так:

product (pid,code,name);
category(cid,code,name);
product_category(pid,cid);

вот, пож-та.

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

Сорри, если не в тему -(

 

[tashkentchi]

Я реализовывал такое "дерево". Одной дополнительной таблицей (ИД - ПАРЕНТ_ИД) не обойтись, т.к. рекурсия потом задолбает. Лучше создать еще одну (ИД - ЧАЙЛД_ИД) для всех пар предок-потомок. Эту вторую можно снабдить полем, куда писать уровень родства, тогда можно обойтись без первой таблицы. Но я все-таки держу в базе обе таблицы, причем вторая автоматом изменяется при изменении первой. Вторая может быть целиком восстановлена из первой.

 

[inse3t]

Деревья... Может ты о наследовании в ООП.

 

[tashkentchi]

Читай тему внимательней

 

[robocomp]

inse3t

Деревья ... может, он вообще о яблонях, м?
-)

 

[ReMaRk]

robocomp
О яблоках (яблонях) в свое время Ньютон упомянал