Working of a Range Tree
A range tree is made recursively. A BST(Binary Search Tree) on a dimension of points constitutes one level of a range tree and this is done until all the points are addressed which means the first level of the range tree is the BST of the first dimension of points and so on.
Each node of the tree has two information in it:
- The range of points for which the node is responsible.
- The maximum value of a point in the range of node.
To address a range query, recursive traversal of the tree is done. The interval of query is compared to the range of each node in the tree. If the interval intersects the range of node, then the maximum value of the node’s range is reported and if this is not the case then the traversal is continued on next dimension of the query interval which is the child node.