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

Question

我有一个需求，需要根据某个属性值更新图形前端的颜色。该属性值具有不同的范围，例如-30到-45，-60到-80等等。因此，我需要一种数据结构来存储这些范围（预先填充它们）。当我确定点时，我想知道该点所在的范围是O(1)时间还是O(logN)时间内的唯一范围。因此，我的查询将包含一个单独的点，并且输出应该是包含该点的唯一范围...

我在范围树和线段树之间感到困惑...我想在C++ STL map上构建树。

- basav

---

我不确定我理解你想要什么。你能给一个简单的例子吗？ - MikeMB

这些范围是否不相交？ - MikeMB

可能是重复的问题：如何判断一个点是否在一组区间内？ - Michal Hosala

范围可能是30-45、45-70、70-85等。我读取了一个属性值，现在想知道这个属性属于哪个区间（范围）？ - basav

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

- Ashot

---

区间树以区间作为输入，并将重叠的区间作为输出？如果我错了，请纠正我。 - basav

确切地说，如果您提供一个点（左右相等的区间），那么您将得到包含该点的区间。 - Ashot

好的，现在明白了...所以，即使在插入时，也没有单点的概念...一切都基于间隔...谢谢。 - basav

Answer 2

如果我理解你的意思正确的话，你可以很容易地使用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;
    }
}

当然，你应该围绕它构建一个包装类。

- MikeMB

---

这对于少量间隔来说非常有用...这绝对是一个方便的解决方案...但是如果我有大量的间隔呢？我认为时间复杂度会变成O(n)... - basav

@basav：我不这么认为，因为std::set本身通常被实现为一棵树（set::find具有对数复杂度）。 - MikeMB

查了一下...它确保了常数时间复杂度，并且很可能会被实现为红黑树。我将尝试使用std::set...我有大约100个区间...将尝试两种解决方案。谢谢。 - basav

@basav：那么你当然是正确的（无论如何都应该进行测量）。如果您有时间实现和测试所有三种变体，我真的很想看看哪个是收支平衡点。 - MikeMB

我在工作场所没有那么多时间……但我一定会在自己的时间里完成它，并在本周末之前更新结果……我会在这里更新。 - basav

Answer 3

也许这个库可以帮助您： https://github.com/ekg/intervaltree

- Philipp Claßen