快速动态优先搜索树的实现及其应用  

Realization and Application of Fast Dynamic Priority Search Tree

作　　者：黄惠萍[1] 陆伟成[1] 肖林甫[1] 赵文庆[1] 

机构地区：[1]复旦大学专用集成电路与系统国家重点实验室,上海201203

出　　处：《计算机工程》2009年第10期40-43,48,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(90307017;60676018);教育部高等学校博士学科点专项科研基金资助项目(20050246082);上海市自然科学基金资助项目(05JC14007)

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

关 键 词：动态优先搜索树 区域树 堆 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]