Skip to content

14.3 Interval trees

14.3-1

Write pseudocode for $\text{LEFT-ROTATE}$ that operates on nodes in an interval tree and updates the $max$ attributes in $O(1)$ time.

Add 2 lines in $\text{LEFT-ROTATE}$ in 13.2

1
2
    y.max = x.max
    x.max = max(x.high, x.left.max, x.right.max)

14.3-2

Rewrite the code for $\text{INTERVAL-SEARCH}$ so that it works properly when all intervals are open.

1
2
3
4
5
6
7
INTERVAL-SEARCH(T, i)
    x = T.root
    while x != T.nil and i does not overlap x.int
        if x.left != T.nil and x.left.max > i.low
            x = x.left
        else x = x.right
    return x

14.3-3

Describe an efficient algorithm that, given an interval $i$ , returns an interval overlapping $i$ that has the minimum low endpoint, or $T.nil$ if no such interval exists.

As it travels down the tree, $\text{INTERVAL-SEARCH}$ first checks whether current node $x$ overlaps the query interval $i$ and, if it does not, goes down to either the left or right child. If node $x$ overlaps $i$, and some node in the right subtree overlaps $i$, but no node in the left subtree overlaps $i$, then because the keys are low endpoints, this order of checking (first $x$, then one child) will return the overlapping interval with the minimum low endpoint. On the other hand, if there is an interval that overlaps $i$ in the left subtree of $x$, then checking $x$ before the left subtree might cause the procedure to return an interval whose low endpoint is not the minimum of those that overlap $i$. Therefore, if there is a possibility that the left subtree might contain an interval that overlaps $i$, we need to check the left subtree first. If there is no overlap in the left subtree but node $x$ overlaps $i$, then we return $x$. We check the right subtree under the same conditions as in $\text{INTERVAL-SEARCH}$: the left subtree cannot contain an interval that overlaps $i$, and node $x$ does not overlap $i$, either.

Because we might search the left subtree first, it is easier to write the pseudocode to use a recursive procedure $\text{MIN-INTERVAL-SEARCH-FROM}(T, x, i)$, which returns the node overlapping $i$ with the minimum low endpoint in the subtree rooted at $x$, or $T.nil$ if there is no such node.

1
2
MIN-INTERVAL-SEARCH(T, i)
    return MIN-INTERVAL-SEARCH-FROM(T, T.root, i)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
MIN-INTERVAL-SEARCH-FROM(T, x, i)
    if x.left != T.nil and x.left.max  i.low
        y = MIN-INTERVAL-SEARCH-FROM(T, x.left, i)
        if y != T.nil
            return y
        else if i overlaps x.int
            return x
        else return T.nil
    else if i overlaps x.int
        return x
    else return MIN-INTERVAL-SEARCH-FROM(T, x.right, i)

The call $\text{MIN-INTERVAL-SEARCH}(T, i)$ takes $O(\lg n)$ time, since each recursive call of $\text{MIN-INTERVAL-SEARCH-FROM}$ goes one node lower in the tree, and the height of the tree is $O(\lg n)$.

14.3-4

Given an interval tree $T$ and an interval $i$, describe how to list all intervals in $T$ that overlap $i$ in $O(\min(n, k \lg n))$ time, where $k$ is the number of intervals in the output list. ($\textit{Hint:}$ One simple method makes several queries, modifying the tree between queries. A slightly more complicated method does not modify the tree.)

1
2
3
4
5
6
7
8
9
INTERVALS-SEARCH(T, x, i)
    let list be an empty array
    if i overlaps x.int
        list.APPEND(x)
    if x.left != T.nil and x.left.max > i.low
        list = list.APPEND(INTERVALS-SEARCH(T, x.left, i))
    if x.right != T.nil and x.int.low  i.high and x.right.max  i.low
        list = list.APPEND(INTERVALS-SEARCH(T, x.right, i))
    return list

14.3-5

Suggest modifications to the interval-tree procedures to support the new operation $\text{INTERVAL-SEARCH-EXACTLY}(T, i)$, where $T$ is an interval tree and $i$ is an interval. The operation should return a pointer to a node $x$ in $T$ such that $x.int.low = i.low$ and $x.int.high = i.high$, or $T.nil$ if $T$ contains no such node. All operations, including $\text{INTERVAL-SEARCH-EXACTLY}$, should run in $O(\lg n)$ time on an $n$-node interval tree.

Search for nodes which has exactly the same low value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
INTERVAL-SEARCH-EXACTLY(T, i)
    x = T.root
    while x != T.nil and i not exactly overlap x
        if i.high > x.max
            x = T.nil
        else if i.low < x.low
            x = x.left
        else if i.low > x.low
            x = x.right
        else x = T.nil
    return x

14.3-6

