Transcript CSC401: Analysis of Algorithms

CSC401 – Analysis of Algorithms
Lecture Notes 4
Trees and Priority Queues
Objectives:
General Trees and ADT
Properties of Trees
Tree Traversals
Binary Trees
Priority Queues and ADT
The Tree Structure
In computer science, a
tree is an abstract model
of a hierarchical structure
A tree consists of nodes
with a parent-child
relation
Applications:
US
– Organization charts
– File systems
Europe
– Programming
environments
Computers”R”Us
Sales
Manufacturing
International
Asia
Laptops
R&D
Desktops
Canada
2
Tree Terminology
Root: node without parent (A)
Internal node: node with at least
one child (A, B, C, F)
External node (a.k.a. leaf ): node
without children (E, I, J, K, G, H,
D)
Ancestors of a node: parent,
grandparent, grand-grandparent,
etc.
Depth of a node: number of
ancestors
Height of a tree: maximum depth E
of any node (3)
Descendant of a node: child,
grandchild, grand-grandchild, etc.
Subtree: tree consisting
of a node and its
descendants
A
B
C
F
I
J
G
K
D
H
subtree
3
Tree ADT
We use positions to
abstract nodes
Generic methods:
–
–
–
–
integer size()
boolean isEmpty()
objectIterator elements()
positionIterator positions()
Accessor methods:
– position root()
– position parent(p)
– positionIterator
children(p)
Query methods:
– boolean isInternal(p)
– boolean isExternal(p)
– boolean isRoot(p)
Update methods:
– swapElements(p, q)
– object replaceElement(p, o)
Additional update methods
may be defined by data
structures implementing the
Tree ADT
4
Depth and Height
Depth -- the depth of v is
the number of ancestors,
excluding v itself
– the depth of the root is 0
– the depth of v other than
the root is one plus the
depth of its parent
– time efficiency is O(1+d)
Height -- the height of a
subtree v is the maximum
depth of its external nodes
– the height of an external
node is 0
– the height of an internal
node v is one plus the
maximum height of its
children
– time efficiency is O(n)
Algorithm depth(T,v)
if T.isRoot(v) then
return 0
else return
1+depth(T, T.parent(v))
Algorithm height(T,v)
if T.isExternal(v) then
return 0
else
h=0;
for each wT.children(v) do
h=max(h, height(T,w))
return 1+h
5
Preorder Traversal
A traversal visits the nodes of a
tree in a systematic manner
In a preorder traversal, a node
is visited before its descendants
The running time is O(n)
Application: print a structured
document
1
Algorithm preOrder(v)
visit(v)
for each child w of v
preorder (w)
Make Money Fast!
2
5
1. Motivations
9
2. Methods
3
4
1.1 Greed
1.2 Avidity
6
2.1 Stock
Fraud
7
2.2 Ponzi
Scheme
References
8
2.3 Bank
Robbery
6
Postorder Traversal
In a postorder traversal, a
node is visited after its
descendants
The running time is O(n)
Application: compute space
used by files in a directory and
its subdirectories
9
Algorithm postOrder(v)
for each child w of v
postOrder (w)
visit(v)
cs16/
3
8
7
homeworks/
todo.txt
1K
programs/
1
2
h1c.doc
3K
h1nc.doc
2K
4
DDR.java
10K
5
Stocks.java
25K
6
Robot.java
20K
7
Binary Tree
A binary tree is a tree with
the following properties:
Applications:
– arithmetic
expressions
– decision processes
– searching
– Each internal node has two
children
– The children of a node are an
ordered pair
We call the children of an
internal node left child and
right child
Alternative recursive
definition: a binary tree is
either
– a tree consisting of a single
node, or
– a tree whose root has an
ordered pair of children, each
of which is a binary tree
A
B
C
D
E
H
F
G
I
8
Binary Tree Examples
Arithmetic expression
binary tree
– internal nodes: operators
– external nodes: operands
– Example: arithmetic
expression tree for the
expression (2(a-1)+(3  b))
+


