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

• 作者: 肖林甫 赵文庆 陆伟成 黄惠萍
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 动态优先搜索树 区域树 堆
• 年，卷（期）: 2009,（10）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 40-43,48
• 页数: 5页
• 分类号: TP311
• 字数: 5556字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2009.10.013

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄惠萍	复旦大学专用集成电路与系统国家重点实验室	2	6	2.0	2.0
2	陆伟成	复旦大学专用集成电路与系统国家重点实验室	14	31	3.0	4.0
3	赵文庆	复旦大学专用集成电路与系统国家重点实验室	11	68	4.0	8.0
4	肖林甫	复旦大学专用集成电路与系统国家重点实验室	1	4	1.0	1.0