352
Relations, Functions, and Matrices
precedence relation with alphabetical characters (the collating sequence must be determined). If we
list words alphabetically, it is a fairly quick procedure to decide whether a word currently being processed is new, but to fit the new word into place, all successive words must be moved one unit down
the line. If the words are listed in the order in which they are processed, new words are simply tacked
onto the end and no rearranging is necessary, but each word being processed has to be compared with
each member of the list to determine if it is new. Thus, both logical linear lists have disadvantages.
We describe a structure called a binary search tree; using this structure, a search process called a
binary tree search can usually determine quickly whether a word is new and, if it is, no juggling is required to fit it into place, thus eliminating the disadvantages of both linear list structures described earlier.
Suppose we want to process the phrase “when in the course of human events.” The first word in the text
is used to label the first node of a graph. Once a node is labeled, it drops down a left and right arc, putting
two unlabeled nodes below the one just labeled.
when
when
When the next word in the text is processed, it is compared with the first node. When the word being processed alphabetically precedes the label of a node, the left arc is taken; when the word follows the label
alphabetically, the right arc is taken. The word becomes the label of the first unlabeled node it reaches.
(If the word equals a node label, it is a duplicate, so the next word in the text is processed.) This procedure
continues for the entire text. Thus,
when
in
then
when
in
the
then
when
in
course
the
Relations, Functions, and Matrices
precedence relation with alphabetical characters (the collating sequence must be determined). If we
list words alphabetically, it is a fairly quick procedure to decide whether a word currently being processed is new, but to fit the new word into place, all successive words must be moved one unit down
the line. If the words are listed in the order in which they are processed, new words are simply tacked
onto the end and no rearranging is necessary, but each word being processed has to be compared with
each member of the list to determine if it is new. Thus, both logical linear lists have disadvantages.
We describe a structure called a binary search tree; using this structure, a search process called a
binary tree search can usually determine quickly whether a word is new and, if it is, no juggling is required to fit it into place, thus eliminating the disadvantages of both linear list structures described earlier.
Suppose we want to process the phrase “when in the course of human events.” The first word in the text
is used to label the first node of a graph. Once a node is labeled, it drops down a left and right arc, putting
two unlabeled nodes below the one just labeled.
when
when
When the next word in the text is processed, it is compared with the first node. When the word being processed alphabetically precedes the label of a node, the left arc is taken; when the word follows the label
alphabetically, the right arc is taken. The word becomes the label of the first unlabeled node it reaches.
(If the word equals a node label, it is a duplicate, so the next word in the text is processed.) This procedure
continues for the entire text. Thus,
when
in
then
when
in
the
then
when
in
course
the