Construction of an Interval Tree: A Detailed Explanation

The Interval Tree is a self-balancing binary search tree that helps efficiently store and query intervals.
Let’s break down its construction step by step.

Step 1: Understanding the Structure of an Interval Tree

Each node in the tree represents an interval (low,high)(low, high)(low,high) and contains:

 low: The starting point of the interval.

 high: The ending point of the interval.

 max: The maximum high value of all intervals in its subtree.

 left: Pointer to the left child.

 right: Pointer to the right child.

Example Input:

Consider the following intervals:

(15,20),(10,30),(17,19),(5,20),(12,15),(30,40)(15, 20), (10, 30), (17, 19), (5, 20), (12, 15), (30, 40)
(15,20),(10,30),(17,19),(5,20),(12,15),(30,40)

We will construct an Interval Tree step by step.

Step 2: Insertion Process

The insertion of an interval into the tree follows the BST property, where:

 Intervals are sorted based on their "low" values.

 The max value of each node is updated after insertion.

Insertion Algorithm:

1. Insert the first interval as the root.

2. For each subsequent interval:

o Compare low with the low of the root.

o If low is smaller, insert in the left subtree.

o If low is greater, insert in the right subtree.

o Update the max value of each node while returning back.

3. Continue this process for all intervals.

Step 2.1: Insert (15, 20) as the Root

Since the tree is empty, the first interval becomes the root:
(15, 20) [20]

 max value is 20 (as it is the only interval).

Step 2.2: Insert (10, 30)

 low = 10 (less than 15) → Go left.

 Insert as the left child of (15, 20).

 Update max at (15, 20) → max(20, 30) = 30.

(15, 20) [30]

(10, 30) [30]

Step 2.3: Insert (17, 19)

 low = 17 (greater than 15) → Go right.

 Insert as the right child of (15, 20).

 Update max at (15, 20) → max(30, 19) = 30.

(15, 20) [30]

/ \

(10, 30) [30] (17, 19) [19]

Step 2.4: Insert (5, 20)

 low = 5 (less than 15) → Go left.

 low = 5 (less than 10) → Go left of (10, 30).

 Insert as the left child of (10, 30).

 Update max values up the tree.

(15, 20) [30]

/ \

(10, 30) [30] (17, 19) [19]

(5, 20) [20]

 Updating max:

o max(5,20) = 20 at (5, 20)

o max(30,19) = 30 at (15,20)

Step 2.5: Insert (12, 15)

 low = 12 (less than 15) → Go left.

 low = 12 (greater than 10) → Go right of (10, 30).

 Insert as the right child of (10, 30).

 Update max values.

(15, 20) [30]

/ \

(10, 30) [30] (17, 19) [19]

/ \

(5, 20) [20] (12, 15) [15]

 Updating max:

o max(15,20) = 20 at (10,30) → No change at the root.

Step 2.6: Insert (30, 40)

 low = 30 (greater than 15) → Go right.

 low = 30 (greater than 17) → Go right of (17, 19).

 Insert as the right child of (17, 19).

 Update max values.

(15, 20) [40]

/ \

(10, 30) [30] (17, 19) [40]

/ \ \

(5, 20) [20] (12, 15) [15] (30, 40) [40]

 Updating max:

o max(19,40) = 40 at (17,19).

o max(30,40) = 40 at (15,20).

Step 3: Querying for Overlapping Intervals

Query Example: Find intervals overlapping with (14, 16)

1. Start at the root (15, 20) → Overlaps!

2. Check left child (10, 30) → Overlaps!

3. Check left child (5, 20) → Overlaps!

4. Check right child (12, 15) → No overlap.

5. Check right child (17, 19) → No overlap.

Result:

Intervals (15,20), (10,30), and (5,20) overlap with (14,16).