Section 6.2 Trees and Their Representations
511
applications of Trees
Decision trees were used to solve counting problems in Chapter 4 and will be used
in Section 6.3 to help establish lower bounds on the work for certain algorithms.
Exercise 43 of Section 5.1 describes the organization of data into a binary tree
structure. By using these trees, a collection of records can be efficiently searched
to locate a particular record or to determine that a record is not in the collection.
Examples of such a search would be checking for a volume in a library, for a
patient’s medical record in a hospital, or for an individual’s credit record at the
bank. We will also look at binary tree search in Section 6.3. The derivations of
words in certain formal languages will be shown as trees in Chapter 9 (these are
the parse trees generated by a compiler while analyzing a computer program).
A family tree is usually, indeed, a tree, although if there were intermarriages,
it would be a graph but not a tree in the technical sense. (Information obtained
from a family tree is not only interesting but also useful for research in medical
genetics.) The organization chart indicating who reports to whom in a large company or other enterprise is usually a tree (Figure 6.37).
Board of
Regents
University
President
Academic Vice
President
Administrative
Vice President
Dean of Arts
and Sciences
Dean of
Business
History Chair
Computer
Science Chair
Computer Science
Faculty Member
Dean of
Engineering
Dean of
Agriculture
Figure 6.37
Folders and files on your computer are organized in a hierarchical (treelike)
structure. In Figure 6.38, the CSCI 34000 tree (folder) has been expanded to show
two subtrees; the Web Materials subtree has been expanded to show additional
folders, the Activities subtree has not been expanded.
511
applications of Trees
Decision trees were used to solve counting problems in Chapter 4 and will be used
in Section 6.3 to help establish lower bounds on the work for certain algorithms.
Exercise 43 of Section 5.1 describes the organization of data into a binary tree
structure. By using these trees, a collection of records can be efficiently searched
to locate a particular record or to determine that a record is not in the collection.
Examples of such a search would be checking for a volume in a library, for a
patient’s medical record in a hospital, or for an individual’s credit record at the
bank. We will also look at binary tree search in Section 6.3. The derivations of
words in certain formal languages will be shown as trees in Chapter 9 (these are
the parse trees generated by a compiler while analyzing a computer program).
A family tree is usually, indeed, a tree, although if there were intermarriages,
it would be a graph but not a tree in the technical sense. (Information obtained
from a family tree is not only interesting but also useful for research in medical
genetics.) The organization chart indicating who reports to whom in a large company or other enterprise is usually a tree (Figure 6.37).
Board of
Regents
University
President
Academic Vice
President
Administrative
Vice President
Dean of Arts
and Sciences
Dean of
Business
History Chair
Computer
Science Chair
Computer Science
Faculty Member
Dean of
Engineering
Dean of
Agriculture
Figure 6.37
Folders and files on your computer are organized in a hierarchical (treelike)
structure. In Figure 6.38, the CSCI 34000 tree (folder) has been expanded to show
two subtrees; the Web Materials subtree has been expanded to show additional
folders, the Activities subtree has not been expanded.