Looking for an efficient Interval tree Algorithm

1
votes

I have a set of objects which store intervals given by the low and high value. I'm searching for a data struture, which will allow me to get all objects, whose intervals overlap with a given point in real-time. I also need to be able to add and delete single objects as fast as possible. Interval trees based on Red-Black trees have O(log n) insertion and deletion time and O(n) space. But the query to find all overlaps takes O(k log n) time, which can be worse than brute-force search, if there are many overlapping intervals. Is there a better way to do this?

1
algorithmtreecomplexity-theoryintervals

1 Answers

1
votes

Interval trees are made for this job. Finding all the intervals that overlap a point takes O(k + log n) time, not O(k log n).

This is the "centered interval tree" as mentioned in your wikipedia link. It's reasonable to implement one of these based on red-black trees:

  • The main tree would be a red-black tree. Each node would have its center point and interval lists. You create a new node whenever you insert a new interval that doesn't overlap any existing center points. You delete a node whenever you delete all of its center-point-overlapping intervals.
  • The rotation operations performed to balance the RB-tree will require you to move some center-point-overlapping intervals up from child nodes to their new parents. Each node should store its lists of center-point-overlapping intervals in other red-black trees, so that this movement can be done in log(n) time. Note that an RB tree does an amortized constant number of rotations per insert/delete.

However... since it seems that you have not already done this with RB-trees, and RB-trees are complicated, I would suggest doing the same thing with treaps instead: https://en.wikipedia.org/wiki/Treap

Treaps will be much easier than RB trees, because they're simpler to begin with, and they don't require rotations to keep them balanced, which makes it much easier to maintain the lists of center-point-overlapping intervals. Those intervals can be stored in treaps as well.

Much easier... but still not that easy :-)