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

The tree built so far is shown in Figure 8-5 .

mac

era tee

ode

Figure 8-5. BST after adding mac, tee, ode, era

ria is next and is greater than mac , so we go right; it is smaller than tee , so we go left; it is
greater than ode , so it is inserted as the right subtree of ode .
Following this procedure, lea is inserted as the right subtree of era , and vim is inserted as the right subtree of tee ,
giving the final tree shown in Figure 8-6 .

•

mac

era tee

lea ode vim

ria

Figure 8-6. BST after adding all seven words

Note that the tree obtained is quite different from the optimal search tree. The number of comparisons required
to find a given word has also changed. For instance, ria now requires four comparisons; it required three previously,
and lea now requires three as opposed to two previously. But it's not all bad news; era now requires two as compared
to three previously.
It can be proved that if the words come in random order, then the average search time for a given word is
approximately 1.4 times the average for the optimal search tree, that is, 1.4log 2 n , for a tree of n nodes.
But what about the worst case? If the words come in alphabetical order, then the tree built will be that shown in
Figure 8-7 .

era

lea

mac

ode

ria

tee

vim

Figure 8-7. A degenerate tree