Java Reference
In-Depth Information
Efficiency of Binary Search Trees
When searching a tree that is as short as possible (all paths from root to a leaf differ by
at most one node), the search method
isInSubtree
, and hence also the method
con-
tains
, is about as efficient as the binary search on a sorted array (Display 11.6). This
should not be a surprise since the two algorithms are in fact very similar. In big-
O
notation, the worst-case running time is
O
(log
n
), where
n
is the number of nodes in
the tree. That means that searching a short, fat binary tree is very efficient. To obtain
this efficiency, the tree does not need to be as short as possible so long as it comes close
to being as short as possible. As the tree becomes less short and fat and more tall and
thin, the efficiency falls off until, in the extreme case, the efficiency is the same as that
of searching a linked list with the same number of nodes.
Maintaining a tree so that it remains short and fat as nodes are added is a topic that
is beyond the scope of what we have room for in this topic. (The technical term for
short and fat is
balanced
.) We will only note that if the numbers that are stored in the
tree arrive in random order, then with very high probability the tree will be short and
fat enough to realize the efficiency discussed in the previous paragraph.
Self-Test Exercises
25. Suppose that the code for the method
showElementsInSubtree
in Display 15.40
were changed so that
showElementsInSubtree(subTreeRoot.leftLink);
System.out.print(subTreeRoot.data + " ");
showElementsInSubtree(subTreeRoot.rightLink);
were changed to
System.out.print(subTreeRoot.data + " ");
showElementsInSubtree(subTreeRoot.leftLink);
showElementsInSubtree(subTreeRoot.rightLink);
Will the numbers still be output in ascending order?
26. How can you change the code for the method
showElementsInSubtree
in Dis-
play 15.40 so that the numbers are output from largest to smallest instead of
from smallest to largest?