-
2
a
Decision tree
3
b
1
– internal nodes: questions with yes/no answer
– external nodes: decisions
– Example: dining decision
Want a fast meal?
No
Yes
How about coffee?
Yes
Starbucks
No
Spike’s
On expense account?
Yes
Al Forno
No
Café Paragon
9
Properties of Binary Trees
Notation
n number of nodes
e number of external
nodes
i number of internal
nodes
h height
Properties:
– e=i+1
– n = 2e - 1
– hi
– h  (n - 1)/2
– h+1  e  2h
– h  log2 e
– h  log2 (n + 1) - 1
10
BinaryTree ADT
The BinaryTree ADT extends the Tree
ADT, i.e., it inherits all the methods of
the Tree ADT
Additional methods:
– position leftChild(p)
– position rightChild(p)
– position sibling(p)
Update methods may be defined by data
structures implementing the BinaryTree
ADT
11
Inorder Traversal
In an inorder traversal a
node is visited after its left
subtree and before its
right subtree
Time efficiency is O(n)
Application: draw a binary
tree
Algorithm inOrder(v)
if isInternal (v)
inOrder (leftChild (v))
visit(v)
if isInternal (v)
inOrder (rightChild (v))
– x(v) = inorder rank of v
– y(v) = depth of v
6
2
8
1
4
3
7
9
5
12
Print Arithmetic Expressions
Specialization of an inorder
traversal
– print operand or operator
when visiting node
– print “(“ before traversing
left subtree
– print “)“ after traversing
right subtree
+


-
2
a
3
b
Algorithm printExpression(v)
if isInternal (v)
print(“(’’)
inOrder (leftChild (v))
print(v.element ())
if isInternal (v)
inOrder (rightChild (v))
print (“)’’)
((2  (a - 1)) + (3  b))
1
13
Evaluate Arithmetic Expressions
Specialization of a
postorder traversal
– recursive method
returning the value of a
subtree
– when visiting an internal
node, combine the
values of the subtrees
Algorithm evalExpr(v)
if isExternal (v)
return v.element ()
else
x  evalExpr(leftChild (v))
y  evalExpr(rightChild (v))
  operator stored at v
return x  y
+


-
2
5
3
1
2
14
Euler Tour Traversal
Generic traversal of a binary tree
Includes a special cases the preorder, postorder and inorder
traversals
Walk around the tree and visit each node three times:
– on the left (preorder)
– from below (inorder)
– on the right (postorder)
+
L
2


