 |
 |
 |
|
 |
|
|
 |
 |
 |
Binary Tree
Two dimensions
This best known technique applies the principle of divide-and-conquer to the organization and search for point data. This range search technique makes use of a binary tree to order the data with respect to their x and y coordinates. Initially a feature located approximately centrally within the range of x coordinates is chosen to partition the data set vertically into two halves. In each half another feature is chosen in similar manner to partition the halves along horizontal lines passing through these features. The process of splitting stops whenever a new subregion contains no other points.
 k-D-tree |
 |
The branching factor of binary trees is at most 2. In fact every fork has none, one or max. two branches. The numbers of binary trees of height h = 1, 2, ... are 1, 3, 21, 651, 457653, ...
 |
H = 1 level -> 1 tree |
 |
H = 2 levels -> 3 different trees |
 |
H = 3 levels -> 21 possible trees |
Higher dimensions
The range search approach can be extended into higher dimensionality by considering planes or hyperplanes, which partition the k-dimensional space into two. As the tree is descended, splitting will take place for each dimension in turn. The general tree structure is called k-D tree, standing for k-dimensional binary tree (Jones 1997).
Binary search scheme
The tree resulting from the recursive splitting of the data space can be searched to determine points that lie inside a search rectangle, for instance named D. Starting at the root, a test is performed to determine whether D lies in one or other of the two regions separated by the point stored in the root node. If D does lie entirely within one side or the other, the corresponding branch of the tree is descended and a similar test is preformed with the point in that node. If, however, D is found to cross the partitioning line, a test is performed to find whether the point in the node lies inside the window. If it does, it is saved. The search then continues down the branches of the tree before applying the same logic to each of the two branch nodes. The search terminates at individual nodes when the node is a leaf, i.e. there are no branches to descend.
 |
 |
 |
|
|
|
|
|
|
|
