У меня есть довольно простая реализация дерева в SQL:
CREATE TABLE [dbo].[Nodes] (
[Id] [int] IDENTITY(1,1) NOT NULL,
[Name] [nvarchar](max) NULL
);
CREATE TABLE [dbo].[NodeNodes] (
[ParentNodeId] [int] NOT NULL,
[ChildNodeId] [int] NOT NULL
);
Моя реализация дерева такова, что у узла может быть несколько родителей.Это позволяет пользователю создавать собственные деревья, которые группируют часто используемые узлы.Например:
1 8 9
/ \ / \ / \
2 3 4 7 2 6
/ \ / \ / \
4 5 6 7 4 5
Node | Parents | Children
---------------------------
1 | - | 2,3
2 | 1,9 | 4,5
3 | 1 | 6,7
4 | 2,8 | -
5 | 2 | -
6 | 3,9 | -
7 | 3,8 | -
8 | - | 4,7
9 | - | 2,6
Итак, есть три дерева, которые обозначены тремя узлами без родительского элемента.Моя проблема заключается в проверке потенциальных отношений, когда пользователь добавляет узел в качестве дочернего узла другого.Я бы хотел, чтобы ни один узел не появлялся дважды в одном и том же дереве.Например, добавление узла 2 в качестве дочернего по отношению к узлу 6 должно завершиться сбоем, поскольку это приведет к тому, что узел 2 появится дважды в дереве 1 и в дереве 9.У меня проблемы с написанием эффективного алгоритма, который делает это.
Моей первой идеей было найти все корни предполагаемого родителя, сгладить деревья корней, чтобы получить один список узлов на дерево, затем пересечь эти списки с предполагаемым потомком и, наконец, пройти только проверку.если все результирующие пересекаемые списки пусты.Следуя примеру, я получу следующие шаги:
1) Trace prospective parent through all parents to roots:
6->3->1
6->9
2) Flatten trees of the roots
1: {1,2,3,4,5,6,7}
9: {2,4,5,6,9}
3) Intersect lists with the prospective child
1: {1,2,3,4,5,6,7}^{2} = {2}
9: {2,4,5,6,9}^{2} = {2}
4) Only pass if all result lists are empty
1: {2} != {} ; fail
9: {2} != {} ; fail
Этот процесс работает, за исключением того факта, что он требует помещения целых деревьев в память.У меня есть несколько деревьев с 20 000+ узлов, и это занимает почти минуту, чтобы бежать.Эта производительность не является на 100% разрушителем, но она очень расстраивает.Есть ли более эффективный алгоритм для этого?
Edit 4/2 2 pm
Приведенный выше алгоритм фактически не работает. deroby указал, что добавление 9 в качестве дочернего к 7 будет передано алгоритмом, но не должно быть.Проблема в том, что добавление узла с дочерними элементами в другой узел будет успешным, пока узел не повторяется - он не проверяет дочерние элементы.