EEM 611
Design and Analysis of Algorithms
Dynamic Order Statistics
Order Statistic Trees
● OS Trees augment red-black trees:
■ Associate a size field with each node in the tree
■ x->size records the size of subtree rooted at x,
including x itself:
M
8
C P
5 2
A F Q
1 3 1
D H
1 1
Selection On OS Trees
M
8
C P
5 2
A F Q
1 3 1
D H
1 1
How can we use this property
to select the ith element of the set?
OS-Select
OS-Select(x, i)
{
r = x->left->size + 1;
if (i == r)
return x;
else if (i < r)
return OS-Select(x->left, i);
else
return OS-Select(x->right, i-r);
}
OS-Select Example
● Example: show OS-Select(root, 5):
OS-Select(x, i)
M
{
8
r = x->left->size + 1;
if (i == r) C P
5 2
return x;
else if (i < r) A F Q
return OS-Select(x->left, i); 1 3 1
else D H
return OS-Select(x->right, i-r); 1 1
}
OS-Select Example
● Example: show OS-Select(root, 5):
OS-Select(x, i)
M i=5
{
8 r=6
r = x->left->size + 1;
if (i == r) C P
5 2
return x;
else if (i < r) A F Q
return OS-Select(x->left, i); 1 3 1
else D H
return OS-Select(x->right, i-r); 1 1
}
OS-Select Example
● Example: show OS-Select(root, 5):
OS-Select(x, i)
M i=5
{
8 r=6
r = x->left->size + 1;
if (i == r) C i=5 P
5 r=2 2
return x;
else if (i < r) A F Q
return OS-Select(x->left, i); 1 3 1
else D H
return OS-Select(x->right, i-r); 1 1
}
OS-Select Example
● Example: show OS-Select(root, 5):
OS-Select(x, i)
M i=5
{
8 r=6
r = x->left->size + 1;
if (i == r) C i=5 P
5 r=2 2
return x;
else if (i < r) A F i=3 Q
return OS-Select(x->left, i); 1 3 r=2 1
else D H
return OS-Select(x->right, i-r); 1 1
}
OS-Select Example
● Example: show OS-Select(root, 5):
OS-Select(x, i)
M i=5
{
8 r=6
r = x->left->size + 1;
if (i == r) C i=5 P
5 r=2 2
return x;
else if (i < r) A F i=3 Q
return OS-Select(x->left, i); 1 3 r=2 1
else D H i=1
return OS-Select(x->right, i-r); 1 1 r=1
}
OS-Select: A Subtlety
OS-Select(x, i)
{ Oops…
r = x->left->size + 1;
if (i == r)
return x;
else if (i < r)
return OS-Select(x->left, i);
else
return OS-Select(x->right, i-r);
}
● What happens at the leaves?
● How can we deal elegantly with this?
OS-Select
OS-Select(x, i)
{
r = x->left->size + 1;
if (i == r)
return x;
else if (i < r)
return OS-Select(x->left, i);
else
return OS-Select(x->right, i-r);
}
● What will be the running time?
Determining The
Rank Of An Element
M
8
C P
5 2
A F Q
1 3 1
D H
1 1
What is the rank of this element?
Determining The
Rank Of An Element
M
8
C P
5 2
A F Q
1 3 1
D H
1 1
Of this one? Why?
Determining The
Rank Of An Element
M
8
C P
5 2
A F Q
1 3 1
D H
1 1
Of the root? What’s the pattern here?
Determining The
Rank Of An Element
M
8
C P
5 2
A F Q
1 3 1
D H
1 1
What about the rank of this element?
Determining The
Rank Of An Element
M
8
C P
5 2
A F Q
1 3 1
D H
1 1
This one? What’s the pattern here?
OS-Rank
OS-Rank(T, x)
{
r = x->left->size + 1;
y = x;
while (y != T->root)
if (y == y->p->right)
r = r + y->p->left->size + 1;
y = y->p;
return r;
}
● What will be the running time?
OS-Trees: Maintaining Sizes
● So we’ve shown that with subtree sizes, order
statistic operations can be done in O(lg n) time
● Next step: maintain sizes during Insert() and
Delete() operations
■ How would we adjust the size fields during
insertion on a plain binary search tree?
OS-Trees: Maintaining Sizes
● So we’ve shown that with subtree sizes, order
statistic operations can be done in O(lg n) time
● 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
OS-Trees: Maintaining Sizes
● So we’ve shown that with subtree sizes, order
statistic operations can be done in O(lg n) time
● 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
y x
19 rightRotate(y) 19
x y
11 12
7 leftRotate(x) 6
6 4 4 7
● Salient point: rotation invalidates only x and 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()
