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:
- Add an interval
- Remove an interval
- 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:
- An interval i: represented as a pair [low, high].
- 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:
#include <iostream> // Include the iostream header for cout and endl
#include <functional> // For std::function
// Define a custom node update policy struct
template <
typename Const_Node_Iterator, // Constant node iterator type
typename Node_Iterator, // Node iterator type
typename Cmp_Fn_, // Comparator function type
typename Allocator_> // Allocator type
struct custom_node_update_policy {
// Define a nested struct to represent metadata type
struct metadata_type {
// Define members of metadata type here
};
// Define a method similar to the apply() method in Java
void apply(Node_Iterator it,
Const_Node_Iterator endIt)
{
// Implementation of the method
// Note: C++ doesn't have function objects like Java
}
// Other methods can be added here as needed
};
using std::cout; // Import cout into the global namespace
using std::endl; // Import endl into the global namespace
int main() {
// Your program logic goes here
// You can create instances of
// custom_node_update_policy and call its methods
// For example:
custom_node_update_policy<int, int,
std::function<int(int)>,
void*> policy;
policy.apply(10, 20); // Example call to apply method
// Output to demonstrate that the program is running
cout << "Program executed successfully." << endl;
return 0;
}
import java.util.function.Function;
public class Program {
// Define a generic class with type parameters
public static class CustomNodeUpdatePolicy<
ConstNodeIterator, NodeIterator, CmpFn, Allocator> {
// Define a nested class to represent metadata type
public class MetadataType {
// Define members of metadata type here
}
// Define a method similar to the operator() in C++
public void apply(NodeIterator it,
ConstNodeIterator endIt)
{
// Implementation of the method
// Note: Java doesn't have operator overloading
// like C++
}
// Other methods can be added here as needed
}
public static void main(String[] args)
{
// Your program logic goes here
// You can create instances of
// CustomNodeUpdatePolicy and call its methods For
// example:
CustomNodeUpdatePolicy<Integer, Integer,
Function<Integer, Integer>,
Object> policy
= new CustomNodeUpdatePolicy<>();
policy.apply(10,
20); // Example call to apply method
// Output to demonstrate that the program is running
System.out.println(
"Program executed successfully.");
}
}
using System;
public class Program
{
// Define a generic class with type parameters
public class CustomNodeUpdatePolicy<ConstNodeIterator, NodeIterator, CmpFn, Allocator>
{
// Define a nested class to represent metadata type
public class MetadataType
{
// Define members of metadata type here
}
// Define a method similar to the operator() in C++
public void Apply(NodeIterator it, ConstNodeIterator endIt)
{
// Implementation of the method
// Note: C# doesn't have operator overloading like C++
}
// Other methods can be added here as needed
}
public static void Main(string[] args)
{
// Your program logic goes here
// You can create instances of CustomNodeUpdatePolicy and call its methods
// For example:
CustomNodeUpdatePolicy<int, int, Func<int, int, int>, object> policy = new CustomNodeUpdatePolicy<int, int, Func<int, int, int>, object>();
policy.Apply(10, 20); // Example call to Apply method
// Output to demonstrate that the program is running
Console.WriteLine("Program executed successfully.");
}
}
// Define a generic class with type parameters
class CustomNodeUpdatePolicy {
constructor(ConstNodeIterator, NodeIterator, CmpFn, Allocator) {
this.ConstNodeIterator = ConstNodeIterator;
this.NodeIterator = NodeIterator;
this.CmpFn = CmpFn;
this.Allocator = Allocator;
}
// Define a nested class to represent metadata type
MetadataType() {
// Define members of metadata type here
}
// Define a method similar to the operator() in Python
apply(it, endIt) {
// Implementation of the method
// Note: JavaScript doesn't have operator overloading like Python
}
// Other methods can be added here as needed
}
// Your program logic goes here
// You can create instances of CustomNodeUpdatePolicy and call its methods
// For example:
const policy = new CustomNodeUpdatePolicy(Number, Number, (x, y) => x + y, Object);
policy.apply(10, 20); // Example call to Apply method
// Output to demonstrate that the program is running
console.log("Program executed successfully.");
# Define a generic class with type parameters
class CustomNodeUpdatePolicy:
def __init__(self, ConstNodeIterator, NodeIterator, CmpFn, Allocator):
self.ConstNodeIterator = ConstNodeIterator
self.NodeIterator = NodeIterator
self.CmpFn = CmpFn
self.Allocator = Allocator
# Define a nested class to represent metadata type
class MetadataType:
pass
# Define members of metadata type here
# Define a method similar to the operator() in C++
def apply(self, it, endIt):
pass
# Implementation of the method
# Note: Python doesn't have operator overloading like C++
# Other methods can be added here as needed
# Your program logic goes here
# You can create instances of CustomNodeUpdatePolicy and call its methods
# For example:
policy = CustomNodeUpdatePolicy(int, int, lambda x, y: x + y, object)
policy.apply(10, 20) # Example call to Apply method
# Output to demonstrate that the program is running
print("Program executed successfully.")
Output
Program executed successfully.
- 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:
// CPP program for above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> Interval;
// An invalid interval, used as
// return value to denote that no
// matching interval was found
const Interval NO_INTERVAL_FOUND = { 1, 0 };
// interval update policy struct
template <class Node_CItr,
class Node_Itr,
class Cmp_Fn, class _Alloc>
struct interval_node_update_policy {
// Our metadata is maximum of
// right-endpoints of intervals in the
// sub-tree, which is of type int
typedef int metadata_type;
// An utility function to check
// if given two intervals overlap
bool doOverlap(Interval i1,
Node_CItr i2)
{
return (i1.first <= (*i2)->second
&& (*i2)->first <= i1.second);
}
// Search for any interval that
// overlaps with Interval i
Interval overlapSearch(Interval i)
{
for (Node_CItr it = node_begin();
it != node_end();) {
if (doOverlap(i, it)) {
return { (*it)->first,
(*it)->second };
}
if (it.get_l_child() != node_end()
&& it.get_l_child()
.get_metadata()
>= i.first) {
it = it.get_l_child();
}
else {
it = it.get_r_child();
}
}
return NO_INTERVAL_FOUND;
}
// To restore the node-invariance
// of the node pointed to by
// (it). We need to derive the
// metadata for node (it) from
// its left-child and right-child.
void operator()(Node_Itr it,
Node_CItr end_it)
{
int max_high = (*it)->second;
if (it.get_l_child() != end_it) {
max_high = max(
max_high,
it.get_l_child()
.get_metadata());
}
if (it.get_r_child() != end_it) {
max_high = max(
max_high,
it.get_r_child()
.get_metadata());
}
// The max of right-endpoint
// of this node and the max
// right-endpoints of children.
const_cast<int&>(
it.get_metadata())
= max_high;
}
virtual Node_CItr node_begin() const = 0;
virtual Node_CItr node_end() const = 0;
virtual ~interval_node_update_policy() {}
};
// IntervalTree data structure
// rb_tree_tag: uses red-black search tree
// interval_node_update_policy:
// our custom Node_update policy
typedef tree<Interval,
null_type,
less<Interval>,
rb_tree_tag,
interval_node_update_policy>
IntervalTree;
// Driver Code
int main()
{
IntervalTree IT;
Interval intvs[] = { { 15, 20 },
{ 10, 30 },
{ 17, 19 },
{ 5, 20 },
{ 12, 15 },
{ 30, 40 } };
for (Interval intv : intvs) {
IT.insert(intv);
}
Interval toSearch = { 25, 29 };
cout << "\nSearching for interval ["
<< toSearch.first << ", "
<< toSearch.second << "]";
Interval res = IT.overlapSearch(toSearch);
if (res == NO_INTERVAL_FOUND)
cout << "\nNo Overlapping Interval\n";
else
cout << "\nOverlaps with ["
<< res.first << ", "
<< res.second << "]\n";
Interval toErase = { 10, 30 };
IT.erase(toErase);
cout << "\nDeleting interval ["
<< toErase.first << ", "
<< toErase.second
<< "]\n";
cout << "\nSearching for interval ["
<< toSearch.first << ", "
<< toSearch.second << "]";
res = IT.overlapSearch(toSearch);
if (res == NO_INTERVAL_FOUND)
cout << "\nNo Overlapping Interval\n";
else
cout << "\nOverlaps with ["
<< res.first << ", "
<< res.second << "]\n";
return 0;
}
import java.util.Comparator;
import java.util.TreeSet;
// Class to represent intervals
class Interval {
int first, second;
public Interval(int first, int second) {
this.first = first;
this.second = second;
}
}
// Class representing the Interval Tree
class IntervalTree {
TreeSet<Interval> treeSet;
// Constructor for IntervalTree class
public IntervalTree() {
// Use a TreeSet with a custom comparator based on the second endpoint of intervals
treeSet = new TreeSet<>(Comparator.comparingInt(interval -> interval.second));
}
// Method to insert an interval into the tree
public void insert(Interval interval) {
treeSet.add(interval);
}
// Method to search for any interval that overlaps with the given interval
public Interval overlapSearch(Interval interval) {
for (Interval i : treeSet) {
if (doOverlap(interval, i)) {
return new Interval(i.first, i.second);
}
}
return NO_INTERVAL_FOUND;
}
// Method to remove an interval from the tree
public void erase(Interval interval) {
treeSet.remove(interval);
}
// Helper method to check if two intervals overlap
private boolean doOverlap(Interval i1, Interval i2) {
return (i1.first <= i2.second && i2.first <= i1.second);
}
// Declare NO_INTERVAL_FOUND as static or public
public static final Interval NO_INTERVAL_FOUND = new Interval(1, 0);
}
// Main class to test the IntervalTree
public class Main {
public static void main(String[] args) {
IntervalTree IT = new IntervalTree();
Interval[] intvs = {
new Interval(15, 20),
new Interval(10, 30),
new Interval(17, 19),
new Interval(5, 20),
new Interval(12, 15),
new Interval(30, 40)
};
// Insert intervals into the tree
for (Interval intv : intvs) {
IT.insert(intv);
}
// Search for overlapping interval
Interval toSearch = new Interval(25, 29);
System.out.println("Searching for interval [" + toSearch.first + ", " + toSearch.second + "]");
Interval res = IT.overlapSearch(toSearch);
if (res == IntervalTree.NO_INTERVAL_FOUND)
System.out.println("No Overlapping Interval");
else
System.out.println("Overlaps with [" + res.first + ", " + res.second + "]");
// Remove an interval from the tree
Interval toErase = new Interval(10, 30);
IT.erase(toErase);
System.out.println("Deleting interval [" + toErase.first + ", " + toErase.second + "]");
// Search for overlapping interval after deletion
System.out.println("Searching for interval [" + toSearch.first + ", " + toSearch.second + "]");
res = IT.overlapSearch(toSearch);
if (res == IntervalTree.NO_INTERVAL_FOUND)
System.out.println("No Overlapping Interval");
else
System.out.println("Overlaps with [" + res.first + ", " + res.second + "]");
}
}
using System;
using System.Collections.Generic;
// Class representing an interval
class Interval
{
public int Start { get; set; }
public int End { get; set; }
public Interval(int start, int end)
{
Start = start;
End = end;
}
}
// Class representing an Interval Tree
class IntervalTree
{
private readonly SortedSet<Interval> intervals;
public IntervalTree()
{
intervals = new SortedSet<Interval>(Comparer<Interval>.Create((a, b) => a.Start.CompareTo(b.Start)));
}
// Insert an interval into the Interval Tree
public void Insert(Interval interval)
{
intervals.Add(interval);
}
// Search for any interval that overlaps with the given query interval
public Interval OverlapSearch(Interval queryInterval)
{
foreach (var interval in intervals)
{
if (DoOverlap(queryInterval, interval))
{
return interval;
}
}
return null;
}
// Remove an interval from the Interval Tree
public void Erase(Interval interval)
{
intervals.Remove(interval);
}
// Check if two intervals overlap
private bool DoOverlap(Interval i1, Interval i2)
{
return (i1.Start <= i2.End && i2.Start <= i1.End);
}
}
class Program
{
static void Main()
{
IntervalTree intervalTree = new IntervalTree();
Interval[] intervals = {
new Interval(15, 20),
new Interval(10, 30),
new Interval(17, 19),
new Interval(5, 20),
new Interval(12, 15),
new Interval(30, 40)
};
// Insert intervals into the Interval Tree
foreach (var interval in intervals)
{
intervalTree.Insert(interval);
}
Interval toSearch = new Interval(25, 29);
Console.Write($"\nSearching for interval [{toSearch.Start}, {toSearch.End}]: ");
Interval result = intervalTree.OverlapSearch(toSearch);
if (result == null)
Console.WriteLine("No Overlapping Interval");
else
Console.WriteLine($"Overlaps with [{result.Start}, {result.End}]");
Interval toErase = new Interval(10, 30);
intervalTree.Erase(toErase);
Console.Write($"\nDeleting interval [{toErase.Start}, {toErase.End}]: ");
Console.Write($"\nSearching for interval [{toSearch.Start}, {toSearch.End}]: ");
result = intervalTree.OverlapSearch(toSearch);
if (result == null)
Console.WriteLine("No Overlapping Interval");
else
Console.WriteLine($"Overlaps with [{result.Start}, {result.End}]");
}
}
// JavaScript Program for the above approach
// Define a Node class representing a node in the interval tree
class Node {
constructor(interval) {
this.interval = interval;
this.max = interval[1];
this.left = null;
this.right = null;
}
}
// Define an IntervalTree class to manage the interval tree operations
class IntervalTree {
constructor() {
this.root = null;
}
// insert a new interval into the interval tree
insert(root, interval) {
if (!root) {
return new Node(interval);
}
if (interval[0] < root.interval[0]) {
root.left = this.insert(root.left, interval);
} else {
root.right = this.insert(root.right, interval);
}
root.max = Math.max(root.max, interval[1]);
return root;
}
// check for interval operlap in the interval tree
overlap(root, interval) {
if (!root) {
return null;
}
if (root.interval[0] <= interval[1] && root.interval[1] >= interval[0]) {
return root.interval;
}
if (root.left && root.left.max >= interval[0]) {
return this.overlap(root.left, interval);
}
return this.overlap(root.right, interval);
}
// delete an interval from the interval tree
delete(root, interval) {
if (!root) {
return root;
}
if (interval[0] < root.interval[0]) {
root.left = this.delete(root.left, interval);
} else if (interval[0] > root.interval[0]) {
root.right = this.delete(root.right, interval);
} else {
if (!root.left) {
let temp = root.right;
root = null;
return temp;
} else if (!root.right) {
let temp = root.left;
root = null;
return temp;
}
let temp = this.minValueNode(root.right);
root.interval = temp.interval;
root.right = this.delete(root.right, temp.interval);
}
return root;
}
// helper function to find the node with the minimum value in subtree
minValueNode(root) {
let current = root;
while (current.left !== null) {
current = current.left;
}
return current;
}
}
// Example usage of the IntervalTree
const intervals = [[15, 20], [10, 30], [17, 19], [5, 20], [12, 15], [30, 40]];
const IT = new IntervalTree();
for (const interval of intervals) {
IT.root = IT.insert(IT.root, interval);
}
// Search for an interval and print the result
const to_search = [25, 29];
console.log(`Searching for interval ${JSON.stringify(to_search)}`);
let res = IT.overlap(IT.root, to_search);
if (res) {
console.log(`Overlaps with ${JSON.stringify(res)}`);
} else {
console.log("No Overlapping Interval");
}
// Delete an interval and print the result
const to_erase = [10, 30];
console.log(`Deleting interval ${JSON.stringify(to_erase)}`);
IT.root = IT.delete(IT.root, to_erase);
// Search for an interval again after deletion and print the result
console.log(`Searching for interval ${JSON.stringify(to_search)}`);
res = IT.overlap(IT.root, to_search);
if (res) {
console.log(`Overlaps with ${JSON.stringify(resultAfterDeletion)}`);
} else {
console.log("No Overlapping Interval");
}
// This code is contributed by Yash Agarwal(yashagarwal2852002)
# Define a Node class representing a node in the interval tree
class Node:
def __init__(self, interval):
self.interval = interval
self.max = interval[1]
self.left = None
self.right = None
# Define an IntervalTree class to manage the interval tree operations
class IntervalTree:
def __init__(self):
self.root = None
# Insert a new interval into the interval tree
def insert(self, root, interval):
if not root:
return Node(interval)
if interval[0] < root.interval[0]:
root.left = self.insert(root.left, interval)
else:
root.right = self.insert(root.right, interval)
root.max = max(root.max, interval[1])
return root
# Check for interval overlap in the interval tree
def overlap(self, root, interval):
if not root:
return None
if (root.interval[0] <= interval[1] and root.interval[1] >= interval[0]):
return root.interval
if root.left and root.left.max >= interval[0]:
return self.overlap(root.left, interval)
return self.overlap(root.right, interval)
# Delete an interval from the interval tree
def delete(self, root, interval):
if not root:
return root
if interval[0] < root.interval[0]:
root.left = self.delete(root.left, interval)
elif interval[0] > root.interval[0]:
root.right = self.delete(root.right, interval)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.minValueNode(root.right)
root.interval = temp.interval
root.right = self.delete(root.right, temp.interval)
return root
# Helper function to find the node with the minimum value in a subtree
def minValueNode(self, root):
current = root
while(current.left is not None):
current = current.left
return current
# Example usage of the IntervalTree
intervals = [(15, 20), (10, 30), (17, 19), (5, 20), (12, 15), (30, 40)]
IT = IntervalTree()
for interval in intervals:
IT.root = IT.insert(IT.root, interval)
# Search for an interval and print the result
to_search = (25, 29)
print(f"Searching for interval {to_search}")
res = IT.overlap(IT.root, to_search)
if res:
print(f"Overlaps with {res}")
else:
print("No Overlapping Interval")
# Delete an interval and print the result
to_erase = (10, 30)
print(f"Deleting interval {to_erase}")
IT.root = IT.delete(IT.root, to_erase)
# Search for an interval again after deletion and print the result
print(f"Searching for interval {to_search}")
res = IT.overlap(IT.root, to_search)
if res:
print(f"Overlaps with {res}")
else:
print("No Overlapping Interval")
Output
Searching for interval [25, 29] Overlaps with [10, 30] Deleting interval [10, 30] Searching for interval [25, 29] No Overlapping Interval
Time Complexity : O(log N), 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.
Contact Us