476
Graphs and Trees
including those at WWW, use the ASCII encoding scheme for converting characters
into binary form, under which each character requires 1 byte (8 bits) of storage. Because each different part number consists of 9 characters, the WWW parts data file
is approximately 9 × 5 × 10
8 bytes, or 4.5 Gb.
Question: How can you compress this data file so that it takes less storage space?
One answer to this question involves working with binary tree structures. A tree
is a visual representation of data items and the connections between some of these
items. It is a special case of a more general structure called a graph. Graphs or
trees can be used to represent a surprising number of real-world situations—
organization charts, road maps, transportation and communications networks,
and so forth. Later we will see other uses of graphs and trees to represent logic
networks, finite-state machines, and formal-language derivations.
Graph theory is an extensive topic. Sections 6.1 and 6.2 present some of the
considerable terminology connected with graphs and trees and some elementary
results about these structures. To represent a graph or a tree in computer memory,
data must be arranged in a way that preserves all the information contained in the
visual representation. Several approaches to representing graphs and trees within
a computer are discussed.
Decision trees are graphical representations of the activities of certain types
of algorithms. In Section 6.3, decision trees are presented and used to find lower
bounds on the worst-case behavior of searching and sorting algorithms. In Section 6.4, an algorithm is given for constructing binary trees that allow for data
compression of large files.
S e c t i o n 6 . 1 Gr aphs and Their represenTaTions
Definitions of a Graph
One way to while away the hours on an airplane trip is to look at the literature in
the seat pockets. This material almost always includes a map showing the routes
of the airline you are flying, such as the one in Figure 6.1. All this route information could be expressed in paragraph form; for example, there is a direct route between Chicago and Nashville but not between St. Louis and Nashville. However,
the paragraph would be rather long and involved, and we would not be able to
assimilate the information as quickly and clearly as we can from the map. There
are many cases where “a picture is worth a thousand words.”
Chicago
Nashville
Miami
St. Louis
Dallas
Albuquerque
Phoenix
Denver
Los Angeles
San Francisco
Figure 6.1
Graphs and Trees
including those at WWW, use the ASCII encoding scheme for converting characters
into binary form, under which each character requires 1 byte (8 bits) of storage. Because each different part number consists of 9 characters, the WWW parts data file
is approximately 9 × 5 × 10
8 bytes, or 4.5 Gb.
Question: How can you compress this data file so that it takes less storage space?
One answer to this question involves working with binary tree structures. A tree
is a visual representation of data items and the connections between some of these
items. It is a special case of a more general structure called a graph. Graphs or
trees can be used to represent a surprising number of real-world situations—
organization charts, road maps, transportation and communications networks,
and so forth. Later we will see other uses of graphs and trees to represent logic
networks, finite-state machines, and formal-language derivations.
Graph theory is an extensive topic. Sections 6.1 and 6.2 present some of the
considerable terminology connected with graphs and trees and some elementary
results about these structures. To represent a graph or a tree in computer memory,
data must be arranged in a way that preserves all the information contained in the
visual representation. Several approaches to representing graphs and trees within
a computer are discussed.
Decision trees are graphical representations of the activities of certain types
of algorithms. In Section 6.3, decision trees are presented and used to find lower
bounds on the worst-case behavior of searching and sorting algorithms. In Section 6.4, an algorithm is given for constructing binary trees that allow for data
compression of large files.
S e c t i o n 6 . 1 Gr aphs and Their represenTaTions
Definitions of a Graph
One way to while away the hours on an airplane trip is to look at the literature in
the seat pockets. This material almost always includes a map showing the routes
of the airline you are flying, such as the one in Figure 6.1. All this route information could be expressed in paragraph form; for example, there is a direct route between Chicago and Nashville but not between St. Louis and Nashville. However,
the paragraph would be rather long and involved, and we would not be able to
assimilate the information as quickly and clearly as we can from the map. There
are many cases where “a picture is worth a thousand words.”
Chicago
Nashville
Miami
St. Louis
Dallas
Albuquerque
Phoenix
Denver
Los Angeles
San Francisco
Figure 6.1