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
摘要: 对形如([x1: x2], [-∞: y])的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O(n),插入、删除操作的时间复杂度为O(logn),搜索复杂度为O(logn+k)。
关键词:
动态优先搜索树,
区域树,
堆
CLC Number:
HUANG Hui-ping; LUK Wai-shing; XIAO Lin-fu; ZHAO Wen-qing. Realization and Application of Fast Dynamic Priority Search Tree[J]. Computer Engineering, 2009, 35(10): 40-43.
黄惠萍;陆伟成;肖林甫;赵文庆. 快速动态优先搜索树的实现及其应用[J]. 计算机工程, 2009, 35(10): 40-43.