【摘要】 对形如([x1:x2],[-∞:y])的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O(n),插入、删除操作的时间复杂度为O(logn),搜索复杂度为O(logn+k)。更多还原

【Abstract】 A fast Dynamic Priority Search Tree(DPST) is proposed for 2-D range query in form of([x1:x2],[-∞:y]).The proposed DPST stores input data only in its leaf nodes and performs tree rotation in constant time.Let n be the total number of leaf nodes in the tree,and k be the number of solutions in query.The tree requires takes O(n) storage space and takes O(logn) for insertion and deletion,and O(logn+k) time for query.更多还原