在嵌套集合中查找最低公共祖先

Question

我正在寻找一种在嵌套集合中找到最低公共祖先的方法，该集合可以使用单个等式找到。

​

​

例如，来自位于：https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg的图像

西装和女装之间的LCA是服装。我可以使用基于级别的系统来找出父级在哪里相遇，但这样做的用例是在数据库设计中，因此提高级别将不利于性能。

我希望我可以使用一个单一的计算使用套装(3:8)和女人(10:21)来得出服装的组合(1:22)，即如果存在这样的等式。

Answer 1

嵌套集有一个有趣的属性，我们可以用它来查找所有共同的祖先。这个属性仅仅是一个节点的所有子节点都有一个大于它的左边和一个小于它的右边的左边。

这意味着我们需要找到左右边界包含我们所关心的所有节点的节点。我们可以通过使用我们关心的节点集来设置我们正在寻找的边界来实现这一点。我们可以很容易做到这一点，如下所示：

在您想要共同祖先的所有节点中，取最低的左边和最高的右边。在本例中，所选节点的最低左侧是suits上的3，最高右侧是女性上的21，然后您可以在这个3:21的统一节点空间上执行祖先查询。

在本例中，您将查找一组左<3和右> 21的节点。这将为您提供所有共同祖先的集合。在这种情况下，唯一匹配的是衣服。服装上的1小于3，22大于21。

如果您有多个共同的祖先，但您想要最低的，您可以按左列降序对它们进行排序，然后取第一个。

这在SQL中可能看起来像这样。我使用的是T-SQL，因此"top 1“可能是limit 1或您的SQL风格中的其他值。

select top 1 * from Clothing where [left] < 3 and [right] > 21 order by [left] desc