Multi-Dimensional Range Search Tree
What It Does
A multi-dimensional range search tree (also known as a range tree) is a data structure for efficiently
locating points contained within a specified multi-dimensional region (box).
A sample query: Given a set of points in 3D, find all points such that:
10 <= point.X <= 15
35 <= point.Y <= 67
24 <= point.Z <= 32
The above three constraints define a multi-dimensional range (or box). Once built,
this search tree is able to answer any such query efficiently.
What It Looks Like
A multi-dimensional range search tree data structure is actually a collection of
many trees. In the implementaion provided on this page, items are only present in the leaf nodes.
Intermediate nodes are simply used for guiding a search. For searching within
the first dimension, there is a single search tree. Each internal node of the
first dimension search tree points to a tree for searching within the second
dimension as in the example above.
This pattern of trees pointing to other trees can continue for more than two
dimensions. For example, if the items were three dimensional, each internal node
of each second dimension search tree would point to a third dimension search
tree.
This may seem like it takes a lot of space, but it has been proven that the total
amount of space of this data structure is O(n·logd-1(n)) where
n is the number of nodes and d is the number of dimensions.
Complexity Gaurantees
Let n be the number of points, d be the number of dimensions, and
t be the number of points that match the search criteria (are in the
multi-dimensional range). Then the complexities are:
- Build Time: O(n·logd-1(n))
- Space: O(n·logd-1(n))
- Query Time: O(logd(n) + t)
2D Demo
The following is a 2D demo that uses the C# source code provided on this page. You must have
Microsoft Silverlight
2 or a later version
installed to view it.
Source Code
Download
- C# Source Code for an arbitrary number of dimensions.
This implementation does not allow inserting or removing elements; the tree is
built once and for all.
Sample Usage
The following code sample, creates a list of several points and uses the
multi-dimensionalge range search tree data structure to get all points for which
2 <= x <= 5 and 3 <= y <= 5.
// Create a list of points.
List<Point> points = new List<Point>()
{
new Point(3, 6),
new Point(2, 5),
new Point(5, 2),
new Point(2, 1),
new Point(3, 4),
new Point(4, 4),
new Point(2, 6),
new Point(2, 2)
};
// Create a new range search tree for the points, specifying that it should have 2 dimension.
RangeSearchTree<Point> tree = new RangeSearchTree<Point>(2, points);
// Get all of the points in the range determined by the two corner points (2, 3) and (5, 5).
List<Point> pointsInRange = tree.GetAllInRange(new Point(2, 3), new Point(5, 5));
Related Work
|