중첩 세트 내에서 가장 낮은 공통 조상을 찾는 방법을 찾고 있습니다. 하나의 방정식을 사용하여 찾을 수 있습니다. 이미지에서의 예를 들어중첩 세트에서 가장 낮은 공통 조상 찾기
: https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg
정장과 여성 사이의 LCA는 의류입니다. 부모님이 만나는 곳을 파악하기 위해 레벨 기반 시스템을 사용할 수는 있지만이 경우의 사용 사례는 데이터베이스 디자인에 있으므로 단계적으로 올라가면 성능에 좋지 않을 수 있습니다.
저는 Suits (3 : 8)와 Women 's (10:21)를 사용하여 의류에 대한 조합 (1:22)을 얻는 한 번의 계산을 사용할 수 있기를 기대합니다.
중첩 세트에는 모든 공통 조상을 찾는 데 사용할 수있는 흥미로운 속성이 있습니다. 이 속성은 노드의 모든 자식이 왼쪽보다 왼쪽이 더 크고 오른쪽이 오른쪽보다 적음을 간단히 나타냅니다.
이것은 우리가 신경 써야 할 모든 노드가 포함 된 왼쪽 오른쪽 경계가있는 노드를 찾아야 함을 의미합니다. 우리가 찾고있는 범위를 설정하는 데 관심이있는 노드 집합을 사용하여이 작업을 수행 할 수 있습니다. 다음과 같이 쉽게 할 수 있습니다 :
공통 조상을 원할 모든 노드의 가장 왼쪽과 가장 오른쪽을 가져갑니다. 이 경우 선택한 노드의 가장 왼쪽 하단이 정장에 3 개이고 가장 높은 오른쪽에 여성이 21 개 있습니다. 그런 다음이 통합 노드 공간에서 3:21의 조상 쿼리를 수행 할 수 있습니다.
이 경우 왼쪽 노드 < 3과 오른쪽 21을 찾을 것입니다. 그러면 모든 공통 조상 집합이 생깁니다. 이 경우 유일한 일치는 의복입니다. 의류의 1은 3보다 작고 22는 21보다 큽니다.
가장 일반적인 조상이 있지만 가장 낮은 것을 원하면 왼쪽 열에 따라 내림차순으로 정렬하고 첫 번째 테이크를 가져올 수 있습니다.
이것은 SQL에서 이와 유사 할 수 있습니다. 나는 T-SQL을 사용하여 "top 1"이 SQL의 취향에 1 또는 다른 것을 제한 할 수 있습니다.
select top 1 * from Clothing where [left] < 3 and [right] > 21 order by [left] desc
너무 단순하지만 훌륭합니다. – Flosculus
이미지가 약간 흐릿 해 보입니다. 드레스와 양복 모두 그 숫자를 기반으로 한 아이를 가져야합니다. Wikipedia의 중첩 세트 페이지에는 동일한 계층 구조의 업데이트 된 버전이 있습니다. https://en.wikipedia.org/wiki/Nested_set_model – Devin