Rooted Trees
387
To carry out a preorder or a postorder listing, follow the same trail alongside the tree.
For a preorder listing, however, record the label on the vertex the first time the vertex is
encountered. For a postorder listing, record the label on the vertex the last time it is passed,
as the traversal moves up to the vertex's parent. Examples of these listings of the labels
are shown in Figure 6.51. Notice that for preorder and postorder listing, the labels at the
vertices are not listed in alphabetical order.
Postorder
Preorder
milk
milk
"c"soda
"
"soda
cereal•
8
7,
ceree aa 66 l
milkl
8
banana"
gape
b\
grape
3
5
6
banana
1 /,
orange
water
3
/
orange
water
fruit 2
fruit 5
banana
milk
fruit
cereal
grape
banana
cereal
grape
orange
fruit
water
soda
soda
orange
milk
water
Figure 6.51 Tree traversals.
6.12.4 Application: Decision Trees
To find a lower bound for the complexity of a class of algorithms, it is necessary to find
a model for all possible algorithms of the class. The lower bound for sorting algorithms
based on using a comparison of two elements as the fundamental operation can be found
by using a decision tree model. A decision tree is a rooted binary tree with labeled vertices
and edges.
Each step of a comparison-based sorting algorithm involves the comparison of two
distinct elements (if two elements were the same, we would be reduced to a smaller case)
using the linear order on the set of elements being sorted. These comparisons are used to
label the vertices of the tree. The label a : b at a vertex indicates that a and b are to be
compared. The left edge from a vertex represents what is known about the order of the
elements when a < b is true. The right edge represents what is known about the order of
the elements when b < a is true. Each leaf represents the fact that the questions used to
get to that leaf have completely identified the order among the elements of the input. The
discovered order is then presented in a box. Figure 6.52 shows a tree that represents one
way to sort three elements.
387
To carry out a preorder or a postorder listing, follow the same trail alongside the tree.
For a preorder listing, however, record the label on the vertex the first time the vertex is
encountered. For a postorder listing, record the label on the vertex the last time it is passed,
as the traversal moves up to the vertex's parent. Examples of these listings of the labels
are shown in Figure 6.51. Notice that for preorder and postorder listing, the labels at the
vertices are not listed in alphabetical order.
Postorder
Preorder
milk
milk
"c"soda
"
"soda
cereal•
8
7,
ceree aa 66 l
milkl
8
banana"
gape
b\
grape
3
5
6
banana
1 /,
orange
water
3
/
orange
water
fruit 2
fruit 5
banana
milk
fruit
cereal
grape
banana
cereal
grape
orange
fruit
water
soda
soda
orange
milk
water
Figure 6.51 Tree traversals.
6.12.4 Application: Decision Trees
To find a lower bound for the complexity of a class of algorithms, it is necessary to find
a model for all possible algorithms of the class. The lower bound for sorting algorithms
based on using a comparison of two elements as the fundamental operation can be found
by using a decision tree model. A decision tree is a rooted binary tree with labeled vertices
and edges.
Each step of a comparison-based sorting algorithm involves the comparison of two
distinct elements (if two elements were the same, we would be reduced to a smaller case)
using the linear order on the set of elements being sorted. These comparisons are used to
label the vertices of the tree. The label a : b at a vertex indicates that a and b are to be
compared. The left edge from a vertex represents what is known about the order of the
elements when a < b is true. The right edge represents what is known about the order of
the elements when b < a is true. Each leaf represents the fact that the questions used to
get to that leaf have completely identified the order among the elements of the input. The
discovered order is then presented in a box. Figure 6.52 shows a tree that represents one
way to sort three elements.