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 ilow
○We will store max, the maximum endpoint in the subtree rooted at i
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 ilow
○We will store max, the maximum endpoint in the subtree rooted at i
