Motivation

Given a set of intervals $I$ on the real line and a query point $q_x$, find the intervals that contain $q_x$.

Let $I:={[x_1:x_1’],[x_2:x_2’],\ldots,[x_n:x_n’]}$. Let $x_{\rm mid}$ be the median of the $2n$ interval endpoints such that atmost half of them lie on the left and half of them lie on the right.

Definition

• If $I=\phi$ then interval tree is a leaf.
• Otherwise let $x_{\rm mid}$ be the median of the endpoints of the interval. Let
  • $I_{\rm left}:={[x_j:x_j’]\in I\mid x_j’<x_{\rm mid}}$
  • $I_{\rm mid}:={[x_j:x_j’]\in I\mid x_j\le x_{\rm mid}\le x_j’}$.
  • $I_{\rm right}:={[x_j:x_j’]\in I\mid x_j>x_{\rm mid}}$

The Interval tree consists of a root node $v$ storing $x_{\rm mid}$.

• $I_{\rm mid}$ is stored twice:

  1. ${\cal L}_{\rm left}$ that is sorted on the left endpoints of $I_{\rm mid}$

  2. ${\cal L}_{\rm right}$ that is sorted on the right endpoints of $I_{\rm mid}$

• Left subtree of $v$ is an interval tree for the set $I_{\rm left}$.

• Right subtree of $v$ is an interval tree for the set $I_{\rm right}$.

Creation $O(n\log n)$

create(I)
  if I = null
    return empty leaf
  else
    create a node v
    computer x_mid (linear time, constant if presorted)
    store x_mid with v
    compute I_mid, L_left, L_right
    left_child(v) <- create(I_left)
    right_child(v) <- create(I_right)
    return v

Querying $O(\log n+k)$

• If $q_x < x_{\rm mid}(v)$ walk along $\cal L_{\rm left}$ reporting all intervals that contain $q_x$. Stop as soon as an interval doesn’t contain $q_x$. Query left subtree of $v$.
• Symmetrically do for $q_x>x_{\rm mid(v)}$

$k$ = Number of reported intervals.

2-D Range Tree

The data structure to store a a horizontal line segments is $\rm T$. If we want to create a 2-D range tree then instead of $\cal L_{\rm left}(v)$ and $\cal L_{\rm right}(v)$ we will store:

• A range tree $T_{\rm left}(v)$ on left endpoint segments in $I_{\rm mid}(v)$.
• A range tree $T_{\rm right}(v)$ on right endpoint segments in $I_{\rm mid}(v)$

At time of querying instead of walking along $\cal L_{\rm left}(v)$ and $\cal L_{\rm right}(v)$ we will perform a query in the range trees $\rm T_{left}(v)$ and $\rm T_{right}(v)$.

• Creation: $O(n\log n)$
• Querying: $O(\log^2n+k)$