COMP90038
Algorithms and Complexity
Lecture 12: More Divide-and-Conquer Algorithms (with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Divide and Conquer
In the last lecture we studied the archetypal divide- and-conquer sorting algorithms: mergesort and quicksort.
We also introduced the powerful master theorem, providing solutions to a large class of recurrence relations, for free.
•
•
•
Now we shall look at tree traversal, and then a final example of divide-and-conquer, giving a better solution to the closest-pair problem.
allows us to quickly determine the complexity of
•
these divide-and-conquer algorithms
3
Binary Trees
This tree has height 4, the empty tree having height -1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
An example of a binary tree, with empty subtrees
•
marked as ☐
•
Review of Linked List Terminology
node
pointer
(in Java: “reference”)
X:
X is (a pointer to) the head node of the list
2
2
3
5
7
2
Y: “Y.val” refers to
“Y.next” refers to
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tree Terminology
root
right subtree
left subtree
5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Tree Terminology
t:
17
33
33
… …… …
t is (a pointer to) the root node of the tree
t:
“t.root” refers to “t.left” refers to
17
“t.right” refers to
6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Binary Trees
This tree has height 4, the empty tree having height -1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
An example of a binary tree, with empty subtrees
•
marked as ☐
7
•
Empty Nodes
38
25
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
empty trees are just null pointers
right subtree is empty
null pointer
9
Levels and Height
Level 0
Level 1 Level 2 Level 3 Level 4
So the tree has height 4 (its maximum level) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Binary Tree Concepts
Special trees have their external nodes ☐ ︎only at
•
level h and h+1 for some h:
10
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
A full binary tree:
Each node has 0 or 2
(non-empty) children.
A complete tree: Each level filled left to right.
(Every level except perhaps the
last is completely filled.)
Calculating the Height
Recursion is the natural way of calculating the height: T:
•
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Height Complexity
Input size: number n of (internal) nodes (e.g. for T n is 13) Number of external nodes always n+1 (e.g. for T x is 14)
The function HEIGHT makes one tree comparison (is T null/ empty?) per node (internal and external), so altogether 2n +
• • •
1 comparisons.
T:
12
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Binary Tree Traversal
Preorder traversal visits the root, then the left Inorder traversal visits the left subtree, then the
•
subtree, and finally the right subtree.
•
root, and finally the right subtree.
Postorder traversal visits the left subtree, the right Level-order traversal visits the nodes, level by
•
subtree, and finally the root.
•
level, starting from the root.
Preorder Traversal Visit order:
PREORDERTRAVERSE(17) Call Stack
14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal Visit order: 17
PREORDERTRAVERSE(17) Call Stack
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal Visit order: 17
PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal Visit order: 17 33
PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal Visit order: 17 33
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(19) PREORDERTRAVERSE(33)
PREORDERTRAVERSE(17) Call Stack
Preorder Traversal Visit order: 17 33 19
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(19) PREORDERTRAVERSE(33)
PREORDERTRAVERSE(17) Call Stack
Preorder Traversal Visit order: 17 33 19
20
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(null)
PREORDERTRAVERSE(19) PREORDERTRAVERSE(33)
PREORDERTRAVERSE(17) Call Stack
Preorder Traversal Visit order: 17 33 19
21
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(19) PREORDERTRAVERSE(33)
PREORDERTRAVERSE(17) Call Stack
Preorder Traversal Visit order: 17 33 19
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(null)
PREORDERTRAVERSE(19) PREORDERTRAVERSE(33)
PREORDERTRAVERSE(17) Call Stack
Preorder Traversal Visit order: 17 33 19
23
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(19) PREORDERTRAVERSE(33)
PREORDERTRAVERSE(17) Call Stack
Preorder Traversal Visit order: 17 33 19
PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal Visit order: 17 33 19
25
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal Visit order: 17 33 19 16
26
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal Visit order: 17 33 19 16
27
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(38) PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal
Visit order: 17 33 19 16 38
28
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(38) PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal
Visit order: 17 33 19 16 38
29
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(38) PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
(…skipping the calls to PREORDERTRAVERSE(null)…)
Preorder Traversal
Visit order: 17 33 19 16 38
30
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal
Visit order: 17 33 19 16 38
31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(31) PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal
Visit order: 17 33 19 16 38 31
32
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(31) PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal
Visit order: 17 33 19 16 38 31
33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(31) PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
(…skipping the calls to PREORDERTRAVERSE(null)…)
Preorder Traversal
Visit order: 17 33 19 16 38 31
34
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(16) PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
Preorder Traversal
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(33) PREORDERTRAVERSE(17)
Call Stack
35 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(17) Call Stack
36 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31
PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
37 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48
PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
38 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48
PREORDERTRAVERSE(11) PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
39
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11
PREORDERTRAVERSE(11) PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
40
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11
41
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(11) PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
(…skipping the calls to PREORDERTRAVERSE(null)…)
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11
PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
42 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11
PREORDERTRAVERSE(14) PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
43
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48
PREORDERTRAVERSE(14) PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
11 14
44
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11 14
45
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
PREORDERTRAVERSE(14) PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
(…skipping the calls to PREORDERTRAVERSE(null)…)
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11 14
PREORDERTRAVERSE(48) PREORDERTRAVERSE(17)
Call Stack
46 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11 14
PREORDERTRAVERSE(17) Call Stack
47 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal
Visit order: 17 33 19 16 38 31 48 11 14
Call Stack
48 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal Visit order:
INORDERTRAVERSE(17) Call Stack
49 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal Visit order:
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
50 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal Visit order:
51
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(19)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order:
52
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null)
INORDERTRAVERSE(19)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order:
53
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(19)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19
54
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(19)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19
55
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null)
INORDERTRAVERSE(19)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19
56
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(19)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
57 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal Visit order: 19 33
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
58 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal Visit order: 19 33
59
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33
60
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(38) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33
61
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null) INORDERTRAVERSE(38)
INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33
62
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(38) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38
63
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(38) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38
64
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null) INORDERTRAVERSE(38)
INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38
65
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(38) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38
66
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38 16
67
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38 16
68
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(31) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38 16
69
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null) INORDERTRAVERSE(31) INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal Visit order: 19 33 38 16
70
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(31) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31
71
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(31) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31
72
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null) INORDERTRAVERSE(31) INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31
73
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(31) INORDERTRAVERSE(16)
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31
74
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(16) INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31
INORDERTRAVERSE(33) INORDERTRAVERSE(17)
Call Stack
75 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31
INORDERTRAVERSE(17) Call Stack
76 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17
INORDERTRAVERSE(17) Call Stack
77 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
78 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17
79
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(11) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31 17
80
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null) INORDERTRAVERSE(11)
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31 17
81
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(11) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31 17 11
82
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(11) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31 17 11
83
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(null) INORDERTRAVERSE(11)
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31 17 11
84
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
INORDERTRAVERSE(11) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
Inorder Traversal
Visit order: 19 33 38 16 31 17 11
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
85 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
86 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48
INORDERTRAVERSE(14) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
87
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48
INORDERTRAVERSE(null) INORDERTRAVERSE(14)
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
88
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48
INORDERTRAVERSE(14) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
89
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48 14
INORDERTRAVERSE(14) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
90
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48 14
INORDERTRAVERSE(null) INORDERTRAVERSE(14)
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
91
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48 14
INORDERTRAVERSE(14) INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
92
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48 14
INORDERTRAVERSE(48) INORDERTRAVERSE(17)
Call Stack
93 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48 14
INORDERTRAVERSE(17) Call Stack
94 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Inorder Traversal
Visit order: 19 33 38 16 31 17 11 48 14
Call Stack
95 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order:
POSTORDERTRAVERSE(17) Call Stack
96 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order:
POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
97 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order:
98
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
POSTORDERTRAVERSE(19) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
Postorder Traversal Visit order:
99
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
POSTORDERTRAVERSE(null)
POSTORDERTRAVERSE(19) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
Postorder Traversal Visit order:
POSTORDERTRAVERSE(19) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
100 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order:
POSTORDERTRAVERSE(null)
POSTORDERTRAVERSE(19) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
101 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order:
POSTORDERTRAVERSE(19) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
102 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(19) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
104 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
105 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
106 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(null) POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
107 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
108 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(null) POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
109 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19
POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
110 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38
POSTORDERTRAVERSE(38)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
111 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
112 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38
POSTORDERTRAVERSE(31)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
113 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38
POSTORDERTRAVERSE(31)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
(…skipping the calls to POSTORDERTRAVERSE(null)…)
114 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31
POSTORDERTRAVERSE(31)
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
115 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
116 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31 16
POSTORDERTRAVERSE(16) POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
117 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31 16
POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
118 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31 16 33
POSTORDERTRAVERSE(33) POSTORDERTRAVERSE(17)
Call Stack
119 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31 16 33
POSTORDERTRAVERSE(17) Call Stack
120 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31 16 33
POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
121 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31 16 33
POSTORDERTRAVERSE(11) POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
122 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal Visit order: 19 38 31 16 33
POSTORDERTRAVERSE(11) POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
(…skipping the calls to POSTORDERTRAVERSE(null)…)
123 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11
POSTORDERTRAVERSE(11) POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
124 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11
POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
125 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11
POSTORDERTRAVERSE(14) POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
126 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11
POSTORDERTRAVERSE(14) POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
(…skipping the calls to POSTORDERTRAVERSE(null)…)
127 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11 14
POSTORDERTRAVERSE(14) POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
128 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11 14
POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
129 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11 14 48
POSTORDERTRAVERSE(48) POSTORDERTRAVERSE(17)
Call Stack
130 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11 14 48
POSTORDERTRAVERSE(17) Call Stack
131 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11 14 48
17
POSTORDERTRAVERSE(17) Call Stack
132 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Postorder Traversal
Visit order: 19 38 31 16 33 11 14 48
17
Call Stack
133 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
134
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Preorder Traversal Using a Stack
Explicitly maintain a stack of nodes
In an implementation, the elements placed onto the stack would not be whole trees, but pointers to the corresponding internal nodes
•
•
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue:
Traversal order:
•
135
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 17
Traversal order:
•
136
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue:
Traversal order:
•
137
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue:
Traversal order: 17
•
138
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 33
Traversal order: 17
•
139
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 33 48
Traversal order: 17
•
140
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 48
Traversal order: 17
•
141
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 48
Traversal order: 17 33
•
142
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 48 19
Traversal order: 17 33
•
143
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 48 19 16
Traversal order: 17 33
•
144
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 19 16
Traversal order: 17 33
•
145
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 19 16
Traversal order: 17 33 48
•
146
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 19 16 11
Traversal order: 17 33 48
•
147
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 19 16 11 14
Traversal order: 17 33 48
•
148
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 16 11 14
Traversal order: 17 33 48
•
149
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 16 11 14
Traversal order: 17 33 48 19
•
150
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 11 14
Traversal order: 17 33 48 19
•
151
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 11 14
Traversal order: 17 33 48 19 16
•
152
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 11 14 38
Traversal order: 17 33 48 19 16
•
153
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 11 14 38 31
Traversal order: 17 33 48 19 16
•
154
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 14 38 31
Traversal order: 17 33 48 19 16
•
155
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 14 38 31
Traversal order: 17 33 48 19 16 11
•
156
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 38 31
Traversal order: 17 33 48 19 16 11
•
157
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 38 31
Traversal order: 17 33 48 19 16 11 14
•
158
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 31
Traversal order: 17 33 48 19 16 11 14
•
159
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue: 31
Traversal order: 17 33 48 19 16 11 14 38
•
160
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue:
Traversal order: 17 33 48 19 16 11 14 38
•
161
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Level-Order Traversal Using a Queue
Replace the stack with a queue
Queue:
Traversal order: 17 33 48 19 16 11 14 38 31
•
162
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem (2D) Revisited (see Lecture 5)
163 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
164
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
In Lecture 5 we gave a brute-force algorithm for the closest pair problem: Given n points in the Cartesian plane, find a pair with minimal distance.
•
The brute-force method had complexity Θ(n2). We can
•
use divide-and-conquer to do better, namely Θ(n log n).
First, sort the points by x value and store the result in result in array byY.
•
array byX. Also sort the points by y value and store the
•
Now we can identify the x median, and recursively process the set PL of points with lower x values, as well as the set PR with higher x values.
Closest Pair Problem Revisited
165 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
166 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
167 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
168 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
169 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
170 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
171 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
172
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem Revisited
•
For each point in S, consider just its “close” neighbours in S.
The recursive calls will identify dL, the shortest distance for pairs in
•
PL, and dR, the shortest distance for pairs in PR.
Let m be the x median and let d = min(dL,dR). This d is a
•
candidate for the smallest distance.
But d may not be the global minimum—there could be some close
•
pair whose points are on opposite sides of the median line x = m.
For candidates that may improve on d we only need to look at
•
those in the band m − d ≤ x ≤ m + d.
So pick out, from array byY, each point p with x-coordinate
•
between m−d and m+d, and keep these in array S.
Closest Pair Problem Revisited
•
It can be shown that the while loop can execute at most 5 times for each i value— see diagram.
The following calculates the smallest distance
•
and leaves the (square of the) result in minsq.
173
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
174
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
You’re Learning Heaps!
•
Next up: Priority queues, heaps and heapsort.