摘要： 对形如([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.

Key words: Dynamic Priority Search Tree(DPST), range tree, heap

中图分类号: 

• TP311