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