摘要
对形如([x1:x2],[-∞:y])的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O(n),插入、删除操作的时间复杂度为O(logn),搜索复杂度为O(logn+k)。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2009年第10期40-43,48,共5页
Computer Engineering
基金
国家自然科学基金资助项目(90307017
60676018)
教育部高等学校博士学科点专项科研基金资助项目(20050246082)
上海市自然科学基金资助项目(05JC14007)
关键词
动态优先搜索树
区域树
堆
Dynamic Priority Search Tree（DPST）
range tree
heap
