.. _interval_tree:

Interval Tree
==========================================

The following is an **ordered** interval tree of non-overlaping intervals. The base data structure is a C++ map(red-black tree).

.. literalinclude:: interval_tree.h
    :lines: 11-42
    :language: c++
    :linenos:

The basic idea is to use `map::upper_bound` to find the insertion point. Because we use `head` as the key, we may need to merge the current node with previous node. We also may need to merge all the overlapping nodes after the current node.

The following is a test case for the interval tree.

.. literalinclude:: interval_tree_test.cpp
    :lines: 5-18
    :language: c++
    :linenos:

In the test case, `1-4, 5-6, 8-9` are firstly inserted into the map `m`. :numref:`interval_tree_1`. Because there is no overlap, no merge operation is required and the insertion is very straightforward.

.. figure:: interval_tree_1.png
  :name: interval_tree_1
  :align: center
  :width: 160

When inserting interval `1-10`, there is overlap. A simple algorithm is to use `map::upper_bound` to find the node which has head greater than 1. The previous node's head could be equal to 1, so we need to check the previous node. If there is overlap, we delete the node and merge the interval with `1-10`. After removing all the overlapped nodes, we insert the merged interval, which is `1-10` in this case. After insertion of `1-10`, the tree shrinks to one node.

.. figure:: interval_tree_2.png
  :name: interval_tree_2
  :align: center


|:feet:| Refer to :numref:`lower_upper_bound` for the usage of **map::upper_bound**.

|:alien:| How about using `lower_bound` to solve this problem?
|:alien:| How to find if a value is in the interval tree?

.. only:: html

  - https://leetcode.com/problems/range-module/