Interval Tree in C - Sanfoundry

This is a C Program to implement interval tree. Consider a situation where we have a set of intervals and we need 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.
Interval Tree: The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc to maintain set of intervals so that all operations can be done in O(Logn) time.

Here is source code of the C Program to Implement Interval Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <math.h>
```
```
 
```
```
// Structure to represent an interval
```
```
struct Interval {
```
```
    int low, high;
```
```
};
```
```
 
```

// Structure to represent a node in Interval Search Tree

```
struct ITNode {
```

    Interval *i; // 'i' could also be a normal variable

```
    int max;
```
```
    ITNode *left, *right;
```
```
};
```
```
 
```

// A utility function to create a new Interval Search Tree Node

```
ITNode * newNode(Interval i) {
```
```
    ITNode *temp = new ITNode;
```
```
    temp->i = new Interval(i);
```
```
    temp->max = i.high;
```
```
    temp->left = temp->right = NULL;
```
```
}
```
```
;
```
```
 
```

// A utility function to insert a new Interval Search Tree Node

// This is similar to BST Insert.  Here the low value of interval

```
// is used tomaintain BST property
```

ITNode *insert(ITNode *root, Interval i) {

    // Base case: Tree is empty, new node becomes root

```
    if (root == NULL)
```
```
        return newNode(i);
```
```
 
```

    // Get low value of interval at root

```
    int l = root->i->low;
```
```
 
```

    // If root's low value is smaller, then new interval goes to

```
    // left subtree
```
```
    if (i.low < l)
```

        root->left = insert(root->left, i);

```
 
```

    // Else, new node goes to right subtree.

```
    else
```

        root->right = insert(root->right, i);

```
 
```

    // Update the max value of this ancestor if needed

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

// A utility function to check if given two intervals overlap

bool doOVerlap(Interval i1, Interval i2) {

    if (i1.low <= i2.high && i2.low <= i1.high)

```
        return true;
```
```
    return false;
```
```
}
```
```
 
```

// The main function that searches a given interval i in a given

```
// Interval Tree.
```

Interval *intervalSearch(ITNode *root, Interval i) {

```
    // Base Case, tree is empty
```
```
    if (root == NULL)
```
```
        return NULL;
```
```
 
```

    // If given interval overlaps with root

```
    if (doOVerlap(*(root->i), i))
```
```
        return root->i;
```
```
 
```

    // If left child of root is present and max of left child is

    // greater than or equal to given interval, then i may

    // overlap with an interval is left subtree

    if (root->left != NULL && root->left->max >= i.low)

        return intervalSearch(root->left, i);

```
 
```

    // Else interval can only overlap with right subtree

    return intervalSearch(root->right, i);

```
}
```
```
 
```
```
void inorder(ITNode *root) {
```
```
    if (root == NULL)
```
```
        return;
```
```
 
```
```
    inorder(root->left);
```
```
 
```

    cout << "[" << root->i->low << ", " << root->i->high << "]" << " max = "

```
            << root->max << endl;
```
```
 
```
```
    inorder(root->right);
```
```
}
```
```
 
```

// Driver program to test above functions

```
int main() {
```

    // Let us create interval tree shown in above figure

    Interval ints[] = { { 15, 20 }, { 10, 30 }, { 17, 19 }, { 5, 20 },

```
            { 12, 15 }, { 30, 40 } };
```

    int n = sizeof(ints) / sizeof(ints[0]);

```
    ITNode *root = NULL;
```
```
    for (int i = 0; i < n; i++)
```
```
        root = insert(root, ints[i]);
```
```
 
```

    printf("Inorder traversal of constructed Interval Tree is\n");

```
    inorder(root);
```
```
 
```
```
    Interval x = { 6, 7 };
```
```
 
```

    printf("\nSearching for interval [%d, %d]", x.low, x.high);

    Interval *res = intervalSearch(root, x);

```
    if (res == NULL)
```

        printf("\nNo Overlapping Interval");

```
    else
```

        printf("\nOverlaps with [%d, %d]", res->low, res->high);

```
}
```

Output:

$ gcc IntervalTree.c
$ ./a.out
 
Inorder traversal of constructed Interval Tree is
[5, 20] max = 20
[10, 30] max = 30
[12, 15] max = 15
[15, 20] max = 40
[17, 19] max = 40
[30, 40] max = 40
 
Searching for interval [6,7]
Overlaps with [5, 20]

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Print All Nodes of a Tree

» Next - C Program to Create Expression Tree from Postfix Expression

Related Posts:

Recommended Articles: