A range tree is a multi-level tree data-structure to store a finite subset of a multi-ordered set such that range searches can be efficiently answered for .
The range tree implementation in Pastel has the following restrictions:
After the construction points can be added or removed only by a complete reconstruction.
We require the range tree to have at least 2 strict weak orders (). This is an accidental discontinuity; due to fractional cascading we could not come up with a clean uniform design which would have also allowed a single strict weak order.
The single-order range-tree can be recovered exactly by using an additional trivial strict weak order (always returning false) for the second order. The range tree then consists of a binary search tree for the first order, and a range-search works as usual, reporting all points in all intermediate subtrees (since all points are equivalent with respect to the second order).
A more efficient work-around, due to locality of reference, is to use an additional trivial strict weak order for the first order. The range tree then consists of a single node which contains all the points ordered with respect to the first strict weak order, and a range-search is a single binary search in that node, followed by a linear scan.
The range tree implementation in Pastel has the following properties:
| Property / Task | Complexity |
|---|---|
| Construct the tree from points. | |
| Space |
Here is the number of points in the tree, and is the number of strict weak orders.
The space complexity degrades gracefully as points become equivalent with respect to the orders. For example, if the points are all equivalent in the first orders, for , then the data-structure takes only space. More generally, the space complexity is sensitive to the number of comparisons needed to separate points; points which are equivalent with respect to some order do not need to be separated by that order.