Transcript Chapter 5-3 - Computer Science

Graphs and Trees
Mathematical Structures
for Computer Science
Chapter 5.3
Copyright © 2006 W.H. Freeman & Co.
MSCS Slides
Graphs and Trees
Decision Trees



Section 5.3
DEFINITION: DECISION TREE A decision tree is a tree in which
the internal nodes represent actions, the arcs represent outcomes of an
action, and the leaves represent final outcomes.
The following figure represents the various possibilities for five coin
tosses under the constraint that two heads in a row do not occur.
Each internal node of the tree represents an action (a coin toss), and the
arcs to the children of internal nodes represent the outcomes of that
action (heads or tails). The leaves of the tree represent the final
outcomes, that is, the different ways that five tosses could occur.
Decision Trees
1
Searching



Decision trees aren’t data structures; that is, tree nodes
don’t contain data, they represent actions. Edges
represent the outcomes of actions.
Decision trees can be used to analyze a variety of
computer algorithms; for example, search and sort
algorithms that are performed on lists.
Searching a list is a common activity



Section 5.3
List items are identified by keys, each of which may have
additional data associated with it.
When given a specific key, the objective is to find it in the
list or determine that it isn’t present.
L[i] is an element in the list. We can think of the list
being stored in an array, but there are also other
representations.
Decision Trees
2
Searching – Sequential Search

Sequential search for x on list L with n elements
proceeds by comparing x to each element of the list in
turn.





Section 5.3
If x = L[i] the element is found
If x  L[i] check next element in the list (L[i+1])
Repeat until x is found or until there are no more
elements in the list.
Figure 5.52 (page 453) shows a binary tree
representation of the search process. Each internal node
in the list represents one comparison, each leaf node
represents a possible outcome of the search.
Best case performance: one comparison; worst case: n
comparisons; average case: n/2 if all are equally likely.
Decision Trees
3
Searching – Binary Search


Sequential search is based on an unsorted list.
Binary search assumes the list is sorted.



Advantages of binary search compared to sequential
search: it requires fewer comparisons


Section 5.3
The sorted elements are stored in an array, or some
other linear data structure
A binary decision tree represents the sorting process, it
does not mean that the list is stored in a binary tree.
Algorithm efficiency is measured in terms of the main
operation; here, it’s the compare/decide operation
Disadvantage of binary search: it requires that the list
be sorted. If list elements change frequently there’s
extra work involved to keep the list sorted.
Decision Trees
4
Searching – Binary Search

The binary search algorithm on a sorted list works as follows: examine
the middle node in the list. There are three possibilities:






Section 5.3
x = L[i]: algorithm terminates, x has been found (not actually shown on the decision tree below)
x < L[i]: algorithm proceeds to the left half of the list
x > L[i]: algorithm proceeds to the right half of the list
If x is not found follow either
left or right branch, examine
the middle node in that half
of the list.
Repeat process until either
x is found or until you can
determine that x is not in
the array.
Leaf nodes represent an
unsuccessful search.
Decision Trees
5
Lower Bounds on Searching




The number of nodes at each level in a full binary tree follows a
geometric progression: 20 nodes at level 0, 21 nodes at level 1,
22 nodes at level 2, and so on.
1 + 2 + 22 + 23 ... 2d = 2d + 1  1
Any binary tree of depth d has at most 2d + 1  1 nodes.
Any binary tree with m nodes has depth  log2 m.
THEOREM ON THE LOWER BOUND FOR SEARCHING Any
algorithm that solves the search problem for an n-element list by
comparing the target element x to the list items must do at least
└log2 n┘ + 1 comparisons in the worst case.

Section 5.3
Since binary search does no more work than this required
minimum amount, binary search is an optimal algorithm in its
worst-case behavior.
Decision Trees
6
Example
Here’s a list with eight elements:
L[1] L[2] L[3] L[4] L[5] L[6] L[7] L[8]
-80, -17, 10, 25, 31, 48, 89, 101
n = 8, └log2 n┘ + 1 = 3 + 1 = 4
So 4 is the maximum number of compares
needed to search for an element in an 8 element
list.
Search tree for key = 89
Nodes examined are L[4], L[6], L[7]
Found at L[7]
Number of comparisons: 3
Search tree for key = 1
Nodes examined: L[4], L[2], L[3]
Not found: -17(L[2]) < 1 < 10 (L[3])
Number of comparisons: 3
Section 5.3
Decision Trees
7
Binary Search Tree




Section 5.3
The binary search algorithm on a list requires that data
already be sorted.
Arbitrary data can be organized into a structure called a
binary search tree, which can then be searched using a
different algorithm called, binary tree search.
To build a binary search tree, the first item of data is made
the root of the tree.
Successive items are inserted by comparing them to
existing nodes, beginning with the root. If the item is less
than a node, the next node tested is the left child; otherwise
it is the right child. When no child node exists, the new
item becomes the child.
Decision Trees
8
Binary Search Tree Example



Section 5.3
The data items 5, 8, 2, 12, 10, 14, 9 are to be organized into a binary
search tree.
A binary search tree, by the way it is constructed, has the property
that the value at each node is greater than all values in its left subtree
(the subtree rooted at its left child) and less than all values in its right
subtree.
A binary tree search compares item x with a succession of nodes,
beginning with the root. If x equals the node item, the algorithm
terminates; if x is less than the item, the left child is checked next; if x
is greater than the item, the right child is checked next. If no child
exists, the algorithm terminates because x is not on the list.
Decision Trees
9
Sorting




Section 5.3
Decision trees can also model algorithms that sort a list of items
by a sequence of comparisons between two items from the list.
The internal nodes of such a decision tree are labeled L[i]:L[j ]
to indicate a comparison of list item i to list item j.
The outcome of such a comparison is either L[i] < L[j ]
or L[i] > L[j ]. If L[i] < L[j ], the algorithm proceeds to the
comparison indicated at the left child of this node; if L[i] > L[j ],
the algorithm proceeds to the right child.
If no child exists, the algorithm terminates because the sorted
order has been determined.
Decision Trees
10
Sorting Example


Section 5.3
The figure below shows the decision tree for a sorting algorithm acting
on a list of three elements; e.g., the list 3, 2, 1 or 2, 1, 3
Leaf nodes represent the final sorted list, or else inconsistent results –
denoted by x below. For example in the left subtree the series of
comparisons L[1] < L[2], L[2] < L[3], L[1] > L[3] is not possible
because by transitivity L[1] < L[3]. It cannot also be > L[3].
Decision Trees
11
Lower Bound on Sorting




A decision tree argument can also be used to establish a lower
bound on the worst-case number of comparisons required to sort a
list of n elements.
The leaves of such a tree represent the final outcomes, that is, the
various ordered arrangements of the n items.
There are n! such arrangements, so if p is the number of leaves in
the decision tree, then p ≤ n!. The worst case will equal the depth of
the tree.
But it is also true that if the tree has depth d, then p ≤ 2d:
d = log2 p  log2 n!

THEOREM ON THE LOWER BOUND FOR SORTING Any
algorithm that sorts an n-element list by comparing pairs of items
from the list must do at least ┌log2 n!┐ comparisons in the worst
case.

Section 5.3
For n = 3, n ! = 6, 22 < 6 < 23 so worst case sorting requires at most 8
Decision Trees
12