Finding C++ Interval Tree Algorithm Implementation

C implementation of an interval tree?

C code for a red and black tree, licensed with the very generous MIT license.

_{(Backup at archive.org.)}

C++ - interval tree implementation

Boost-like ? Boost ICL!

The Boost Interval Container Library

Interval Tree algorithm inplementation

max is needed to find the overlap, eg use this data

 {{15, 20}, {10, 11}, {17, 22}, {5, 20}, {12, 25}, {30, 40}};

and search for 24

Data structure for handling intervals

It sounds like you could just use a balanced binary tree of all the boundary times.

For example, represent {(1,4), (8,10), (12,15)} as a tree containing 1, 4, 8, 10, 12, and 15.

Each node needs to say whether it's the start or end of an interval. So:

                          8 (start)
                         /        \
                1 (start)         12 (start)
                      \             /      \
                     4 (end)   10 (end)   15 (end)

(Here all the "end" nodes ended up at the bottom by coincidence.)

Then I think you can have all your operations in O(log n) time. To add an interval:

• Find the start time. If it's already in the tree as a start time, you can leave it there. If it's already in the tree as an end time, you'll want to remove it. If it's not in the tree and it doesn't fall during an existing interval, you'll want to add it. Otherwise you don't want to add it.

• Find the stop time, using the same method to find out if you need to add it, remove it, or neither.

• Now you just want to add or remove the abovementioned start and stop nodes and, at the same time, delete all the existing nodes in between. To do this you only need to rebuild the tree nodes at or directly above those two places in the tree. If the height of the tree is O(log n), which you can guarantee by using a balanced tree, this takes O(log n) time.

(Disclaimer: If you're in C++ and doing explicit memory management, you might end up freeing more than O(log n) pieces of memory as you do this, but really the time it takes to free a node should be billed to whoever added it, I think.)

Removing an interval is largely the same.

Checking a point or interval is straightforward.

Finding the first gap of at least a given size after a given time can be done in O(log n) too, if you also cache two more pieces of information per node:

• In each start node (other than the leftmost), the size of the gap immediately to the left.

• In every node, the size of the largest gap that appears in that subtree.

To find the first gap of a given size that appears after a given time, first find that time in the tree. Then walk up until you reach a node that claims to contain a large enough gap. If you came up from the right, you know this gap is to the left, so you ignore it and keep walking up. Otherwise you came from the left. If the node is a start node, check to see if the gap to its left is large enough. If so, you're done. Otherwise, the large-enough gap must be somewhere to the right. Walk down to the right and continue down until you find the gap. Again, because the height of the tree is O(log n), walking it three times (down, up, and possibly down again) is O(log n).

How to search in a Range Tree?

The algorithm you are proposing is not quite right - you should compare the range you are querying with the range of the node you are looking at, not the value of the node.

E.g., initially you should compare (-inf, 1) with (-5, 6), which is the data range of the tree (you can also use (-inf, inf) as the data range of the tree or any interval that encloses (-5, 6), for that matter), instead of the value 0. Recursively you should compare the query range with the range of the subtree rooted at the node you are querying at.

Also, the range update can be done while searching - when splitting at a node, the upper/lower bound of the left/right recursive call interval is the node value.

Data structure for quick time interval look up

What you are looking for is an Interval Tree (which is a type of Range Tree).

These have logarithmic lookup time like other tree structures (e.g., RB trees), so you should see comparable performance to using something like a Java TreeMap or an STL map.

• Code for Red-black trees and interval trees from MIT
• There is a C++ implementation in the CGAL Library.
• Here's a C# Implementation

---

Related Topics