바이러스 성 또는 제한적인 라이센스없이 효율적으로 C++ 간격 트리 구현 (주로 검은 색 나무를 기반으로 함)을 찾으려고합니다. 깨끗하고 가벼운 독립 실행 형 구현에 대한 지침이 있습니까? 내가 생각하고있는 유스 케이스의 경우, 인터벌 세트는 처음에 알려졌고 (백만 개가있을 것입니다) 주어진 간격과 겹치는 간격 목록을 빨리 얻을 수 있기를 원합니다. 따라서 한 번 작성된 트리는 변경되지 않으며 빠른 쿼리가 필요합니다.C++ 간격 트리 알고리즘 구현 찾기
C++ 표준 라이브러리는 빨강/검정 나무 std::map, std::multimap, std::set 및 std::multiset을 제공합니다.
정말, 나는 반복자 쌍의 std::map을 유지하고 upper_bound() 및 lower_bound()에 그 반복자 쌍을 통과하는 것보다 더 효율적으로이 문제를 해결할 수있는 방법을 생각할 수 없다. 인터벌에서 쌍이 될 가능성이있는 부분을 쉽게 제로로 만들 수 있도록 반복자 쌍을지도 자체에 보관해야합니다. ("후보 간격"의 시작 반복자가 지정된 간격의 끝에서 오는 경우 당신이보고있는 것을 볼 수 있습니다. 그런 다음 모든 반복자 쌍을 검사하는 것을 건너 뛸 수 있습니다.
저는 C++에서 템플릿 기반 간격 트리 구현 인 https://github.com/ekg/intervaltree을 작성했습니다. MIT 라이센스. 즐겨.
이 구현은 일단 트리가 생성되면 트리를 변경할 수 없다는 것, 즉 정적 간격 트리를 구성한다는 점에 유의하십시오. '동적 인'나무는 http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html을 참조하십시오. – logion
또한 this link에 간격 트리의 C# 구현이 있습니다. 도움이 필요한 사람들을 위해 C++로 쉽게 번역 할 수 있습니다.
지도/세트를 간격 나무로 구현하는 방법에 대해 좀 더 설명해 주시겠습니까? – Kyuubi
@ Kyuubi :'std :: map' /'std :: set' (즉,'std :: map' /'std :: set'로 시작하여 간격 트리로 끝나는) ** 인터벌 트리로 시작해서'std :: map','std :: set'을 구현하는 것은 아닙니다. –
@Kyuubi 추억으로 떠나는 생각은, 당신이 (1) 사물의 컬렉션, (2) 당신이보고 있던 컬렉션의 간격 목록, (3) 당신이 ' begin과 end 반복자. 그래서,'std :: map'을 사용하면'begin' 반복자를 키로 만들고,'it' 반복자를 값으로 사용할 수 있습니다. 이를 사용하면 한 번에 원하는 모든 간격을 찾을 수 없지만 필터링해야하는 간격을 좁힐 수 있습니다. –