Interval Tree using GNU Tree-based container

Consider a situation where we have a set of intervals and we need the following operations to be implemented efficiently: 

1. Add an interval
2. Remove an interval
3. Given an interval x, find if x overlaps with any of the existing intervals.

An Interval Tree can be implemented as an augmented binary-search tree (preferably self-balancing), and thus enable us to perform the required operations in O(logN) time complexity. 

Each node of the tree will store the following information: 

1. An interval i: represented as a pair [low, high].
2. Metadata max of right-endpoints: The maximum of the right-endpoints of all the intervals stored in the subtree rooted at this node. Storing this metadata is how we are augmenting the tree.

Example Interval Tree used in Interval Tree | Set 1: 

In Interval Tree | Set 1, we saw how to implement an interval tree using a simple BST (which is not self-balancing). In this article, we will use the built-in GNU tree-based container to implement an Interval Tree. The benefits of doing so are: 

• We do not have to code our own tree data structure.
• We get the default operations like insert and delete out-of-the-box.
• We get to use the in-built Red-Black tree implementation, which means our tree will be self-balancing.

We will be using GNU policy-based implementation of tree data structure. 

The article Policy-based data structures in g++ introduce GNU policy-based data structure along with the required header files. 

We will define our own Node_update policy such that we can maintain the maximum of right-endpoints of intervals in the subtree as metadata in the nodes of our tree. 

The syntax for defining a custom Node_policy is: 

• type_of_our_metadata: int in our case since we want to store the metadata “max of right-endpoints of intervals in the subtree”.
• void operator()(node_iterator it, const_node_iterator end_it): method which is called internally to restore node-invariance, i.e. maintaining correct metadata, after invariance has been invalidated. 
• it: node_iterator to the node whose invariance we need to restore.
• end_it: const_node_iterator to a just-after-leaf node.

See GNU tree-based containers for more details.

We will also define a method overlapSearch which searches for any interval in the tree overlapping with a given interval i.

// pseudocode for overlapSearch

Interval overlapSearch(Interval i) {
    // start from root
    it = root_node

    while (it not null) {
        if (doOVerlap(i, it->interval)) {
              // overlap found
               return it->interval
        }

        if (left_child exists
                     AND
             left_child->max_right_endpoint
                   >= it->left_endpoint) {
            // go to left child
            it = it->left_child
        }

        else {
            // go to right child
            it = it->right_child
        }
    }

    // no overlapping interval found
    return NO_INTERVAL_FOUND
}

Below is the implementation of the Interval Tree:

Searching for interval [25, 29]
Overlaps with [10, 30]

Deleting interval [10, 30]

Searching for interval [25, 29]
No Overlapping Interval

Time Complexity 

All operations are logarithmic in size, i.e. O(logN), where N is the number of intervals stored in the tree. 

Auxiliary Space: O(N)

We are able to achieve logarithmic worst-case complexity because a red-black tree is used internally which is self-balancing.