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

摘要：

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

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

所属期刊栏目：35

分类号：TP311(计算技术、计算机技术)

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

在线出版日期：2009-06-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：40-43,48