Show how to maintain a dynamic set $Q$ of numbers that supports the operation $\text{MIN-GAP}$, which gives the magnitude of the difference of the two closest numbers in $Q$. For example, if $Q = \{1, 5, 9, 15, 18, 22 \}$, then $\text{MIN-GAP}(Q)$ returns $18 - 15 = 3$, since $15$ and $18$ are the two closest numbers in $Q$. Make the operations $\text{INSERT}$, $\text{DELETE}$, $\text{SEARCH}$, and $\text{MIN-GAP}$ as efficient as possible, and analyze their running times.

  1. Underlying data structure:

    A red-black tree in which the numbers in the set are stored simply as the keys of the nodes.

    $\text{SEARCH}$ is then just the ordinary $\text{TREE-SEARCH}$ for binary search trees, which runs in $O(\lg n)$ time on red-black trees.

  2. Additional information:

    The red-black tree is augmented by the following attributes in each node $x$:

    • $x.min\text-gap$ contains the minimum gap in the subtree rooted at $x$. It has the magnitude of the difference of the two closest numbers in the subtree rooted at $x$. If $x$ is a leaf (its children are all $T.nil$), let $x.min\text-gap = \infty$.
    • $x.min\text-val$ contains the minimum value ($key$) in the subtree rooted at $x$.
    • $x.max\text-val$ contains the maximum value ($key$) in the subtree rooted at $x$.
  3. Maintaining the information:

    The three attributes added to the tree can each be computed from information in the node and its children. Hence by Theorem 14.1, they can be maintained during insertion and deletion without affecting the $O(\lg n)$ running time:

    $$ x.min\text-val = \begin{cases} x.left.min\text-val & \text{if there is a left subtree}, \\ x.key & \text{otherwise}, \end{cases} $$

    $$ x.max\text-val = \begin{cases} x.right.max\text-val & \text{if there is a right subtree}, \\ x.key & \text{otherwise}, \end{cases} $$

    $$ x.min\text-gap = \min \begin{cases} x.left.min\text-gap & \text{($\infty$ if no left subtree)}, \\ x.right.min\text-gap & \text{($\infty$ if no right subtree)}, \\ x.key - x.left.max\text-val & \text{($\infty$ if no left subtree)}, \\ x.right.min\text-val - x.key & \text{($\infty$ if no right subtree)}. \end{cases} $$

    In fact, the reason for defining the $min\text-val$ and $min\text-val$ attributes is to make it possible to compute $min\text-gap$ from information at the node and its children.

  4. New operation:

    $\text{MIN-GAP}$ simply returns the $min\text-gap$ stored at the tree root. Thus, its running time is $O(1)$.

    Note that in addition (not asked for in the exercise), it is possible to find the two closest numbers in $O(\lg n)$ time. Starting from the root, look for where the minimum gap (the one stored at the root) came from. At each node $x$, simulate the computation of $x.min\text-gap$ to figure out where $x.min\text-gap$ came from. If it came from a subtree's $min\text-gap$ attribute, continue the search in that subtree. If it came from a computation with $x$'s key, then $x$ and that other number are the closest numbers.

14.3-7 $\star$

VLSI databases commonly represent an integrated circuit as a list of rectangles. Assume that each rectangle is rectilinearly oriented (sides parallel to the $x$- and $y$-axes), so that we represent a rectangle by its minimum and maximum $x$ and $y$-coordinates. Give an $O(n\lg n)$-time algorithm to decide whether or not a set of $n$ rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect. ($\textit{Hint:}$ Move a "sweep" line across the set of rectangles.)

General idea: Move a sweep line from left to right, while maintaining the set of rectangles currently intersected by the line in an interval tree. The interval tree will organize all rectangles whose $x$ interval includes the current position of the sweep line, and it will be based on the $y$ intervals of the rectangles, so that any overlapping $y$ intervals in the interval tree correspond to overlapping rectangles. Details:

  1. Sort the rectangles by their $x$-coordinates. (Actually, each rectangle must appear twice in the sorted list—once for its left $x$-coordinate and once for its right $x$-coordinate.)
  2. Scan the sorted list (from lowest to highest $x$-coordinate).
    • When an $x$-coordinate of a left edge is found, check whether the rectangle's $y$-coordinate interval overlaps an interval in the tree, and insert the rectangle (keyed on its $y$-coordinate interval) into the tree.
    • When an $x$-coordinate of a right edge is found, delete the rectangle from the interval tree.

The interval tree always contains the set of "open" rectangles intersected by the sweep line. If an overlap is ever found in the interval tree, there are overlapping rectangles.

Time: $O(n\lg n)$.

  • $O(n\lg n)$ to sort the rectangles (we can use merge sort or heap sort).
  • $O(n\lg n)$ for interval-tree operations (insert, delete, and check for overlap).