空间剖分树形查找结构的效率分析

摘要

Space subdivision is a key and efficient way for constructing data structures of point searching, such as quad-tree, octree and Kd-tree and so on, which are typical data structures constructed on space subdivision. How to choose suitable parameters to construct the tree structures has obvious and significant impact on the efficiency of the algorithms that the structures are involved in. In this paper, based on analyzing the basic ideas of these three tree structures, it investigates and discusses the relationship between the parameters of the trees and the time-efficiency of the algorithms by a set of point data with various space distributions. It gives optimized tree-parameters finally. The conclusion can provide a useful guide for constructing optimized tree structures for point searching algorithm.%空间剖分是构造快速空间查找数据结构的有效方法，四叉树、八叉树、Kd-树是典型的基于空间剖分思想的树形空间查找结构。选择合适的参数来构造实际点集数据的树形查找结构，对提高相关算法的效率具有重要意义。在分析三种树形查找结构基本原理的基础上，通过构造具有不同空间分布特征的实验数据，设置不同的树形空间剖分结构参数，来分析三种结构支持下搜索算法的时间消耗，确定使查找效率达到最优的树形结构构造参数。相关研究结论对于优化空间剖分树形查找结构的效率、提高相关算法的性能等，有一定的参考价值。