| 快速动态优先搜索树的实现及其应用 |
| |
| 引用本文： | 黄惠萍,陆伟成,肖林甫,赵文庆.快速动态优先搜索树的实现及其应用[J].计算机工程,2009,35(10):40-43. |
| |
| 作者姓名： | 黄惠萍 陆伟成 肖林甫 赵文庆 |
| |
| 作者单位： | 复旦大学专用集成电路与系统国家重点实验室,上海,201203 |
| |
| 基金项目： | 国家自然科学基金，教育部高等学校博士学科点专项科研基金，上海市自然科学基金 |
| |
| 摘 要： | 对形如（x1：x2,-∞：y]）的二维查询问题，提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法，采用只在叶节点存储数据的结构，以及在常数时间内实现旋转操作的算法。设n为数据点的个数，k为满足搜索条件的解的个数，则该动态搜索树空间复杂度为O（n），插入、删除操作的时间复杂度为O（10gn），搜索复杂度为O（logn＋k）。
|
| 关 键 词： | 动态优先搜索树 区域树 堆 |
| 修稿时间： | |
Realization and Application of Fast Dynamic Priority Search Tree |
| |
| HUANG Hui-ping,LU Kai-shing,XIAO Lin-fu,ZHAO Wen-qing.Realization and Application of Fast Dynamic Priority Search Tree[J].Computer Engineering,2009,35(10):40-43. |
| |
| Authors: | HUANG Hui-ping LU Kai-shing XIAO Lin-fu ZHAO Wen-qing |
| |
| Affiliation: | State Key Lab of ASIC & System;Fudan University;Shanghai 201203 |
| |
| 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. |
| |
| Keywords: | Dynamic Priority Search Tree(DPST) range tree heap |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
