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

A data structure for finding all intervals that overlap a point

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

Highspeed finding of the collection of all intervals overlapping a point is one of the urgent problems to be solved in the applications of computer graphology and mode matching. This paper introduces a data structure to find all intervals overlapping a pointthe interval skip list.The function and property of this data structure is similar to that of AVL Tree. ( AVL Tree is a kind of balanced tree with two branches. The property of the tree is that the height difference between the left branch and the right one at any point is not more than 1. It's quite efficient to inquire and retrieve by this tree structure.) With regard to execution , however, it's much easier than that of AVL Tree because it can find the collection of all intervals overlapping a point in high speed. Searching an ISlist containing n intervals to find intervals overlapping a point takes expected time O(logn+L) where L is the number of matching intervals. Inserting or deleting an interval takes expected time O(log2n).1fig.,5refs.