R
B
5
3
2
1
15
Template Method Pattern
Generic algorithm that
public abstract class EulerTour {
can be specialized by
protected BinaryTree tree;
redefining certain steps
protected void visitExternal(Position p, Result r) { }
Implemented by means
protected void visitLeft(Position p, Result r) { }
of an abstract Java class
protected void visitBelow(Position p, Result r) { }
Visit methods that can
protected void visitRight(Position p, Result r) { }
be redefined by
protected Object eulerTour(Position p) {
subclasses
Result r = new Result();
Template method eulerTour
if tree.isExternal(p) { visitExternal(p, r); }
– Recursively called on
the left and right
children
– A Result object with
fields leftResult, rightResult
and finalResult keeps track
of the output of the
recursive calls to eulerTour
else {
visitLeft(p, r);
r.leftResult = eulerTour(tree.leftChild(p));
visitBelow(p, r);
r.rightResult = eulerTour(tree.rightChild(p));
visitRight(p, r);
return r.finalResult;
}…
16
Specializations of EulerTour
We show how to
specialize class
EulerTour to evaluate
an arithmetic
expression
Assumptions
public class EvaluateExpression
extends EulerTour {
protected void visitExternal(Position p, Result r) {
r.finalResult = (Integer) p.element();
}
protected void visitRight(Position p, Result r) {
Operator op = (Operator) p.element();
r.finalResult = op.operation(
(Integer) r.leftResult,
(Integer) r.rightResult
);
}
– External nodes store
Integer objects
– Internal nodes store
Operator objects
supporting method
operation (Integer, Integer)
…
}
17
Data Structure for Trees
A node is represented
by an object storing

– Element
– Parent node
– Sequence of children
nodes
B
Node objects
implement the Position
ADT


A
D
F
B
D
A
C
F
E

C

E
18
Data Structure for Binary Trees
A node is represented
by an object storing
–
–
–
–
Element
Parent node
Left child node
Right child node

B
Node objects implement
the Position ADT


B
A
A
D
D

C
E

C


E
19
Vector-Based Binary Tree
Level numbering of nodes of T: p(v)
– if v is the root of T, p(v)=1
– if v is the left child of u, p(v)=2p(u)
– if v is the right child of u, p(v)=2p(u)+1
Vector S storing the nodes of T by putting
the root at the second position and
following the above level numbering
Properties: Let n be the number of nodes of T,
N be the size of the vector S, and PM be the
maximum value of p(v) over all the nodes of T
– N=PM+1
– N=2^((n+1)/2)
20
Java Implementation
Tree interface
BinaryTree interface
extending Tree
Classes implementing
Tree and BinaryTree
and providing
expandExternal(v)
v
A
A

– Constructors
– Update methods
– Print methods
Examples of updates
for binary trees
B
– expandExternal(v)
– removeAboveExternal(w)
v

removeAboveExternal(w)
A
B
C
w
21
Trees in JDSL
JDSL is the Library of Data
Structures in Java
Tree interfaces in JDSL
–
–
–
–
InspectableBinaryTree
InspectableTree
BinaryTree
Tree
Inspectable versions of the
interfaces do not have
update methods
Tree classes in JDSL
– NodeBinaryTree
– NodeTree
JDSL was developed at
Brown’s Center for
Geometric Computing
See the JDSL
documentation and
tutorials at http://jdsl.org
InspectableTree
Tree
InspectableBinaryTree
BinaryTree
22
Priority Queue ADT
A priority queue stores
a collection of items
An item is a pair
(key, element)
Main methods of the
Priority Queue ADT
– insertItem(k, o) -inserts an item with key
k and element o
– removeMin() -- removes
the item with smallest
key and returns its
element
Additional methods
– minKey(k, o) -- returns,
but does not remove, the
smallest key of an item
– minElement() -- returns,
but does not remove, the
element of an item with
smallest key
– size(), isEmpty()
Applications:
– Standby flyers
– Auctions
– Stock market
23
Total Order Relation
Keys in a priority
queue can be
arbitrary objects
on which an
order is defined
Two distinct
items in a
priority queue
can have the
same key
Mathematical concept
of total order relation

– Reflexive property:
xx
– Antisymmetric
property:
xy  yx x=y
– Transitive property:
xy  yz xz
24
Comparator ADT
A comparator
encapsulates the action of
comparing two objects
according to a given total
order relation
A generic priority queue
uses an auxiliary
comparator
The comparator is
external to the keys being
compared
When the priority queue
needs to compare two
keys, it uses its
comparator
Methods of the
Comparator ADT, all
with Boolean return
type
– isLessThan(x, y)
– isLessThanOrEqualTo(x,
y)
– isEqualTo(x,y)
– isGreaterThan(x, y)
– isGreaterThanOrEqualTo
(x,y)
– isComparable(x)
25
Sorting with a Priority Queue
We can use a priority
queue to sort a set of
comparable elements
– Insert the elements
one by one with a
series of insertItem(e,
e) operations
– Remove the elements
in sorted order with a
series of removeMin()
operations
The running time of
this sorting method
depends on the
priority queue
implementation
Algorithm PQ-Sort(S, C)
Input sequence S, comparator C
for the elements of S
Output sequence S sorted in
increasing order according to C
P  priority queue with
comparator C
while S.isEmpty ()
e  S.remove (S. first ())
P.insertItem(e, e)
while P.isEmpty()
e  P.removeMin()
S.insertLast(e)
26
Sequence-based Priority Queue
Implementation with
an unsorted sequence
– Store the items of the
priority queue in a listbased sequence, in
arbitrary order
Performance:
– insertItem takes O(1)
time since we can insert
the item at the beginning
or end of the sequence
– removeMin, minKey and
minElement take O(n)
time since we have to
traverse the entire
sequence to find the
smallest key
Implementation with a
sorted sequence
– Store the items of the
priority queue in a
sequence, sorted by
key
Performance:
– insertItem takes O(n)
time since we have to
find the place where to
insert the item
– removeMin, minKey and
minElement take O(1)
time since the smallest
key is at the beginning
of the sequence
27
Selection-Sort
Selection-sort is the variation of PQ-sort
where the priority queue is implemented with
an unsorted sequence
Running time of Selection-sort:
– Inserting the elements into the priority queue with
n insertItem operations takes O(n) time
– Removing the elements in sorted order from the
priority queue with n removeMin operations takes
time proportional to
1 + 2 + …+ n
Selection-sort runs in O(n2) time
28
Insertion-Sort
Insertion-sort is the variation of PQ-sort
where the priority queue is implemented
with a sorted sequence
Running time of Insertion-sort:
–
Inserting the elements into the priority queue with
n insertItem operations takes time proportional to
1 + 2 + …+ n
–
Removing the elements in sorted order from the
priority queue with a series of n removeMin
operations takes O(n) time
Insertion-sort runs in O(n2) time
29
In-place Insertion-sort
Instead of using an
external data structure,
we can implement
selection-sort and
insertion-sort in-place
A portion of the input
sequence itself serves as
the priority queue
For in-place insertion-sort
5
4
2
3
1
5
4
2
3
1
4
5
2
3
1
2
4
5
3
1
– We keep sorted the initial
portion of the sequence
– We can use
swapElements instead of
modifying the sequence
2
3
4
5
1
1
2
3
4
5
1
2
3
4
5
30