区间范围树数据结构c
发布时间：2020-12-16 09:56:08 所属栏目：百科 来源：网络整理
导读：我有一个要求,我必须根据一些属性值更新图形前端的颜色.属性值有不同的范围….比如-30到-45,-60到-80等等….那么,我需要一个数据结构,我可以存储这些范围(预填充它们)….当我确定这一点时,我想知道这一点落在O(1)时间或O的范围内(logN)时间….所以,我的查询
|
我有一个要求,我必须根据一些属性值更新图形前端的颜色.属性值有不同的范围….比如-30到-45,-60到-80等等….那么,我需要一个数据结构,我可以存储这些范围(预填充它们)….当我确定这一点时,我想知道这一点落在O(1)时间或O的范围内(logN)时间….所以,我的查询将由一个点组成,输出应该是包含该点的唯一范围…
我在范围树和段树之间感到困惑….我想在c stl地图上构建树. 解决方法
你需要的是间隔树.
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章. 相反,你可以使用提升.它有间隔容器库. http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |