在一組嵌套

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