内のノードの繰り返しのチェック：多親木
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
したがって、3つのノードは3つのノードで表示され、親はありません。私の問題は、ユーザーがノードを別のノードとして追加したときの潜在的な関係を検証することです。同じツリーにノードが2回表示されないようにしたいと思います。たとえば、ノード2を1のツリーおよび9のツリーに2回表示させるため、ノード2をノード6の子として追加すると失敗するはずです。私はこれを行う効率的なアルゴリズムを書くのに問題があります。
私の最初のアイデアは、見込みのある親のすべてのルートを見つけて、ルートごとのツリーを平坦化して、ツリーごとのノードのリストを取得し、それらのリストを将来の子と交差させ、結果として生じる交差リストのうちの1つは空である。例と一緒に行く、私はこれらの手順を取得したい：
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
このプロセスは、それが全体をメモリに木を置く必要とするという事実を除いて、動作します。私は2万以上のノードを持ついくつかの木を持っており、これは実行するのに約1分かかります。このパフォーマンスは100％のデベロッパーではありませんが、非常にイライラです。これを行うより効率的なアルゴリズムはありますか？
編集は4/2 14:00
上記のアルゴリズムは、実際には動作しません。 derobyは、7に子として9を加えることはアルゴリズムによって渡されるが、そうであってはならないことを指摘した。問題は、子を持つノードを別のノードに追加することは、ノードが繰り返されない限り成功し、子ノードを検証しないことです。
私は物事を正しく理解していることを確信しています。つまり、9に9を加えて7にすると、この例では問題ありませんか？ – deroby
9人の子供を7人に追加すると、9人の子供のすべてが繰り返されてしまうので、私がやろうとしていることに違反しますが、上記のアルゴリズムを使用していると捕らえられません。したがって、上記のアルゴリズムは、リーフノードを追加する場合はうまく動作しますが、ノードを子ノードとともに追加しようとしている場合、子ノードを検証しません。 – ptorian
「ノード2」と言うと、「ノード2のID（列）に値2の行」という意味ですか？ –