Overview
A range tree is a multi-level search tree that stores points by coordinate so orthogonal range queries can report all points inside an axis-aligned query box.
CoreSource checked
Range Tree
Supports orthogonal range queries with a layered balanced-tree structure.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Advanced
- Family
- Orthogonal range searching
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Not ready
- Visualization
- Not ready
- Aliases
- Orthogonal range tree
Core Concepts
orthogonal range searchbalanced treesmultidimensional searchrange query
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log^d n + k) query after preprocessing
Average
O(log^d n + k) query after preprocessing
Worst
O(log^d n + k) query after preprocessing
Space
O(n log^(d - 1) n)
When to Use
- Use when exact orthogonal range reporting is more important than compactness.
When Not to Use
- Avoid when approximate nearest-neighbor search or dynamic updates are the primary task.
What It Does
- Indexes points by coordinate.
- Uses associated structures to answer multidimensional range queries.
- Reports points contained in an axis-aligned query range.
Use Cases
- Computational geometry
- Spatial databases
- Multidimensional indexing
Inputs
- A set of multidimensional points and an orthogonal range query.
Outputs
- The indexed points that fall inside the query range.
Pseudocode
- 1.Build a balanced tree on one coordinate.
- 2.Attach secondary structures for remaining coordinates.
- 3.Search split nodes and report matching secondary ranges.
Canonical Example
- Input
- A set of 2D points and an axis-aligned rectangle.
- Output
- All indexed points inside the rectangle.
- Explanation
- The tree restricts candidate points by coordinate ranges.
Implementation Notes
- Fractional cascading may be used in some variants to improve query time.
Common Pitfalls
- Confusing range trees with k-d trees, which have different decomposition and query tradeoffs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow a range tree decomposition and highlight reported points inside an axis-aligned query box.
Step 1 of 3: Build a balanced tree on one coordinate.
tree-queryNotes
Range trees trade extra storage and preprocessing for exact orthogonal range reporting; dynamic updates and high-dimensional data may need different structures.
Sources (2)
What each reference supports for this entry.
Bentley (1979)
PaperSupports decomposable searching and multidimensional search context used by range-search structures.
Open sourceBentley and Friedman (1979)
PaperSurveys data structures for range searching and supports the orthogonal range-query role of range-search structures.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsed byOrthogonal Range Search
Range trees are a standard data structure used to answer orthogonal range-search queries.
Alternative tok-d Tree
Range trees and k-d trees are alternative multidimensional indexing structures with different storage and range-query tradeoffs.
Related Algorithms
Tags
TreeRange Query