CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-treeintervals
Ecir Hana
Ecir Hana

Reputation: 11468

Augmented interval tree

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?

Upvotes: 4

Views: 1285

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

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.

Upvotes: 3

Related Questions