Introduction to Algorithms/Augmenting Data Structures

Video Link

Dynamic order statistics

• OS-Select(i)- returns $i$th smallest item in dynamic set.
• OS-rank(x)- returns rank of $x$ in sorted order.

Idea: keep subtree sizes in nodes of r-b tree.

size[x]=size[left[x]]+size[right[x]]+1.

Trick: use sentinel (dummy record) for nil,size[nil]=0

OS-Select(x, i) //ith smallest in subtree rooted at x
  k = size[left[x]] + 1
  if i == k
    return x
  else if i < k
    return OS-Select(left[x], i)
  else
    return OS-Select(right[x], i - k)

Analysis: $O(\lg n)$.

Q. Why bit keep ranks in nodes insteadof subtree sizes? Hard to maintain when r-b tree is modified.

Modifying ops: insert, delete. Strategy: update subtree sizes when inserting or deleting.(but also handle rebalancing).$O(\lg n)$

• r-b recoloring: no effect
• rotations: look at children and fix up in $O(1)$ time.

Data structure augmentation

Methodology. (Ex. OS trees)

1. Choose an underlying data structure (r-b tree).
2. Determine additional info (subtree sizes in example).
3. Verifyi info can be maintained for the modifying ops (insert, delete, rotations).
4. Develop new operations that use info(OS-Select,OS-Rank).

Interval trees

Maintain a set of intervals, e.g. time intervals.

Methodology:

1. red-black tree keyed on low endpoint.
2. Store the largest value $m$ in the subtree rooted at that node. m[x]=max(m[left[x],m[right[x]],high[int[x]]
3. Modifying ops:
   • Insert: Fix m’s on way down. But also need to handle rotations(fix m’s takes $O(1) time$). Total time is $O(\lg n)$.
   • Delete similar
4. New ops:
   • Interval-Search(i): Find an inteval that overlaps $i$.

Interval-Search(i)
  x = root
  while x != nil and low[i] > high[int[x]] or low[int[x]] > high[i]
    // don't overlap
    if left[x] != nil and low[i] <= m[left[x]]
      x = left[x]
    else
      x = right[x]
  return x

List all overlaps? output sensitive. Best is $O(k+\lg n)$.

Correctness:

Theorem: Let $L=\{i \in left[x]\},R=\{i \in right[x]\}$.

• If search goes right, then $\{i’ \in L: i’ \ \text{overlaps}\ i\}=\varnothing$ .
• If search goes left,then $\{i \in L: i’ \ \text{overlaps} \ i\}=\varnothing \implies \{i’ \in R:i’ \ \text{overlaps} \ i\}=\varnothing$.

Proof: Suppose search goes right:

• $left[x]=nil$, done since $L=\varnothing$.
• Otherwise, $low[i]>m[left[x]]=high[j],\exists j \in L$. And $\forall i’ \in L,hight[i’]\leqslant high[j]<low[i]$. $\implies \{i’ \in L: i’ \ \text{overlaps}\ i\}=\varnothing$

Suppose search goes left and $\{i \in L: i’ \ \text{overlaps} \ i\}=\varnothing$. $\implies low[i]\leqslant m[left[x]]$, thus $\forall j\in L,high[i]<low[j]$. BST property implies $\forall i’ \in R, low[i’]>low[j]$. So $low[i’]>high[i]$.$\square$