Section 6.3 Decision Trees
529
Although we have used decision trees, we haven’t given a formal definition of
what a decision tree is.
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.
Sometimes useful information can be obtained by using a decision tree to represent the activities of a real algorithm; actions that the algorithm performs take
place at internal nodes, the children of an internal node represent the next action
taken, based on the outcome of the previous action, and the leaves represent some
sort of circumstance that can be inferred upon algorithm termination. Note that,
unlike the trees we talked about in Section 6.2, a decision tree is not a data structure; that is, the nodes of the tree have no data values associated with them. Nor
are the algorithms we are representing necessarily acting on a tree structure. In
fact, we will use decision trees in this section to learn more about algorithms for
searching and sorting, and these algorithms act on lists of data items.
searching
A search algorithm either finds a target element x within a list of elements or determines that x is not in the list. Such an algorithm generally works by making
S e c t i o n 6 . 3 deCision Trees
We used decision trees in Chapter 4 to solve counting problems. Figure 6.51 shows
the tree used in Example 39 of Chapter 4 to represent 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.
T
H
T
T
T
H
H
T
H
T
H
H
T
H
T
T
H
T
T
T
H
H
T
T
H
T
H
T
T
T
T
H
T
T
T
H
T
T
H
T
T
H
T
H
T
H
T
T
H
T
T
T
H
T
T
T
H
H
T
T
T
H
T
T
H
T
H
T
T
H
T
T
T
T
T
T
H
T
T
T
H
T
T
T
T
T
T
H
T
T
T
H
H
T
H
T
Toss 1
Toss 2
Toss 5
Toss 4
Toss 3
Figure 6.51
529
Although we have used decision trees, we haven’t given a formal definition of
what a decision tree is.
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.
Sometimes useful information can be obtained by using a decision tree to represent the activities of a real algorithm; actions that the algorithm performs take
place at internal nodes, the children of an internal node represent the next action
taken, based on the outcome of the previous action, and the leaves represent some
sort of circumstance that can be inferred upon algorithm termination. Note that,
unlike the trees we talked about in Section 6.2, a decision tree is not a data structure; that is, the nodes of the tree have no data values associated with them. Nor
are the algorithms we are representing necessarily acting on a tree structure. In
fact, we will use decision trees in this section to learn more about algorithms for
searching and sorting, and these algorithms act on lists of data items.
searching
A search algorithm either finds a target element x within a list of elements or determines that x is not in the list. Such an algorithm generally works by making
S e c t i o n 6 . 3 deCision Trees
We used decision trees in Chapter 4 to solve counting problems. Figure 6.51 shows
the tree used in Example 39 of Chapter 4 to represent 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.
T
H
T
T
T
H
H
T
H
T
H
H
T
H
T
T
H
T
T
T
H
H
T
T
H
T
H
T
T
T
T
H
T
T
T
H
T
T
H
T
T
H
T
H
T
H
T
T
H
T
T
T
H
T
T
T
H
H
T
T
T
H
T
T
H
T
H
T
T
H
T
T
T
T
T
T
H
T
T
T
H
T
T
T
T
T
T
H
T
T
T
H
H
T
H
T
Toss 1
Toss 2
Toss 5
Toss 4
Toss 3
Figure 6.51