Interval Tree

An interval tree is a data structure to efficiently store and query intervals. It augments a binary search tree by tracking the maximum interval endpoint in each subtree.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Interval {
  int low, high;
}

class Node {
  Interval interval;
  int max;
  Node left, right;
}

Node insert(Node root, Interval i) {
  if (root == null) {
    root = new Node(i);
  } else if (i.low < root.interval.low) {
    root.left = insert(root.left, i);
  } else {
    root.right = insert(root.right, i);
  }
  
  // Update max
  root.max = Math.max(root.max, i.high);  

  return root;
}

boolean overlaps(Node root, Interval i) {
  // Check interval overlap logic  
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Interval {
  int low, high;   
};

struct Node {
  Interval* interval;
  int max;
  Node *left, *right;
};  

// Insert interval
void insert(Node* root, Interval* i) {
  // Recursive insert 
 
  // Update max
  root->max = max(root->max, i->high);
}

// Check interval overlap
bool overlaps(Node* root, Interval* i) {
  // Logic to check for overlap 
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Interval:
  def __init__(self, low, high):
    self.low = low
    self.high = high
    
class Node:
  def __init__(self, interval, left=None, right=None):
    self.interval = interval
    self.max = interval.high
    self.left = left
    self.right = right
    
# Insert interval  
def insert(root, interval):
  # Recursive insert
  
  # Update max 
  root.max = max(root.max, interval.high)
  
  return root
  
# Check overlap 
def overlaps(root, interval):
  # Logic to check overlap
  

Interval trees efficiently store intervals for stabbing and intersection queries. Useful for scheduling, temporal datasets.

Interval tree is a data structure that can be used to represent intervals and their relationships. It is a tree data structure where each node represents an interval. The intervals in the tree are stored in a sorted order. Interval tree can be used to solve a variety of problems related to intervals, such as finding the intersection of two intervals, finding the union of two intervals, and finding the number of intervals that overlap a given interval.

The interval tree problem on LeetCode is to design and implement an interval tree data structure. The problem statement is as follows:

Design and implement an interval tree data structure. The data structure should support the following operations:

Interval* createInterval(int start, int end): Creates an interval with the given start and end times.
void insertInterval(Interval* interval): Inserts the given interval into the data structure.
Interval* query(int start, int end): Returns the interval that overlaps the given time range, or NULL if no such interval exists.

Concept of Interval Tree

An Interval Tree is a balanced binary search tree specifically designed for storing intervals. It allows efficient querying of all intervals that overlap with a given interval or point. This data structure is particularly useful in computational geometry, databases, and scheduling problems. The key feature is its ability to return all overlapping intervals in O(log N + k) time, where N is the number of intervals and k is the number of overlapping intervals.

Java Code

Here is a simplified Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Interval {
    int low, high;
}

class Node {
    Interval i;
    int max;
    Node left, right;
}

public class IntervalTree {
    Node root;

    Node insert(Node root, Interval i) {
        if (root == null) return new Node(i);

        int l = root.i.low;

        if (i.low < l) {
            root.left = insert(root.left, i);
        } else {
            root.right = insert(root.right, i);
        }

        if (root.max < i.high) {
            root.max = i.high;
        }

        return root;
    }
}

C++ Code

Here’s how you could implement an interval tree in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct Interval {
    int low, high;
};

struct Node {
    Interval i;
    int max;
    Node *left, *right;
};

Node* insert(Node* root, Interval i) {
    if (!root) return new Node{i, i.high, nullptr, nullptr};

    int l = root->i.low;

    if (i.low < l) {
        root->left = insert(root->left, i);
    } else {
        root->right = insert(root->right, i);
    }

    if (root->max < i.high) {
        root->max = i.high;
    }

    return root;
}

Python Code

Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Interval:
    def __init__(self, low, high):
        self.low = low
        self.high = high

class Node:
    def __init__(self, i):
        self.i = i
        self.max = i.high
        self.left = None
        self.right = None

class IntervalTree:
    def __init__(self):
        self.root = None

    def insert(self, root, i):
        if root is None:
            return Node(i)

        l = root.i.low

        if i.low < l:
            root.left = self.insert(root.left, i)
        else:
            root.right = self.insert(root.right, i)

        if root.max < i.high:
            root.max = i.high

        return root

The insert function ensures that the tree remains balanced and updates the max values for each node based on the interval’s high value. This enables the quick querying of overlapping intervals.