Interval Tree

Interval Tree: The concept is to increase a Binary Search Tree self-balancing such as Red Black Tree, and AVL Tree, so that every feature can be completed in time O(Logn).

Each Interval Tree node stores information following.

  • I: An interval representing a pair [low, high]
  • max: Maximum high value in a node-rooted subtree.

The low interval value is used as the key to preserve order within BST.

Insert and delete actions that are used in BST self-balancing are just like insert and delete operations.  

Interval Tree

The key operation is to search for an interval that overlaps. Following is the new algorithm for an overlapping interval x in a root-rooted Interval tree.

1) If x overlaps with an interval of the root, return interval of the root.

2) If left root child is not empty and the limit in the left child is empty is higher than the low value of x, recur for the child left

3) Similar recurrence for the right child.

Why does the Algorithm above work?

Let the query interval be x. We need to prove this for two cases to follow.

Case 1: One of the following must be valid when we go to the correct subtree.

A) The right subtree overlaps: This is fine, as we need to return one overlapping interval.

B) In either subtree, there is no overlap: we go to the right subtree only if either the left subtree is NULL or the left maximum value is lower than x.low. So, the interval in the left subtree cannot be present.

Case 2: One of the following must be true when we go to the left subtree.

A) The left subtree overlaps: This is fine, as we need to return one overlapping interval.

B) In either subtree, there is no overlap: this is the most important part. We need to consider the facts that follow.

  • We went to the left subtree, because in the left subtree x.low <= max
  • Max in the left subtree is one of the intervals in the left subtree, let’s say [a, max].
  • Since x does not overlap with any node in the left x.low subtree, it must be lower than ‘a.’
  • All nodes in BST are ordered by low value, so the low value of all nodes in the right subtree must be higher than ‘a.’
  • We can say from the above two facts that all intervals in the right subtree are of a low value greater than x.low. So x in the right subtree cannot overlap with any interval.

C++ establishment of Interval Tree follows. Basic BST insert operation is used to keep it simple in implementation. Ideally, this should be AVL Tree insertion or Red-Black Tree insertion.


Interval Tree

Pin It on Pinterest

Share This