Transcript Fast Algorithms for Finding Nearest Common Ancestors

Dov Harel and Robert Endre Tarjan
Fast Algorithms for Finding
Nearest Common Ancestors
SIAM J. COMPUT. Vol. 13:338--55, May 1984
Speaker : Chan Shuo Wu (吳展碩)
Dept. of CSIE
National Chi Nan University
Source

Dov Harel and Robert Endre Tarjan. Fast Algorithm
for Finding Nearest Common Ancestors. SIAM J.
Comput. Vol. 13:338--55, May 1984.
2
Introduction

lowest common ancestor
Denote the nearest common ancestor of vertices x
and y by nca(x, y).
3

This paper presents an algorithm for NCA that
runs on a random access machine and uses O(n)
preprocessing time, O(1) time per query, and O(n)
space.
4
Idea
Preprocessing
 For complete binary trees
 For general rooted trees

The difficulty is on how to perform NCA query in constant time.
5
A Fast Algorithm for
Complete Binary Trees
6
A Complete Binary Tree B
7
Path Number

Each node v of B is assigned a number that
encodes the unique path from the root to v.
1000
8
0100
1100
4
12
0010
0110
2
6
1
3
0001
0011
5
0101
1010
1110
10
14
7
9
11
13
0111
1001
1011
1101
15
1111
8
1000
8
1001
1011
---0010
000
1001
---1011 Set to 0
---1010
0100
1100
4
12
0010
0110
2
1010
6
1
3
0001
0011
5
0101
1110
10
14
7
9
11
13
15
0111
1001
1011
1101
1111
9
Computing nca(x, y)




Compute XOR(x, y)
Find the position of the left-most 1-bit in XOR(x, y).
Let it be k.
Let t be x (or y). Set the bit in position k of t to be 1
and those bits right to k to be 0.
Set nca(x, y)=t.
10
Preprocessing of B
Build an O(n)-size table in O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
...
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 ...
1
2
2
3
3
3
3
4
4
4
4
4
4
4
4
...
1111 1110 1110 1100 1100 1100 1100 1000 1000 1000 1000 1000 1000 1000 1000 ...
1

2
4
8
16
With this table, the following operations on binary
numbers can be done in constant time:


find the position k of the left-most 1-bit
set bits to the right of position k to zero
11
1000
8
1001
XOR
1011
---0010
OR
1001
---1011
AND
1110
---1010
1
2
1100
0100
4
12
3
4
5
1
3
0001
0011
6
10
6
2
7
8
9
14
7
9
11
13
15
0111
1001
1011
1101
1111
5
0101
1110
1010
0110
0010
10
11
12
13
14
15
...
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 ...
1
2
2
3
3
3
3
4
4
4
4
4
4
4
4
...
1111 1110 1110 1100 1100 1100 1100 1000 1000 1000 1000 1000 1000 1000 1000 ...
12
Mapping General Tree to
Complete Binary Tree
13
T
B
14
Preprocessing of T
15
Depth-First Numbering
0001
1
0010
0101
2
5
1000
3
4
6
7
0011
0100
0110
0111
8
9
10
1001
1010
16
Definition For any number v, height of v, h(v) denotes the
position of the least-significant 1-bit in the binary representation
of v.
Definition For a node v of T, let I(v) be a node w in T such that
h(w) is maximum over all nodes in the subtree of v.
1000
I (v) = 1000
8
0001
1
0100
1100
4
12
I (v) = 0100
0010
0101
2
0010
0110
2
1010
6
1110
10
1
3
5
7
9
0001
0011
0101
0111
1001
5
14
11
1011
13
15
1101
1111
1000
3
4
6
7
0011
0100
0110
0111
8
9
10
1001
1010
v  I (v)
0001
1
a run
0010
0101
2
5
1000
3
0011
4
0100
6
7
0110
0111
8
9
1001
10
1010
18
Lemma For any node v in T, there is a unique node w
in the subtree of v such that h(w) is maximum over all
nodes in v's subtree.
0010
0100
：
1000
：
1100
For any node v in T, node I(v) is the deepest node in the run
containing node v.
The function v  I(v) is well defined.
19
Lemma If z is an ancestor of x in T then I(z) is an
ancestor of I(x) in B.
z
I(z)
x
I(z)
I(x)
I(x)
T
B
20
Lemma If z is an ancestor of x in T then I(z) is an
ancestor of I(x) in B.
Proof
I(z) = ...010100
I(x) = ...000110
N = ...010000
z
x
010100
I(z)
000110
I(x)
010000
N
T
21
Lemma If z is an ancestor of x in T then I(z) is an
ancestor of I(x) in B.
z
I(z)
x
I(z)
I(x)
I(y)
I(x)
y
T
I(y)
B
22
Preprocessing of T (cont.)
23
For each node v in T, create an O(log n)-bit number Av.
Bit Av(i) is set to 1 if and only if node v has some
ancestor in T that maps to height i in B.
1
1000
1000
0100
1100
2
3
0011
1101
5
4
6
7
0110
1010
0111
1001
8
9
1001
1001
10
1010
1010
24
For each node v in T, create an O(log n) bit number Av.
Bit Av(i) is set to 1 if and only if node v has some
ancestor in T that maps to height i in B.
1000
1
0100
2
5
3
4
6
0011
7
0110
8
0111
9
10
1001
1010
1
2
3
4
5
6
7
8
9
10
1000
1100
1101
1100
1000
1010
1001
1000
1001
1010
25
For each node in T, set a pointer to its parent
node in T.
0001
1
0010
0101
2
5
1000
3
4
6
7
0011
0100
0110
0111
8
9
10
1001
1010
26
For each node v, set a pointer to the root of the
run containing node v.
0001
1
0010
0101
2
5
1000
3
4
6
7
0011
0100
0110
0111
8
9
10
1001
1010
27
Constant-Time NCA Retrieval
z
I(z)
x
I(z)
I(x)
I(y)
I(x)
y
T
I(y)
B
28
Constant-Time nca Retrieval
x’
y’
x
I(z)
I(x)
y
T
I(y)
29
1.
2.
Find
Find
both
Find
3.



