Transcript Review of Chapter 5

Review of Chapter 5
張啟中
Selection Trees


Selection trees can merge k ordered sequences (assume in nondecreasing order) into a single sequence easily.
Two kinds of selection trees
 Winner trees





A winner tree is a complete binary tree
The root represents the smallest node in the tree.
Each leaf node represents the first record in the corresponding run.
Each non-leaf node in the tree represents the winner of its right and
left subtrees.
Loser tress




A loser tree is a complete binary tree.
Each nonleaf node retains a pointer to the loser is called a loser tree.
Each leaf node represents the first record in the corresponding run.
An additional node, node 0, has been added to represent the overall
winner of the tournament.
Winner Tree (k=8)
1
6
2
3
6
8
4
5
9
6
6
8
9
10
11
7
8
17
12
13
14
15
10
9
20
6
8
9
90
17
15
16
20
38
20
30
15
25
28
15
50
11
16
95
99
18
20
run1
run2
run3
run4
run5
run6
run7
run8
Winner Tree (k=8)
O(nlogk)
1
8
2
3
9
8
4
5
9
6
15
8
9
10
11
7
8
17
12
13
14
15
10
9
20
15
8
9
90
17
15
16
20
38
20
30
25
28
15
50
11
16
95
99
18
20
run1
run2
run3
run4
run5
run6
run7
run8
Loser Tree
0
1
Overall
winner
6
8
2
3
9
17
4
5
10
6
20
8
9
10
11
7
9
90
12
13
14
15
10
9
20
6
8
9
90
17
15
16
20
38
20
30
15
25
28
15
50
11
16
95
99
18
20
run1
run2
run3
run4
run5
run6
run7
run8
Forests


Definition
A forest is a set of n ≥ 0 disjoint trees.
When we remove the root of a tree, we’ll get
a forest.
A
B
C
E
D
F
G
H
I
Transforming A Forest Into A Binary Tree

Definition
If T1, …, Tn is a forest of trees, then the binary
tree corresponding to this forest, denoted by
B(T1, …, Tn)


is empty if n = 0
has root equal to root (T1); has left subtree equal
to B(T11, T12,…, T1m), where T11, T12,…, T1m are the
subtrees of root (T1); and has right subtree
B(T2, …, Tn).
Transforming A Forest Into A Binary Tree
A
B
E
C
F
D
G
H
I
Forest Traversals




Preorder
Inorder
Postorder (not natural)
Level-order
The Satisfiability Problem

Expression Rules





A variable is an expression
If x and y are expressions then
x  y, x  y, and x are expressions
Parentheses can be used to alter the normal order of
evaluation, which is not before and before or.
The satisfiablitity problem for formulas of proposition
calculus asks if there is an assignment of values to
the variables that causes the values of the
expression to be true.
The satisfiablitity problem is NP-Complete problem.
The Satisfiability Problem




x1



x2
x3
x3
x1
( x1  x2 )  (x1  x3 )  x3
O(2n)
Set Representation

Trees can be used to represent sets.

Pairwise Disjoint Sets
If Si and Sj, i≠j, are two sets, then there is no element that is
in both Si and Sj.

Set Operations


Disjoint set union
If Si and Sj are two disjoint sets, then their union
Si∪Sj = {all elements x such that x is in Si or Sj}.
Find(i)
Find the set containing element i.
Set Representation
n=10
0
6
7
S1= {0,6,7,8}
2
4
8
1
9
S2 = {1, 4, 9}
3
5
S3={2,3,5}
Disjoint Set Union
S1 U S2
4
0
6
7
OR
4
8
1
9
6
0
1
7
8
9
Data Representation for S1, S2, S3
Set
Name Pointer
S1
S2
S3
0
6
7
2
4
8
1
9
3
5
Array Representation of S1, S2, S3
i
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
parent
-1
4
-1
2
-1
2
0
0
0
4
Degenerate Tree
n-1
Union operation O(n)
Find operation O(n2)
n-2
union(0, 1), find(0)
union(1, 2), find(1)
union(n-2, n-1), find(n-1)
0
Improve the performance of Set Union
and Find Algorithms

Weighting Rule [Weighting rule for union(I, j)]


If the number of nodes in the tree with root i is
less than the number in the tree with root j, then
make j the parent of i; otherwise make i the parent
of j.
Collapsing Rule

