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

Question

我正在寻找一种使用单个公式在嵌套集中查找最近公共祖先的方法。

例如，从此图中：https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg 可以看出，Suits和Women's之间的LCA是Clothing。我可以使用基于级别的系统来确定父级相遇的位置，但这种用例是在数据库设计中使用的，因此升级级别将对性能产生不利影响。我希望可以使用单个计算，使用Suits（3：8）和Women's（10：21）来得出Clothing（1：22）的组合，如果存在这样的方程式的话。

- Flosculus

---

那张图片看起来有些不对劲。根据那些数字，连衣裙和西装都应该有子节点。维基百科上关于嵌套集的页面有一个更新版本的同一层次结构。https://en.wikipedia.org/wiki/Nested_set_model - Devin

Answer 1

嵌套集合有一个有趣的特性，我们可以用它来找到所有共同的祖先。这个特性很简单，即一个节点的所有子节点的左边界都大于该节点的左边界，右边界都小于该节点的右边界。

这意味着我们需要找到具有包含我们关心的所有节点的左右边界的节点。我们可以使用我们关心的节点集来设置我们要查找的边界。我们可以这样轻松地完成：

取出你想要一个共同祖先的所有节点的最低左边界和最高右边界。在这种情况下，你选择的节点的最低左边界是3，而最高右边界是Women's上的21。然后你可以在3:21的统一节点空间上执行一个祖先查询。

在这种情况下，你要寻找的是一个左边界小于3且右边界大于21的节点集合。这将给你所有共同的祖先集合。在这种情况下，唯一匹配的是clothing。clothing上的1小于3，22大于21。

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

在SQL中，这可能看起来像这样。我使用T-SQL，所以“top 1”可能在你的SQL版本中是limit 1或其他什么。

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

- Devin

---

如此简单，却又充满智慧。 - Flosculus