ネストされたセット内の最も低い共通祖先を見つける

Question

ネストされたセット内の最も低い共通祖先を見つける方法を探しています。画像からの例えば

、：https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg

スーツと女性の間のLCAは、衣料品です。私は、レベルベースのシステムを使用して、親がどこで会うのか把握することができますが、これのユースケースはデータベース設計のため、レベルを上げるとパフォーマンスに悪影響を及ぼします。

私はSuits（3：8）とWomen's（10:21）を使用して衣類の組み合わせ（1:22）に達することができることを望んでいます。

Answer 1

ネストされたセットには、すべての共通の祖先を見つけるために使用できる興味深いプロパティがあります。このプロパティは、ノードのすべての子ノードの左辺が左辺より大きく、右辺が右辺よりも小さいことを示しています。

これは、私たちが気にするすべてのノードを含む右端の境界を持つノードを見つける必要があることを意味します。私たちが探している範囲を設定するために気にするノードのセットを使って、これを行うことができます。

共通の祖先が必要なすべてのノードの左下と右上を取ることができます。この場合、選択したノードの左下がスーツで3、あなたの最も高い右が女性で21です。この統一されたノード空間の3時21分に祖先クエリを実行できます。

この場合、左に< 3と右端に21のノードのセットがあります。これは、すべての共通の祖先のセットを提供します。この場合、衣服だけが一致します。衣類の1は3未満、22は21より大きい。

共通の祖先が複数あるが、最低のものを希望する場合は、左の列で降順にソートして最初のものを取ることができます。

これはSQLで次のようになります。私はT-SQLを使用しているので、「トップ1」はSQLのフレーバーに1またはその他の制限があります。

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