The point-range tree
Moez Chaabouni, Soon Myoung Chung · 1993
In this paper, we propose a data structure, the Point-Range Tree (PR-Tree), specifically designed for indexing intervals. With the PR-Tree, a point data can be queried against a set of intervals to determine which of those intervals overlap the point. The PR-tree allows dynamic insertions and deletions while it maintains itself balanced. A balanced PR-Tree takes Ο(log n) time for search. Insertion, deletion, and storage space have worst case requirements of Ο(n log n + m), Ο(n log2 n + m), and Ο(n log n), respectively, where n is the total number of intervals in the tree, and m the number of nodes visited during insertion and deletion. A modified version of the PR-Tree is also developed to minimize space usage. An additional advantage of the PR-Tree is that it can be easily extended to multi-dimensional domains.