Announcements
Pre-spring break survey coming later today. Complete for extra credit.
HW3 is out. Due next Thursday.
Guerrilla section Saturday. Covers all material up to today with a focus on hashing.
CS61B
Lecture 25: Advanced Trees
Traversals
Rooted Trees
We’ve used BSTS to build Maps and Sets, and Heaps to build a PQ.
… but trees are a more general concept.
proj1
synthesizer
spec
GuitarHeroLite.java
hw1.md
karplus-strong.png
...
skeleton
proj0
audio
data
...
...
...
...
planets.txt
Rooted Trees
Given such a tree, find how much disk space all the files use.
proj1
synthesizer
spec
GuitarHeroLite.java
hw1.md
karplus-strong.png
...
skeleton
proj0
audio
data
...
...
...
...
planets.txt
Tree Traversal
Level Order
Depth First Traversals
A
C
B
D
E
F
G
Depth First Traversals
Preorder: “Visit” a node, then traverse its children:
A
C
B
D
E
F
G
preOrder(BSTNode x) {
if (x == null) return;� print(x.key)� preOrder(x.left)� preOrder(x.right)�}
A
B
C
D
E
F
G
Depth First Traversals
Preorder traversal: “Visit” a node, then traverse its children: DBACFEG
Inorder traversal: Traverse left child, visit, then traverse right child:
A
C
B
D
E
F
G
inOrder(BSTNode x) {
if (x == null) return;� inOrder(x.left)� print(x.key)
inOrder(x.right)�}
preOrder(BSTNode x) {
if (x == null) return;� print(x.key)� preOrder(x.left)� preOrder(x.right)�}
A
B
C
D
E
F
G
Depth First Traversals http://shoutkey.com/on
Preorder traversal: “Visit” a node, then traverse its children: DBACFEG
Inorder traversal: Traverse left child, visit, traverse right child: ABCDEFG
Postorder traversal: Traverse left, traverse right, then visit: ???????
A
C
B
D
E
F
G
postOrder(BSTNode x) {
if (x == null) return;� postOrder(x.left)
postOrder(x.right)� print(x.key)
}
Depth First Traversals
Preorder traversal: “Visit” a node, then traverse its children: DBACFEG
Inorder traversal: Traverse left child, visit, traverse right child: ABCDEFG
Postorder traversal: Traverse left, traverse right, then visit: ACBEGFD
A
C
B
D
E
F
G
postOrder(BSTNode x) {
if (x == null) return;� postOrder(x.left)
postOrder(x.right)� print(x.key)
}
A Weird Trick
Example: Post-Order Traversal
9
4
2
1
3
6
8
5
7
What Good Are All These Traversals?
Example: Preorder Traversal for printing directory listing:
python
sc2APM
directOverlay
notes
directO.sln
directO.suo
directIO
printAPM.py
DXHookD3D11.cs
Injector.cs
What Good Are All These Traversals?
Example: Postorder Traversal for gathering file sizes.
python
sc2APM
directOverlay
notes
directO.sln
directO.suo
directIO
printAPM.py
DXHookD3D11.cs
Injector.cs
18381
8798
38912
881
324
874
postOrder(BSTNode x) {
if (x == null) return 0;� int total = 0;
for (BSTNode c : x.children())� total += postOrder(c)� total += x.fileSize();
return total;�}
What Good Are All These Traversals?
Example: Postorder Traversal for gathering file sizes.
python
sc2APM
directOverlay
notes
directO.sln
directO.suo
directIO
printAPM.py
DXHookD3D11.cs
Injector.cs
18381
8798
38912
881
324
874
postOrder(BSTNode x) {
if (x == null) return 0;� int total = 0;
for (BSTNode c : x.children())� total += postOrder(c)� total += x.fileSize();
return total;�}
27179
66972
874
68170
Visitor Pattern (Patterns)
When writing general tree traversal code. Avoid rewriting traversal for every task of interest (print, sum filesizes, etc.) by using the Visitor pattern.
void preorderTraverse(Tree<Label> T, Action<Label> whatToDo) {
if (T == null) { return; }
whatToDo.visit(T); /* before we hard coded a print */
preorderTraverse(T.left, whatToDo);
preorderTraverse(T.right, whatToDo);
}
interface Action<Label> {
void visit(Tree<Label> T);
}
class FindPig implements Action<String> {
boolean found = false;
@Override
void visit(Tree<String> T) {
if ("pig".equals(T.label))
{ found = true; }
}
}
preorderTraverse(someTree, new FindPig());
Preorder Traversal Runtime: http://shoutkey.com/what
What is the runtime of a preorder traversal in terms of N, the number of nodes? (in code below, assume the visit action takes constant time)
e
b
g
a
d
f
j
v
p
y
m
r
x
z
k
void preorderTraverse(Tree<Label> T, Action<Label> whatToDo) {
if (T == null) { return; }
whatToDo.visit(T);
preorderTraverse(T.left, whatToDo);
preorderTraverse(T.right, whatToDo);
}
Preorder Traversal Runtime
What is the runtime of a preorder traversal in terms of N, the number of nodes? (in code below, assume the visit action takes constant time)
3. Θ(N) : Every node visited exactly once. Constant work per visit.
Runtime is exponential in height of the tree, not number of items.
e
b
g
a
d
f
j
v
p
y
m
r
x
z
k
N = 15
H = 3
Level Order Traversal
Tree Traversal: Level Order Traversal
The Level Order Traversal is the result of reading the nodes “like a book”, one level at a time.
How would we implement a level order traversal?
A
C
B
D
E
F
G
Level-Order Traversal through Iterative Deepening
Run visitLevel H times, one for each level.
A
C
B
D
E
F
G
The strategy described on this slide is called “Iterative Deepening”.
public void visitLevel(Tree T, int level, Action toDo) {
if (T == null)
{ return; }
if (lev == 0)
{ toDo.visit(T.key); }
else {
visitLevel(T.left(), lev - 1);
visitLevel(T.right(), lev - 1);
}
}
public void levelOrder(Tree T, Action toDo) {
for (int i = 0; i < T.height(); i += 1) {
visitLevel(T, i, toDo);
}
}
Level-Order Traversal through Iterative Deepening
0
1
0
0
2
1
1
0
0
0
Partially completed Iterative Deepening,
Iterative Deepening Runtime: http://shoutkey.com/sepia
What is the runtime to complete iterative deepening on a complete tree (as shown below) as a function of node count N?
0
1
2
0
0
0
0
0
0
0
0
0
0
0
0
2
1
0
2
1
3
1
1
1
1
0
Preorder Traversal and Prefix Expressions
What is the runtime to complete iterative deepening on a complete tree (as shown below) as a function of node count N?
e
b
g
a
d
f
j
v
p
y
m
r
x
z
k
Top level visited: 1
Then top two levels visited: 1 + 2 = 3
Then top three levels visited: 1 + 2 + 4 = 7
Then top four: 1 + 2 + 4 + 8 = 15
Top H levels: 21+22+23+...+2H - H = Θ(N)
Note: Exact sum doesn’t matter, the order of growth (and hence the pattern) is what is important.
Interesting aside: Much harder to solve as “4 visits at level 0” then “6 visits at level 1”, etc.
Iterative Deepening Runtime: http://shoutkey.com/beacon
What is the runtime for iterative deepening on a “spindly” tree?
v
y
z
k
Iterative Deepening Runtime
What is the runtime for iterative deepening on a “spindly” tree?
Top level visited: 1
Then top two levels: 1 + 1 = 2
Then top three levels: 1 + 1 + 1 = 3
Top H levels: H
Total: 1 + 2 + 3 + … + H = H2
H = N - 1, so Θ(N2)
v
y
z
k
Tree Height
For algorithms whose runtime depends on height, difference between bushy tree and spindly tree can be huge!
H = Θ(N)
H = Θ(log(N))
Iterative deepening runtimes: Θ(N) vs. Θ(N2)
Range Finding
Geometric Search
Suppose we want an operation that returns all items in a range:
Example:
dog
bag
flat
alf
cat
elf
glut
eyes
Geometric Search
Easy approach, just do a traversal of the whole tree, and use visitor pattern to collect matching items.
Runtime is Θ(N)
class rangeFind implements Action<String> {
private Label min, max;
public Set<Label> inRange;
public rangeFind(Label min, Label max) {
this.min = min; this.max = max;
inRange = new HashSet<Label>();
}
void action(Tree<Label> T) {
if (T.label ≼ max && T.label ≽ min) {
inRange.add(T.label);
}
}
}
Geometric Search
Suppose we want an operation that returns all items in a range:
Can avoid need to traverse entire tree by being clever.
Example:
dog
bag
flat
alf
cat
elf
glut
eyes
Nodes inspected: dog, flat, elf, eyes
Nodes matching: dog, elf
Pruning and findInRange Runtime
Suppose we want an operation that returns all items in a range:
dog
bag
flat
alf
cat
elf
glut
eyes
Nodes inspected: dog, flat, elf, eyes
Nodes matching: dog, elf
Pruning: Restricting our search to only nodes that might contain the answers we seek.
Pruning and findInRange Runtime
Suppose we want an operation that returns all items in a range:
dog
bag
flat
alf
cat
elf
glut
eyes
Nodes inspected: dog, flat, elf, eyes
Nodes matching: dog, elf
Pruning: Restricting our search to only nodes that might contain the answers we seek.
Runtime for our search: Θ(log N + R)
See study guide A-level problems for proof.
Spatial Trees
2D Range Finding
Suppose we want to do range finding on Planets in space.
Could iterate through all objects in Θ(N) time.
Pruning implies we need some kind of tree, but ...
Building Trees of Two Dimensional Data
So far, we’ve only considered one dimensional data.
Some data is two dimensional, e.g. the location of Planets.
If we’re comparing by location:
1.5, 1.6
1.0, 2.8
1.5, 1.6
1.0, 2.8
(1.5, 1.6)
(1.0, 2.8)
X-Based Tree
Y-Based Tree
Handling Multidimensional Data: Quadtrees
Quadtrees:
Definition, quadtree is either:
A
NE
SE
SW
NW
Quadtree Demo
Below: Quadtree Representation of 5 objects in 2D space.
A
NW
NE
SE
SW
B
C
SW
SE
D
E
A
(-1, -1)
(2, 2)
B
(0, 1)
C
D
(1, 0)
E
(-2, -2)
Quadtree Demo
Quadtrees allow us to prune when performing a rectangle search.
A
NW
NE
SE
SW
B
C
SW
SE
D
E
A
(-1, -1)
(2, 2)
B
(0, 1)
C
D
(1, 0)
E
(-2, -2)
Tree Iterators (Extra)
Iterators
Suppose we want to iterate through a tree using the : operator.
How can we adapt our traversal code to implement next() and hasNext()?
Iteration: The Obvious Way
One approach: Create an action class that puts visited item in a list.
Iteration: The Obvious Way
One approach: Create an action class that puts visited item in a list.
Iteration: Space-saving Approach
Tricky question: How could convert our recursive traversal into iterative code using a stack?
Observation: Each call to preorderTraverse is the equivalent of putting a call on the call stack.
Iteration: Space-saving Approach
Tricky question: How could convert our recursive traversal into iterative code using a stack?
Observation: Each call to preorderTraverse is the equivalent of putting a call on the call stack.
Iteration: Space-saving Approach
Use our stack-based approach, but use next() instead of looping.
Citations
Title figure: A thing I made (one of the first Java programs I wrote during my teaching career)
Pruning image: https://res.cloudinary.com/dc8hy36qb/image/upload/v1435213404/Fruit-Tree-Pruning-Methods_o7ieen_atkmmq.jpg
Jonathan Shewchuk: Nice intuitive use cases for various traversals.