Abstract:

This paper proposes a data structure that uses the binary tree to organize multidimensional data.Based on the proposed data structure,an area search algorithm is proposed in order to find out all points in the given data set in the domain of given points.The search efficiency of the algorithm is not related with the space dimension.The average time complexity of the algorithm is O(logn).To guarantee the algorithm efficiency,the paper also proposes a balanced tree adjustment algorithm.

Key words: search tree;spatial data;area search