Java Reference
In-Depth Information
FIGURE 25-13
Two binary search trees that contain the same data
(a)
Jared
Brittany
Megan
Brett
Doug
Jim
Whitney
(b)
Brett
Brittany
Doug
Jared
Jim
Megan
Whitney
We do not need a full binary search tree to get O(log
n
) performance from the addition, removal,
and retrieval operations. For example, if we remove some of the leaves from a full tree, we will
not change the performance of these operations. In particular, a complete tree will also give us
O(log
n
) performance.
