Augmenting Data Structures

http://www.slideshare.net/sandpoonia/lecture14-33728738
Next, a structure to support finding the ith
element of a dynamic set in O(lg n) time
■ What operations do dynamic sets usually support?
■ What structure works well for these?
■ How could we use this structure for order statistics?
■ How might we augment it to support efficient extraction of order statistics?

Order Statistic Trees
●OS Trees augment red-black trees:
■Associate a sizefield with each node in the tree
■x->sizerecords the size of subtree rooted at x, including xitself

How can we use this property to select the ith element of the set?
OS-Select(x, i)
{
  r = size[left[x]] + 1;
  if (i == r)
  return x;
  else if (i < r)
  return OS-Select(left[x], i);
  else
  return OS-Select(right[x], i-r);
}
●What happens at the leaves?
●How can we deal elegantly with this?

Note: use a sentinel NIL element at the leaves with size = 0 to simplify code, avoid testing for NULL

Determining The Rank Of An Element
OS-Rank(T, x)
{
  r = size[left[x]] + 1;
  y = x;
  while (y != root[T])
  if (y == right[p[y]])
  r = r + size[left[p[y]]] + 1;
  y = p[y];
  return r;
}

OS-Trees: Maintaining Sizes
●Next step: maintain sizes during Insert() and Delete() operations
■How would we adjust the size fields during insertion on a plain binary search tree?

■A: increment sizes of nodes traversed during search
■Why won’t this work on red-black trees?

Maintaining Size Through Rotation
●Salient point: rotation invalidates only xand y
●Can recalculate their sizes in constant time
■Why?

Augmenting Data Structures: Methodology
●Choose underlying data structure
■E.g., red-black trees
●Determine additional information to maintain
■E.g., subtree sizes
●Verify that information can be maintained for operations that modify the structure
■E.g., Insert(), Delete() (don’t forget rotations!)
●Develop new operations
■E.g., OS-Rank(), OS-Select()

Interval Trees
●The problem: maintain a set of intervals
■E.g., time intervals for a scheduling program

■Query: find an interval in the set that overlaps a given query interval
○[14,16] [15,18]
○[16,19] [15,18] or [17,19]
○[12,14] NULL

○Red-black trees will store intervals, keyed on ilow
○We will store max, the maximum endpoint in the subtree rooted at i