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
14.3-2
Rewrite the code for $\text{INTERVAL-SEARCH}$ so that it works properly when all intervals are open.
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.
Consider the usual interval search given, but, instead of breaking out of the loop as soon as we have an overlap, we just keep track of the overlap that has the minimum low endpoint, and continue the loop. After the loop terminates, we return the overlap stored.
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.)
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.
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.
Store the elements in a red-black tree, where the key value is the value of each number itself. The auxiliary attribute stored at a node $x$ will be the min gap between elements in the subtree rooted at $x$, the maximum value contained in subtree rooted at $x$, and the minimum value contained in the subtree rooted at $x$. The min gap at a leaf will be $\infty$. Since we can determine the attributes of a node $x$ using only the information about the key at $x$, and the attributes in $x.left$ and $x.right$, Theorem 14.1 implies that we can maintain the values in all nodes of the tree during insertion and deletion without asymptotically affecting their $O(\lg n)$ performance. For $\text{MIN-GAP}$, just check the min gap at the root, in constant time.
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.)
Let $L$ be the set of left coordinates of rectangles. Let $R$ be the set of right coordinates of rectangles. Sort both of these sets in $O(n\lg n)$ time. Then, we will have a pointer to $L$ and a pointer to $R$. If the pointer to $L$ is smaller, call interval search on $T$ for the up-down interval corresponding to this left hand side. If it contains something that intersects the up-down bounds of this rectangle, there is an intersection, so stop.
Otherwise add this interval to $T$ and increment the pointer to $L$. If $R$ is the smaller one, remove the up-down interval that that right hand side corresponds to and increment the pointer to $R$. Since all the interval tree operations used run in time $O(\lg n)$ and we only call them at most $3n$ times, we have that the runtime is $O(n\lg n)$.