Lecture 21

CS 332: Algorithms
Augmenting Data Structures:

Interval Trees
Review: Dynamic Order Statistics

Weve seen algorithms for finding the ith element
of an unordered set in O(n) time

OS-Trees: a structure to support finding the ith
element of a dynamic set in O(lg n) time
Support standard dynamic set operations ( Insert(),
Delete(), Min(), Max(), Succ(), Pred() )
Also support these order statistic operations:
void OS-Select(root, i);

int OS-Rank(x);
Review: 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
5
P
2
A
1
F
3
D
1
Q
1
H
1
Review: OS-Select
Example: show OS-Select(root, 5):
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);
}
M
8
C
5
A
1
P
2
F
3
D
1
Q
1
H
1
Review: OS-Select
OS-Select(x, i)
{
if (i == r)
return x;
else if (i < r)
else
}
M
8
i=5
r=6
C
5
A
1
P
2
F
3
D
1
Q
1
H
1
Review: OS-Select
OS-Select(x, i)
{
if (i == r)
return x;
else if (i < r)
else
}
M
8
C
5
A
1
i=5
r=6
i=5
r=2
P
2
F
3
D
1
Q
1
H
1
Review: OS-Select
OS-Select(x, i)
{
if (i == r)
return x;
else if (i < r)
else
}
M
8
C
5
A
1
i=5
r=2
F
3
D
1
i=5
r=6
P
2
i=3
r=2
H
1
Q
1
Review: OS-Select
OS-Select(x, i)
{
if (i == r)
return x;
else if (i < r)
else
}
M
8
C
5
A
1
i=5
r=2
F
3
D
1
i=5
r=6
P
2
i=3
r=2
H
1
Q
1
i=1
r=1
Review: OS-Select
OS-Select(x, i)
{
if (i == r)
return x;
else if (i < r)
else
}
M
8
C
5
A
1
i=5
r=2
F
3
D
1
i=5
r=6
P
2
i=3
r=2
H
1
Q
1
i=1
r=1
Note: use a sentinel NIL element at the leaves with size = 0 to

simplify code, avoid testing for NULL
Review: Determining The

Rank Of An Element
Idea: rank of right child x is one
more than its parents rank, plus
the size of xs left subtree
M
8
C
5
OS-Rank(T, x)
A
F
{
1
3
y = x;
D
1
while (y != T->root)
if (y == y->p->right)
r = r + y->p->left->size + 1;
y = y->p;
return r;
}
P
2
Q
1
H
1

Rank Of An Element
Example 1:
find rank of element with key H
M
8
C
5
OS-Rank(T, x)
A
F
{
1
3
y = x;
D
1
y = y->p;
return r;
}
P
2
Q
1
H
1
y
r=1

Rank Of An Element
Example 1:
M
8
C
5
OS-Rank(T, x)
A
F
{
1
3
y = x;
D
1
y = y->p;
return r;
}
P
2
y
r = 1+1+1 = 3
H
1
r=1
Q
1

Rank Of An Element
Example 1:
M
8
C
5
y
r = 3+1+1 = 5
OS-Rank(T, x)
A
F
{
1
3
y = x;
D
1
y = y->p;
return r;
}
P
2
Q
1
r=3
H
1
r=1

Rank Of An Element
Example 1:
y
r=5
M
8
C
5
P
2
r=5
OS-Rank(T, x)
A
F
{
1
3
y = x;
D
1
y = y->p;
return r;
}
Q
1
r=3
H
1
r=1

Rank Of An Element
Example 2:
find rank of element with key P
M
8
C
5
OS-Rank(T, x)
A
F
{
1
3
y = x;
D
1
y = y->p;
return r;
}
P
2
y
r=1
Q
1
H
1

Rank Of An Element
Example 2:
find rank of element with key P
M
8
y
r=1+5+1=7
C
5
OS-Rank(T, x)
A
F
{
1
3
y = x;
D
1
y = y->p;
return r;
}
P
2
r=1
Q
1
H
1
Review: Maintaining Subtree Sizes

So by keeping subtree sizes, order statistic
operations can be done in O(lg n) time

Next: maintain sizes during Insert() and Delete()
operations
Insert(): Increment size fields of nodes traversed
during search down the tree

Delete(): Decrement sizes along a path from the
deleted node to the root
Both: Update sizes correctly during rotations
Reivew: Maintaining Subtree Sizes

y
19
x
11
6
x
19
rightRotate(y)
7
leftRotate(x)
y
12
Note that rotation invalidates only x and y

Can recalculate their sizes in constant time
Thm 15.1: can compute any property in O(lg n) time that
depends only on node, left child, and right child
Review: Methodology For

Augmenting Data Structures
Choose underlying data structure
Determine additional information to maintain
Verify that information can be maintained for
operations that modify the structure
Develop new operations
Interval Trees
The problem: maintain a set of intervals
E.g., time intervals for a scheduling program:
7
10
5
4
i = [7,10]; i low = 7; ihigh = 10

