Augmented interval tree

4
votes

I'm trying to implement augmented interval tree by using balanced binary search tree ordered by "'low' values of the intervals".

In plain old search trees, when trying to insert a key already present in the tree, it is common to just ignore the duplicate (no insertion).

But when storing intervals, I might have (1,2) and (1,3) which have the same 'low' value but are distinct.

How to deal with duplicate 'low' values in augmented interval trees? I mean, should I allow insertion of multiple same 'low' values? In what order? And how to search through the tree if there are duplicate keys?

1
algorithmdata-structuresbinary-search-treeintervals
One option is to replace the old interval with the new interval if the old interval is totally contained in the new one, as in this example. – ramana_k
obviously store both intervals, keys are keys and values are values. No one says you can have multiple values associated with a key. – user1095108

1 Answers

3
votes

The linked article suggests using the high value of each interval as a secondary ordering. Then you have a total order on intervals, and you can just search normally. Intersection queries don't require a particular order among intervals with the same low value; this will become obvious once you write the code.