Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 228

This is a special kind of binary tree. It has the property that, given any node, a word in the left subtree is “smaller,”
and a word in the right subtree is “greater” than the word at the node. (Here, smaller and greater refer to alphabetical
order.)
Such a tree is called a binary search tree (BST). It facilitates the search for a given key using a method of searching
similar to the binary search of an array.
Consider the search for ria . Starting at the root, ria is compared with ode . Since ria is greater (in alphabetical
order) than ode , we can conclude that if it is in the tree, it must be in the right subtree. It must be so since all the nodes
in the left subtree are smaller than ode .
Following the right subtree of ode , we next compare ria with tee . Since ria is smaller than tee , we follow the left
subtree of tee . We then compare ria with ria , and the search ends successfully.
But what if we were searching for fun ?
1. fun is smaller than ode , so we go left.
2. fun is smaller than lea , so we go left again.
3. fun is greater than era , so we must go right.
But since the right subtree of era is empty, we can conclude that fun is not in the tree. If it is necessary to add fun
to the tree, note that we have also found the place where it must be added. It must be added as the right subtree of era ,
as shown in Figure 8-4 .

ode

lea tee

era mac ria vim

fun

Figure 8-4. BST after adding fun

Thus, not only does the binary search tree facilitate searching, but if an item is not found, it can be easily inserted.
It combines the speed advantage of a binary search with the easy insertion of a linked list.
The tree drawn in Figure 8-3 is the optimal binary search tree for the seven given words. This means that it is the
best possible tree for these words in the sense that no shallower binary tree can be built from these words. It gives the
same number of comparisons to find a key as a binary search on a linear array containing these words.
But this is not the only possible search tree for these words. Suppose the words came in one at a time, and as each
word came in, it was added to the tree in such a way that the tree remained a binary search tree. The final tree built
will depend on the order in which the words came in. For example, suppose the words came in this order:

mac tee ode era ria lea vim

Initially the tree is empty. When mac comes in, it becomes the root of the tree.

tee comes next and is compared with mac . Since tee is greater, it is inserted as the right
subtree of mac .

•

ode comes next and is greater than mac , so we go right; ode is smaller than tee, so it inserted as
the left subtree of tee .

•

era is next and is smaller than mac , so it is inserted as the left subtree of mac .

•