11
17
15
19
18 21
23
Interval Trees
The problem: maintain a set of intervals
E.g., time intervals for a scheduling program:
7
10
i = [7,10]; i low = 7; ihigh = 10

11
17
19
15the set that

18 overlaps
21
4 Query: find8 an interval in
a23given
query interval
[14,16] [15,18]
[16,19] [15,18] or [17,19]
[12,14] NULL
Interval Trees
Following the methodology:
Pick underlying data structure
Decide what additional information to store
Figure out how to maintain the information
Develop the desired new operations
Interval Trees
Red-black trees will store intervals, keyed on ilow
Interval Trees
We will store max, the maximum endpoint in the subtree
rooted at i
Interval Trees
int
max
[17,19]
[5,11]
[4,8]
[21,23]
[15,18]
[7,10]
What are the max fields?
Interval Trees
int
max
[17,19]
23
[5,11]
18
[4,8]
8
[21,23]
23
[15,18]
18
[7,10]
10
Note that:
x high
x max max x left max

x right max
Interval Trees

Store the maximum endpoint in the subtree rooted at i

How would we maintain max field for a BST?
Whats different?
Interval Trees
[11,35]
35
[6,20]
20
14
rightRotate(y)
30
19
[6,20]
???
leftRotate(x)
???
[11,35]
???
???
What are the new max values for the subtrees?
???
Interval Trees
[11,35]
35
[6,20]
20
14
[6,20]
???
rightRotate(y)
30
leftRotate(x)
[11,35]
???
14
19

A: Unchanged
What are the new max values for x and y?
19
30
Interval Trees
[11,35]
35
[6,20]
20
14
[6,20]
35
rightRotate(y)
30
leftRotate(x)
19

A: Unchanged
What are the new max values for x and y?
A: root value unchanged, recompute other
[11,35]
35
14
19
30
Interval Trees

Store the maximum endpoint in the subtree rooted at i

Insert: update max on way down, during rotations
Delete: similar
Searching Interval Trees

IntervalSearch(T, i)
{
x = T->root;
while (x != NULL && !overlap(i, x->interval))
if (x->left != NULL && x->left->max i->low)
x = x->left;
else
x = x->right;
return x
}
What will be the running time?
IntervalSearch() Example
Example: search for interval
overlapping [14,16]
{
x = T->root;
[17,19]
23
[5,11]
18
[4,8]
8
[21,23]
23
[15,18]
18
[7,10]
10

x = x->left;
else
x = x->right;
return x
}
IntervalSearch() Example
Example: search for interval
overlapping [12,14]
{
x = T->root;
[17,19]
23
[5,11]
18
[4,8]
8
[21,23]
23
[15,18]
18
[7,10]
10

x = x->left;
else
x = x->right;
return x
}
Correctness of IntervalSearch()
Key idea: need to check only 1 of nodes 2
children
Case 1: search goes right
Show that overlap in right subtree, or no overlap at all
Case 2: search goes left

Show that overlap in left subtree, or no overlap at all
Case 1: if search goes right, overlap in the right
subtree or no overlap in either subtree

If overlap in right subtree, were done
Otherwise:
xleft = NULL, or x left max < x low (Why?)
Thus, no overlap in left subtree!
x = x->left;
else
x = x->right;
return x;
Case 2: if search goes left, overlap in the left
subtree or no overlap in either subtree

If overlap in left subtree, were done
Otherwise:
i low x left max, by branch condition
x left max = y high for some y in left subtree
Since i and y dont overlap and i low y high,
i high < y low
Since tree is sorted by lows, i high < any low in right subtree
Thus, no overlap in right subtree
x = x->left;
else
x = x->right;
return x;

Lecture 21

Uploaded by

Copyright:

Available Formats

Lecture 21

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 21

Uploaded by

Copyright:

Available Formats

CS 332: Algorithms

Augmenting Data Structures:

Review: Dynamic Order Statistics

of an unordered set in O(n) time

void OS-Select(root, i);

Review: Order Statistic Trees

Note: use a sentinel NIL element at the leaves with size = 0 to

Review: Determining The

Review: Determining The

Review: Determining The

Review: Determining The

Review: Determining The

Review: Determining The

Review: Determining The

Review: Maintaining Subtree Sizes

operations can be done in O(lg n) time

during search down the tree

Reivew: Maintaining Subtree Sizes

Note that rotation invalidates only x and y

depends only on node, left child, and right child

Review: Methodology For

i = [7,10]; i low = 7; ihigh = 10

i = [7,10]; i low = 7; ihigh = 10

15the set that

What are the max fields?

x max max x left max

Decide what additional information to store

Figure out how to maintain the information

Develop the desired new operations

What are the new max values for the subtrees?

What are the new max values for the subtrees?

What are the new max values for the subtrees?

Decide what additional information to store

Figure out how to maintain the information

Develop the desired new operations

Searching Interval Trees

What will be the running time?

while (x != NULL && !overlap(i, x->interval))

while (x != NULL && !overlap(i, x->interval))

Case 2: search goes left

subtree or no overlap in either subtree

subtree or no overlap in either subtree

You might also like