Data Structures19 sections · 729 units
Open in Course

Interval Tree Structure

Divide and conquer idea

An interval tree is a binary tree where each node stores:

1.1. A center point xmidx_{\text{mid}}

2.2. All intervals that contain xmidx_{\text{mid}}

3.3. Left subtree: intervals entirely to the left of xmidx_{\text{mid}}

4.4. Right subtree: intervals entirely to the right of xmidx_{\text{mid}}

class IntervalTreeNode:
    mid: int
    center: list of intervals containing mid
    left: IntervalTreeNode
    right: IntervalTreeNode

The center list is sorted in two ways:

  • By low endpoint (for queries from the left)
  • By high endpoint (for queries from the right)

This dual sorting is the key to efficient queries.