If j is a node on the path from i to its root and
parent[i]≠ root(i), then set parent[j] to root(i).
Set Union with The Weighting Rule
0
1
n-1
0
2
n-1
0
1
1
1
0
4
2
3
3
n-1
2
0
n-1
1
2
3
n-1
Set Find with Collapsing Rule
1
[-8]
[-8]
0
0
2
3
Before
collapsing
1
4
5
6
7
2
4
3
5
After
collapsing
6
7
Equivalence Class
[-1]
[-1]
[-1]
[-1]
[-1]
[-1]
[-1]
[-1]
[-1]
[-1]
[-1]
[-1]
0
1
2
3
4
5
6
7
8
9
10
11
(a) Initial trees
[-2]
[-2]
[-2]
[-2]
[-1]
[-1]
[-1]
[-1]
0
3
6
8
2
5
7
11
4
1
10
9
(b) Height-2 trees following 0≡4, 3≡1, 6≡10, and 8≡9
Equivalence Class
(C) Trees following 7≡4, 6≡8, 3≡5, and 2≡11
[-3]
[-4]
[-3]
[-2]
0
6
3
2
10
7
4
8
11
5
1
9
4
[-3]
[-4]
[-3]
0
6
3
7
2
11
10
8
9
1
5
(d) Thees following 11≡0
Counting Binary Trees

Problem



Determine the number of distinct binary trees
having n nodes.
Determine the number of distinct permutations of
the numbers from 1 through n obtainable by a
stack.
Determine the number of distinct ways of
multiplying n+1 matrices.
Distinct binary trees

n=0 or n=1  1 binary tree
n=2  2 distinct binary trees.

n=3  5 distinct binary trees (自己練習畫)

bn
bi
bn   bi bn i 1 , n  1 , and b0  1
bn-i-1
Stack Permutations
How many permutations can we obtain by
passing the numbers 1 through n through
stack ? See chapter 3 about stack.
 For example, the numbers 1, 2, 3
(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,2,1) but (3,1,2)
 The recursive formula is
bn = b0bn-1 + b1bn-2 + …… + bn-2b1+ bn-1b0

Construct The Binary Tree from Preorder
and Inorder Sequence

Give preorder and inorder sequence as follows.
preorder sequence A B C D E F G H I
Inorder sequence B C A E D G H F I

Problem


Does such a pair of sequences uniquely define a
binary tree ? (Can this pair of sequences come
from more than one binary tree?)
Conclusion

Every binary tree has a unique pair of preorder /
inorder sequences.
Construct The Binary Tree from Preorder
and Inorder Sequence
A
A
B, C
D, E, F, G, H, I
B
D
C
A
F
E
I
G
B
D, E, F, G, H, I
C
H
Inorder and Preorder Permutations
1
A
B
2
D
C
3
F
E
4
I
G
6
5
H
Preorder: 1, 2, 3, 4, 5, 6, 7, 8, 9
Inorder: 2, 3, 1, 5, 4, 7, 8, 6, 9
9
7
8
Stack Permutations
Preorder permutation 1, 2, 3
2
2
3
(1, 2, 3)
1
1
1
1
2
3
2
2
3
3
(1, 3, 2)
(2, 1, 3)
1
(2, 3, 1)
Inorder permutations
3
(3, 2, 1)
Stack Permutations
The number of distinct Binary Trees with n nodes
≡
Inorder permutations obtainable from binary trees
having the preorder permutations, 1,2,3,….,n
≡
The number of distinct permutations by passing 1..n
through stack
Matrix Multiplication




Computing the product of n matrices
M1 * M 2 * … * Mn
By matrix multiplication associative law, we can perform
these multiplications in any order.
For example, n=3 (n=4 自己練習)
(M1 * M2) * M3
M1 * (M2 * M3)
The number of distinct ways to obtain M1 * M2 * … * Mn
n 1
bn   bi bn i , n  1
i 1
Number of Distinct Binary Trees


B( x)   bi x i
Let
i 0
which is the generating function for the number of binary
trees.
By the recurrence relation we get
xB2 ( x)  B( x)  1
B( x) 
1 1 4x
2x

1 / 2 
 1/ 2 
1 
n
m 2 m 1 m
1   




B( x) 
(

4
x
)

(

1
)
2
x






2 x  n0  n 
 m0  m  1
1  2n 
 
bn 
n 1  n 
 bn  O(4 n / n 3 / 2 )