Java Reference
In-Depth Information
The remedy is to define a
hashCode
method in the
Coin
class.
719
720
16.5 Binary Search Trees
A set implementation is allowed to rearrange its elements in any way it chooses so
that it can find elements quickly. Suppose a set implementation sorts its entries. Then
it can use binary search to locate elements quickly. Binary search takes O(log(n))
steps, where n is the size of the set. For example, binary search in an array of 1,000
elements is able to locate an element in about 10 steps by cutting the size of the
search interval in half in each step.
There is just one wrinkle with this idea. We can't use an array to store the elements of
a set, because insertion and removal in an array is slow; an O(n) operation.
In this section we will introduce the simplest of many treelike data structures that
computer scientists have invented to overcome that problem. Binary search trees
allow fast insertion and removal of elements, and they are specially designed for fast
searching.
A linked list is a one-dimensional data structure. Every node has a reference to a
single successor node. You can imagine that all nodes are arranged in line. In
contrast, a tree is made of nodes that have references to multiple nodes, called the
child nodes. Because the child nodes can also have children, the data structure has a
tree-like appearance. It is traditional to draw the tree upside down, like a family tree
or hierarchy chart (see
Figure 7
). In a binary tree, every node has at most two
children (called the left and right children); hence the name binary.
A binary tree consists of nodes, each of which has at most two child nodes.
Finally, a binary search tree is carefully constructed to have the following important
property:
ȗ The data values of all descendants to the left of any node are less than the data
value stored in that node, and all descendants to the right have greater data
values.