Java Reference
In-Depth Information
• Right sibling(r) = r + 1 if r is odd and r + 1 < n.
5.4
Binary Search Trees
Section 4.4 presented the dictionary ADT, along with dictionary implementations
based on sorted and unsorted lists. When implementing the dictionary with an
unsorted list, inserting a new record into the dictionary can be performed quickly by
putting it at the end of the list. However, searching an unsorted list for a particular
record requires (n) time in the average case. For a large database, this is probably
much too slow. Alternatively, the records can be stored in a sorted list. If the list
is implemented using a linked list, then no speedup to the search operation will
result from storing the records in sorted order. On the other hand, if we use a sorted
array-based list to implement the dictionary, then binary search can be used to find
a record in only (log n) time. However, insertion will now require (n) time on
average because, once the proper location for the new record in the sorted list has
been found, many records might be shifted to make room for the new record.
Is there some way to organize a collection of records so that inserting records
and searching for records can both be done quickly? This section presents the
binary search tree (BST), which allows an improved solution to this problem.
A BST is a binary tree that conforms to the following condition, known as
the Binary Search Tree Property: All nodes stored in the left subtree of a node
whose key value is K have key values less than K. All nodes stored in the right
subtree of a node whose key value is K have key values greater than or equal to K.
Figure 5.13 shows two BSTs for a collection of values. One consequence of the
Binary Search Tree Property is that if the BST nodes are printed using an inorder
traversal (see Section 5.2), the resulting enumeration will be in sorted order from
lowest to highest.
Figure 5.14 shows a class declaration for the BST that implements the dictio-
nary ADT. The public member functions include those required by the dictionary
ADT, along with a constructor and destructor. Recall from the discussion in Sec-
tion 4.4 that there are various ways to deal with keys and comparing records (three
approaches being key/value pairs, a special comparison method such as using the
Comparator
class, and passing in a comparator function). Our BST implementa-
tion will handle comparison by explicitly storing a key separate from the data value
at each node of the tree.
To find a record with key value K in a BST, begin at the root. If the root stores
a record with key value K, then the search is over. If not, then we must search
deeper in the tree. What makes the BST efficient during search is that we need
search only one of the node's two subtrees. If K is less than the root node's key
value, we search only the left subtree. If K is greater than the root node's key
value, we search only the right subtree. This process continues until a record with
