C Program to Implement Interval Tree

«
»
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.

  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. // Structure to represent an interval
  5. struct Interval {
  6.     int low, high;
  7. };
  8.  
  9. // Structure to represent a node in Interval Search Tree
  10. struct ITNode {
  11.     Interval *i; // 'i' could also be a normal variable
  12.     int max;
  13.     ITNode *left, *right;
  14. };
  15.  
  16. // A utility function to create a new Interval Search Tree Node
  17. ITNode * newNode(Interval i) {
  18.     ITNode *temp = new ITNode;
  19.     temp->i = new Interval(i);
  20.     temp->max = i.high;
  21.     temp->left = temp->right = NULL;
  22. }
  23. ;
  24.  
  25. // A utility function to insert a new Interval Search Tree Node
  26. // This is similar to BST Insert.  Here the low value of interval
  27. // is used tomaintain BST property
  28. ITNode *insert(ITNode *root, Interval i) {
  29.     // Base case: Tree is empty, new node becomes root
  30.     if (root == NULL)
  31.         return newNode(i);
  32.  
  33.     // Get low value of interval at root
  34.     int l = root->i->low;
  35.  
  36.     // If root's low value is smaller, then new interval goes to
  37.     // left subtree
  38.     if (i.low < l)
  39.         root->left = insert(root->left, i);
  40.  
  41.     // Else, new node goes to right subtree.
  42.     else
  43.         root->right = insert(root->right, i);
  44.  
  45.     // Update the max value of this ancestor if needed
  46.     if (root->max < i.high)
  47.         root->max = i.high;
  48.  
  49.     return root;
  50. }
  51.  
  52. // A utility function to check if given two intervals overlap
  53. bool doOVerlap(Interval i1, Interval i2) {
  54.     if (i1.low <= i2.high && i2.low <= i1.high)
  55.         return true;
  56.     return false;
  57. }
  58.  
  59. // The main function that searches a given interval i in a given
  60. // Interval Tree.
  61. Interval *intervalSearch(ITNode *root, Interval i) {
  62.     // Base Case, tree is empty
  63.     if (root == NULL)
  64.         return NULL;
  65.  
  66.     // If given interval overlaps with root
  67.     if (doOVerlap(*(root->i), i))
  68.         return root->i;
  69.  
  70.     // If left child of root is present and max of left child is
  71.     // greater than or equal to given interval, then i may
  72.     // overlap with an interval is left subtree
  73.     if (root->left != NULL && root->left->max >= i.low)
  74.         return intervalSearch(root->left, i);
  75.  
  76.     // Else interval can only overlap with right subtree
  77.     return intervalSearch(root->right, i);
  78. }
  79.  
  80. void inorder(ITNode *root) {
  81.     if (root == NULL)
  82.         return;
  83.  
  84.     inorder(root->left);
  85.  
  86.     cout << "[" << root->i->low << ", " << root->i->high << "]" << " max = "
  87.             << root->max << endl;
  88.  
  89.     inorder(root->right);
  90. }
  91.  
  92. // Driver program to test above functions
  93. int main() {
  94.     // Let us create interval tree shown in above figure
  95.     Interval ints[] = { { 15, 20 }, { 10, 30 }, { 17, 19 }, { 5, 20 },
  96.             { 12, 15 }, { 30, 40 } };
  97.     int n = sizeof(ints) / sizeof(ints[0]);
  98.     ITNode *root = NULL;
  99.     for (int i = 0; i < n; i++)
  100.         root = insert(root, ints[i]);
  101.  
  102.     printf("Inorder traversal of constructed Interval Tree is\n");
  103.     inorder(root);
  104.  
  105.     Interval x = { 6, 7 };
  106.  
  107.     printf("\nSearching for interval [%d, %d]", x.low, x.high);
  108.     Interval *res = intervalSearch(root, x);
  109.     if (res == NULL)
  110.         printf("\nNo Overlapping Interval");
  111.     else
  112.         printf("\nOverlaps with [%d, %d]", res->low, res->high);
  113. }

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.