查找所有不是父/祖父母/等或子/孙子/等的链接对象的算法

本文关键字：算法 对象 孙子 链接 祖父母 查找 | 更新日期: 2023-09-27 18:07:57

我有一个名为Device的对象。Device可以有一个父 Device。Device也可以有n子Devices。

我有一个下拉列表，显示所有可选择的Devices。我可以很容易地得到数据库中所有的Devices - db.Devices .

层次结构可以是无限级深。

我需要得到所有不高于或低于树中给定Device的Devices。从本质上讲，我要求Devices与给定的Device无关(既不是父母/祖父母/曾祖父母/等，也不是孩子/孙子/曾孙/等)。我还需要从列表中排除给定的Device。

最好的方法是什么?我应该使用递归吗?

(我使用c#和实体框架与SQL Server数据库，所以我可以使用Linq To SQL或使用模型本身)

查找所有不是父/祖父母/等或子/孙子/等的链接对象的算法

我的方法是首先获得设备的所有兄弟姐妹D:

P = parent of the device
sibs = {all children of P that are not D}

任何d in sibs的后代都与D无关。继续往下看家谱:

G = grandparent of the device
sibs = sibs union {all children of G that are not P}

继续这样，集合sibs和它们所有的后代就是你要找的集合。

在伪代码:

D = device;
siblings = {};
while (D has parent) {
    P = parent(D);
    siblings = siblings union (children(P) ' D);
    D = P;
}
return descendants(siblings);

同意Denis的观点，这取决于你的数据是如何存储的。

我建议您使用TSQL HierarchyId数据类型实现您的层次结构。然后，您可以使用isdescent

很容易地检查一行是否是另一行的后代
DECLARE @searchId HierarchyId -- select your id
SELECT @searchId = HierarchyId FROM Devices WHERE DeviceId = 1
SELECT * FROM Devices 
WHERE 
    -- not children
    DeviceHierarchyId.IsDescendantOf(@seachId) = 0
    -- not parents
    AND @searchId.IsDescendantOf(DeviceHierarchyId) = 0

编辑

为了简要解释HierarchyId数据类型及其工作原理，请考虑在根节点下的层次结构中每个项都有一个位置。(如果你有多个天然根，你会把每个根放在一个超级根下)。每个hierarchyid列存储项目的完整层次结构位置。例如

Id | ParentId | HierarchyId
1 | null | '1
2 | 1    | '1'2
3 | 1    | '1'3
4 | 3    | '1'3'4

等等。要检查一个项是否为另一个项的子项，只需检查其hierarchyId是否包含在另一行的hierarchyId中-例如，4是3的子项，因为整个'1'3包含在它的hierarchyId '1'3'4中，但4不是2的子项，因为'1'2不包含在hierarchyId中。

查看itemema是否是itemB的父元素，检查itemB是否是itemA的子元素。

最后，实际上不需要做任何比较。TSQL HierarchyId类型包含许多方法，其中之一是我在上面突出显示的IsDescendantOf方法。因此，像hierarcyId1.IsDescendantOf(hierarchyId2)这样的用法执行我在这里描述的那种检查。hierarchyid是二进制的，可以在数据库中快速比较。

在处理数据库层次结构时，我会尽可能使用hierarchyId

如果你在父元素上有一个索引，你可以尝试

select * 
from devices as child 
where exists(select null 
                 from devices as parent 
                 where parent.id = child.parent)

我的SQL并不完美，但这是我将使用的基本方法。

我的条件反射式算法解决方案是"标记-清除"类型的解决方案(来自垃圾收集器理论)。

http://en.wikipedia.org/wiki/Garbage_collection_ (computer_science) # Na.C3.AFve_mark-and-sweep

基本上，你遍历设备的整个层次结构，并标记那些是"可追踪的"，这意味着它们可以通过另一个设备(使用递归)"到达"。

任何未标记的内容，您将"清除"GC。在这种情况下，任何未标记的内容都是您要查找的集合。

这取决于您如何在数据库中存储树。嵌套集模型允许直接在数据库中执行此类查询。

相关文章：