查找重叠于某点所有区间的一种数据结构

摘要

快速查找重叠于某点的所有区间集是计算机图形学、模式匹配及其他应用中急需解决的问题之一.通过介绍了一种用于查找所有重叠于某个特殊点的区间的数据结构区间空指令表,这种数据结构与AVL树具有相似的功能与特性,但执行起来比AVL树简单得多,它能够实现快速查找重叠于某点的所有区间集.搜索包含n个区间的空指令表以寻找重叠于一个点的区间约需时间为O(logn+L),L代表匹配区间的数目,插入或删除一个区间所需时间为O(log2n).图1,参5.