Java Reference
In-Depth Information
•
In a completely balanced binary tree, the subtrees of each node have exactly the same height. Such trees
must be full. Other binary trees are said to be height balanced if the subtrees of each node in the tree differ in
height by no more than 1.
•
The retrieve, add, and remove operations on a binary search tree can be as fast as O(log
n
) or as slow as
O(
n
). The performance of the search depends on the shape of the tree. When the tree is height balanced, the
operations on a binary search tree are O(log
n
).
•
The order in which you add entries to a binary search tree affects the tree's shape and hence its balance. Ran-
dom additions, as opposed to sorted ones, tend to result in a balanced tree.
•
You can implement the ADT dictionary by using a binary search tree. Although the implementation is not
difficult to write, its efficiency can suffer if additions and removals destroy the balance of the tree.
E
XERCISES
1.
Show the results of adding the following search keys to an initially empty binary search tree: 10, 5, 6, 13, 15, 8,
14, 7, 12, 4.
2.
What ordering of the search keys 10, 5, 6, 13, 15, 8, 14, 7, 12, 4 would result in the most balanced tree if they were
added to an initially empty binary search tree?
3.
Give four different orderings of the search keys 10, 5, 6, 13, 15, 8, 14, 7, 12, 4 that would result in the least
balanced tree if they were added to an initially empty binary search tree.
4.
In Chapter 7, Figure 7-10a shows the recursive computation of the term
F
6
in the Fibonacci sequence. Is this tree
height balanced?
5.
Implement the method
getEntry
iteratively.
6.
Remove
Doug
from the binary search tree pictured in Figure 25-11a. Then remove
Chad
in two different ways.
7.
Remove
Doug
from the binary search tree pictured in Figure 25-11d in two different ways.
8.
Suppose that a node with two children contains an entry
e
, as Figure 25-9a illustrates. Show that you will have a
binary search tree if you replace
e
with its inorder successor
b
and remove the node that contains
b
.
9.
Why does an inorder traversal of a binary search tree visit the nodes in sorted search-key order? Use the definition
of a binary search tree given in Segment 25.1.
10.
Consider the full binary search tree pictured in Figure 25-13a. Now imagine that you traverse the tree and save its
data in a file. If you then read the file and add the data to an initially empty binary search tree, what tree will you
get if the traversal was
a.
Preorder
b.
Inorder
c.
Level order
d.
Postorder
11.
Imagine that you traverse a binary search tree and save its data in a file. If you then read the file and add the
data to an initially empty binary search tree, what traversal should you use when writing the file so that the
new tree is
a.
As tall as possible
b.
Identical to the original binary search tree