4.
5.
the lowest common ancestor b in B of nodes I(x) and I(y).
the smallest position j greater than or equal to h(b) such that
numbers Ax and Ay have 1-bits in position j. j is then h(I(z)).
node x’, the closet node to x on the same run as z as follow:
Find the position l of the right-most 1-bit in Ax.
If l = j, then set x’ = x (x and z are on the same run in T) and go to step 4.
Otherwise (when l < j)
Find the position k of the left-most 1-bit in Ax that is to the right of
position j. From the number consisting of the bits of I(x) to the left of
position k, followed by a 1-bit in position k, followed by all zeros. (That
number will be I(w), even though we don’t yet know w.) Look up node
L(I(w)), which must be node w. Set node x’ to be the parent of node w in
T.
Find node y’, the closest node to y on the same run as z, by the
same approach as in step 3.
If x’ < y’ then set z to x’, else set z to y’.
30
I (v) = 1000
0011
XOR
0110
---0101
OR
0011
---0111
AND
1100
---0100
0001
1
I (v) = 0100
0010
0101
2
5
1000
3
4
6
7
0011
0100
0110
0111
8
1000
8
9
10
1001
1010
0100
1100
4
12
0010
0110
2
1010
6
1
3
0001
0011
5
0101
1110
10
14
7
9
11
13
15
0111
1001
1011
1101
311111
Lemma Let b be the NCA of I(x) and I(y) in B. Let j be the
smallest position  h(b) such that both Ax and Ay have 1-bits in
position j. Then node I(z) is at height j in B.
z
I(z)
x
b
I(z)
I(x)
I(y)
I(x)
y
T
I(y)
B
32
I (v) = 1000
1101
AND
1100
---1100
0001
1
I (v) = 0100
0010
1100
AND
1000
---1000
0101
2
5
1000
A
3
4
6
7
0011
0100
0110
0111
1010
AND
1100
---1000
h(I (z)) = h(1000) = 4
8
9
10
1001
1010
1
2
3
4
5
6
7
8
9
10
1000
1100
1101
1100
1000
1010
1001
1000
1001
1010
33
Constant-Time NCA Retrieval
x’
y’
x
I(z)
I(x)
y
T
I(y)
34
I (v) = 1000
h(I (z)) = 4
0001
1
I (v) = 0100
0010
0101
2
5
1000
3
4
0011
6
0100
7
0110
8
0111
9
10
1001
A
1101
AND
0111 = NOT 1000
---0101
OR
0011
---0111
AND
1100
---0100
1010
1
2
3
4
5
6
7
8
9
10
1000
1100
1101
1100
1000
1010
1001
1000
1001
1010
35
Constant-Time NCA Retrieval
x’
y’
x
I(z)
I(x)
y
T
I(y)
36
0001
1
0010
0101
2
5
1000
3
4
6
7
0011
0100
0110
0111
8
9
10
1001
1010
37
Constant-Time NCA Retrieval
x’
y’
x
I(z)
I(x)
y
T
I(y)
38
Constant-Time NCA Retrieval
z
y’
x
I(z)
I(x)
y
T
I(y)
39
40