Java Reference
In-Depth Information
because on each iteration it divides a range of sorted values in half, which allows you
to eliminate half of the possibilities.
A binary search tree is a structural parallel to the binary search algorithm. At
each level of the tree we divide the data in half, storing approximately half the val-
ues in the left subtree and approximately half the values in the right subtree. The
result is a highly efficient structure for storing a sorted sequence of values that can
be quickly searched for particular values. As we noted in the introduction, both the
TreeMap
and
TreeSet
classes in the Java collections framework are binary search
trees. In this section we will explore how to add values to a binary search tree and
how to search the tree. We will then explore some of the complexity issues related to
binary search trees. We'll see that binary search trees can be very efficient, although
they also can lose their efficiency if they become unbalanced. If you continue to
study computer science, you will learn various techniques which guarantee that the
tree stays balanced.
The values in a binary search tree are guaranteed to be arranged in such a way that
the values in the left subtree are all less than the root data and the values in the right
subtree are all greater than the root data. Sometimes we want to allow duplicates, in
which case we have to adopt a convention about which subtree they appear in. It
doesn't matter what convention we adopt, as long as we are consistent. For example,
we can decide that if duplicates are allowed, then they should appear in the left sub-
tree, which would lead to the following property:
root data
n
values
≤
n
values >
n
This property of nodes is known as the
binary search tree property
.
Binary Search Tree Property
Property of a node which stores data
n
if all values stored in the left subtree
are less than
n
and all values in the right subtree are greater than
n
. If dupli-
cates are allowed, then all values in the left subtree must be less than or
equal to
n
.
For a tree to qualify as a binary search tree, each node of the tree must have this
property. This is not just a property of the overall root.
Search WWH ::
Custom Search