Discrete Mathematics for Computer Science

382 CHAPTER^6 Graph Theory

6.12.2 Binary Search Trees

In addition to directing the edges away from the root in a binary tree, we can assign values

to the vertices in a special way. This new kind of tree is called a binary search tree. A typical

application of a binary search tree includes searching an ordered set for an element.

Definition 4. Let X be a linearly ordered set. A binary tree T = (V, E) with vertices

labeled by elements of X is a binary search tree if and only if:

(a) The value of the label of each vertex in the left subtree of a vertex v and not equal to v

is less than the value of the label at v.

(b) The value of the label of each vertex in the right subtree of v and not equal to v is

greater than the value of the label at v.

(c) no element of X occurs as a label of more than one vertex of T.

We have several choices for managing data when it must be stored in alphabetical

order for ease of access in applications. Certainly, the data can be kept in order in a list.

The data can also be stored as labels of the vertices of a binary search tree. If the binary

search tree can be constructed with a relatively small height, then the search algorithm will

be very efficient.

When the data stored in a binary search tree are a collection of words or names, the

ordering relation that is used to determine the location of a label is simply the familiar

dictionary ordering of words (see Example 9 in Section 3.8.2). The tree pictured in Figure

6.45 is a binary search tree with respect to the usual dictionary ordering of words.

llama

elephant/ / moose goath zebra

aardvark gnu horse

Figure 6.45 Binary search tree.

The search for a word in a set of words labeling a binary search tree can be imple-

mented with the algorithm on the facing page.

Since the labels for the vertices of the binary search tree come from a linearly ordered

set and no two vertices have the same label, each comparison of the elements sought with

the label of a vertex results in one of two outcomes: You find the element, or you restrict

the continuation of the search to a smaller subtree. Since each leaf has an empty subtree

for both its left and right subtrees, the search will terminate either by finding the element

as the label of a vertex or by exhausting the possibility of finding the element by coming

to a leaf of the tree.