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
contains
, is about as efficient as the binary search on a sorted array (Display 11.6).
This should not be a surprise because 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. This 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 note only 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
Display 15.40 so that the numbers are output from largest to smallest instead of
from smallest to largest?
