区间范围树数据结构c++

Question

我有一个要求，我必须根据某些属性更新图形前端的颜色 value.The 属性值有不同的范围....比如 -30 到 -45，-60 到 -80等等......所以，我需要一个数据结构，我可以在其中存储这些范围（预填充它们）......当我确定点时，我想知道这个点落在的范围O(1) 时间或 O(logN) 时间....因此，我的查询将由一个点组成，输出应该是包含该点的唯一范围...

我对范围树和线段树感到困惑....我想在 c++ stl 映射之上构建树。

Answer 1

你需要的是区间树。 http://en.wikipedia.org/wiki/Interval_tree。不幸的是，你不能使用 std::set<> 来获得 O(log N) 插入、删除和查询，因为树节点需要包含额外的数据。你可以在这里阅读它们 http://syedwaqarahmad.webs.com/documents/t.cormen-_introduction_to_algorithms_3rd_edition.pdf 第 14.3 章

相反，您可以使用 boost。它有间隔容器库。

http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

Answer 2

也许这个图书馆可以帮助你： https://github.com/ekg/intervaltree

Answer 3

如果我理解正确的话，你可以很容易地用 std::set:

#include <iostream>
#include <set>


struct Interval {
    int min;
    int max;
};

struct ComInt {
    bool operator()(const Interval& lhs, const Interval& rhs){
        return lhs.max < rhs.min;
    }
};

std::set<Interval, ComInt> intervals = { { -10, -5 }, { -4, 4 }, { 5, 10 } };


int main() {
    int point = 3;
    Interval tmp = { point, point };

    auto result=intervals.find(tmp);
    if (result != intervals.end()) {

        std::cout << "Min:" << result->min << " - Max:" << result->max << std::endl;
    } else {
        std::cout << "No matching Interval found" << std::endl;
    }
}

当然你应该围绕它构建一个包装器class

区间范围树数据结构c++

interval range tree datastructure c++

c++

stl

range-tree