首页 | 本学科首页   官方微博 | 高级检索  
     


Quad trees a data structure for retrieval on composite keys
Authors:R A Finkel  J L Bentley
Affiliation:(1) Computer Science Department, Stanford University, 94305 Stanford, Calif., USA;(2) Computer Science Department, University of North Carolina, 27514 Chapel Hill, North Carolina, USA
Abstract:Summary The quad tree is a data structure appropriate for storing information to be retrieved on composite keys. We discuss the specific case of two-dimensional retrieval, although the structure is easily generalised to arbitrary dimensions. Algorithms are given both for staightforward insertion and for a type of balanced insertion into quad trees. Empirical analyses show that the average time for insertion is logarithmic with the tree size. An algorithm for retrieval within regions is presented along with data from empirical studies which imply that searching is reasonably efficient. We define an optimized tree and present an algorithm to accomplish optimization in n log n time. Searching is guaranteed to be fast in optimized trees. Remaining problems include those of deletion from quad trees and merging of quad trees, which seem to be inherently difficult operations.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号