python 2和3的可编辑间隔树数据结构
intervaltree的Python项目详细描述
间隔树
python 2和3的可变的、自平衡的间隔树。查询可以是按点、按范围重叠或按范围包络。
此库旨在允许标记文本和时间间隔，其中间隔包括下限但不包括上限。
版本3更改！
搜索（begin，end，strict）方法不再存在。相反，请使用以下选项之一：在（点）重叠（开始，结束）信封（开始，结束）
extend（items）方法不再存在。相反，使用update（items）- 像
merge_overlaps（）这样的方法将strict参数始终默认为strict=true。以前，有些方法默认为true而另一些方法默认为false
安装
pip install intervaltree
功能
支持Python2.7和Python3.4+（在2.7和3.4到3.7下测试）
初始化
- 空白
tree=intervaltree（） - 从
interval对象（树=interval tree（interval）） - 从一个元组的iterable（
tree=intervaltree.from-tuples（interval-tuples））
- 空白
插入
树[开始：结束]=数据树.添加（间隔）tree.addi（开始、结束、数据）
删除
树。删除（间隔）（如果不存在，则引发值错误）tree.discard（interval）（如果不存在，请安静）tree.removei（开始、结束、数据）（tree.remove（间隔（开始、结束、数据）））tree.discardi（开始、结束、数据）（简称tree.discard（间隔（开始、结束、数据）））树。删除重叠（点）树。删除重叠（开始，结束）（删除所有重叠的范围）树。移除信封（开始，结束）（移除范围内的所有信封）
点查询
树[点]树。在（点）（与上一个相同）
重叠查询
树[开始：结束]树。重叠（开始，结束）（与上一个相同）
包络查询
树.信封（开始，结束）
会员查询
树中的间隔对象（这是最快的，o（1））tree.containsi（开始、结束、数据）树。重叠（点）树。重叠（开始，结束）
Iterable
对于树中的间隔对象：tree.items（）
调整大小
长度（树）树。是否为空（）不是树tree.begin（）（最左边间隔的begin坐标）tree.end（）（最右边间隔的end坐标）
设置类似操作
联合< /P>
结果树=tree.union（iterable）结果树=树1树2树.更新（iterable）树=其他树
NCE/P>
结果树=tree.difference（iterable）结果树=tree1-tree2树。差异更新（iterable）树-=其他树
交叉口
结果树=tree.intersection（iterable）结果树=tree1&tree2树.交集更新（iterable）树&；=其他树
对称差分
结果树=树。对称差分（iterable）结果树=tree1^tree2树.对称差分更新（iterable）树^=其他树
比较
tree1.issubset（tree2）或tree1<；=tree2tree1<；=tree2tree1.issueperset（tree2）或tree1>；tree2tree1>；=tree2tree1==tree2
重组
chop（begin，end）（切片间隔并删除begin和end之间的所有内容，可以选择修改分割间隔的数据字段）切片（点）（切片间隔在点）split_overlaps（）（在所有间隔边界切片，可以选择修改数据字段）merge_overlaps（）（将重叠间隔合并为单个间隔，可以选择合并数据字段）merge_equals（）（将具有匹配范围的间隔合并为单个间隔，可以选择合并数据字段）
复印和排版
interval tree（tree）（interval对象与tree中的对象相同）tree.copy（）（interval对象是树中对象的浅层副本）集合（树）（以后可以输入intervaltree（））列表（树）（同上）
泡菜友好型
自动AVL平衡
示例
入门
>>>fromintervaltreeimportInterval,IntervalTree>>>t=IntervalTree()>>>tIntervalTree()
添加间隔-任何对象都有效！
>>>t[1:2]="1-2">>>t[4:7]=(4,7)>>>t[5:9]={5:9}
按点查询
查询的结果是一个
set对象，因此如果排序很重要， 必须先排序。>>>sorted(t[6])[Interval(4,7,(4,7)),Interval(5,9,{5:9})]>>>sorted(t[6])[0]Interval(4,7,(4,7))
按范围查询
请注意，范围包括下限，但不包括上限。所以：
>>>sorted(t[2:4])[]
因为我们的搜索超过了
2≤x<；4，所以既没有间隔（1，2）也没有间隔（4，7）包括在内。第一个间隔，1≤x<；2不包括x=2。第二 间隔，4≤x<；7确实包括x=4，但我们的搜索间隔不包括它。所以， 没有重叠的间隔。然而：>>>sorted(t[1:5])[Interval(1,2,'1-2'),Interval(4,7,(4,7))]
仅返回完全被搜索范围包围的间隔：
>>>sorted(t.envelop(1,5))[Interval(1,2,'1-2')]
访问
时间间隔对象>>>iv=Interval(4,7,(4,7))>>>iv.begin4>>>iv.end7>>>iv.data(4,7)>>>begin,end,data=iv>>>begin4>>>end7>>>data(4,7)
从区间列表构造
我们可以这样做一棵类似的树：
>>>ivs=[(1,2),(4,7),(5,9)]>>>t=IntervalTree(...Interval(begin,end,"%d-%d"%(begin,end))forbegin,endinivs...)
或者，如果不需要数据字段：
pip install intervaltree
0甚至：
pip install intervaltree
1删除间隔
pip install intervaltree
2我们也可以完全清空一棵树：
pip install intervaltree
3或删除重叠范围的间隔：
pip install intervaltree
4我们也只能删除完全包含在一个范围内的那些间隔：
pip install intervaltree
5切碎
我们还可以砍掉树的一部分：
pip install intervaltree
6要根据要截断的间隔的哪一侧修改新间隔的数据字段，请执行以下操作：
pip install intervaltree
7切片
也可以在树中切片间隔，而不删除EM：
pip install intervaltree
8您还可以设置数据字段，例如，重新使用上面的
datafunc（）：pip install intervaltree
9
未来改进
请参阅github上的问题跟踪器。
基于
- 永远困惑的AVL树
- 维基百科的间隔树
- 从tyler-kahn的python中的间隔树实现中对其进行了大量修改（github项目）
- 包括来自：
- 塔尔图大学（爱沙尼亚）的康斯坦丁/康斯坦丁特里亚科夫
- sinig/avi gabay
- 德国卡尔斯鲁厄理工学院的lmcarril/luis m.carril
版权所有
- chaim leib halbert，2013-2018年
- 修改，konstantin tretyakov，2014年
在2.0版的apache许可证下获得许可。
此项目的源代码位于https://github.com/chaimleib/intervaltree" rel="nofollow">https://github.com/chaimleib/intervaltree
欢迎加入QQ群-->： 979659372
