区间树

编辑:媒介网互动百科 时间:2020-04-08 18:53:49
编辑 锁定
本词条缺少信息栏名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
区间树是在红黑树基础上进行扩展得到的支持以区间为元素的动态集合的操作,其中每个节点的关键值是区间的左端点。

目录

区间树区间树

编辑
通过建立这种特定的结构,可是使区间的元素的查找和插入都可以在O(lgn)的时间内完成[1] 
相比于基础的数据结构,增加了一个max[x],即以x为根的子树中所有区间的端点的最大值。区间树如下图所示:
这里的区间查找的并不是精确查找,而是查找和给定区间重叠的元素,重叠的定义如下图所示:
图中(a)表示两个区间重叠的情况,其他的(b)、(c)表示没有重叠的情况。

区间树区间查找

编辑
实现INTERVAL-SEARCH(T, i),返回一个和区间i重叠的区间,若无,则返回nil[T]。基本思想是我们通过左子树的max进行划分:如果左子树的max值小于low[i],则左子树不存在这样的区间和i重叠,转到右子树;否则,转到右子树,因为左子树的端点小于右子树,若左子树无可能,右子树也必然不可能。
参考资料
词条标签:
非科学 科学