在一组嵌套

Question

查找最近公共祖先我正在寻找一种方式来找到一个嵌套集合内的最低共同祖先可以使用一个公式来找到。

例如，从图像在：https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg

套装和妇女之间的LCA是服装。我可以使用基于级别的系统来确定父级会面的位置，但是这种情况的用例是在数据库设计中，因此提高级别会对性能造成不利影响。

我希望我可以使用套装（3：8）和女装（10:21）的单一计算来达到服装的组合（1:22），即如果存在这样一个方程式。

Answer 1

嵌套组有我们可以用它来找到所有共同祖先的一个有趣的特性。该属性简单地说，一个节点的所有孩子的左边都比左边的大，而右边的边少于右边。

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

以最低的左边和所有您想要一个共同的祖先节点的最高权利。在这种情况下，所选节点中最低的左侧为3，最高右侧为女性21。然后，您可以在3:21的统一节点空间上执行祖先查询。

在这种情况下，你会寻找一组节点，其中左< 3，右> 21.这将使您的集合中的所有共同祖先的。在这种情况下唯一的搭配就是服装。衣服上的1小于3,22大于21.

如果你有多个共同的祖先，但你想要最低的，你可以按照降序排列他们的左列，并采取第一个。

这在SQL中可能看起来像这样。我正在使用T-SQL，因此“顶级1”可能是限制1或其他类型的SQL。

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