Java Reference
In-Depth Information
// Assertion: if nodeToRemove is a leaf, childNode is null
assert
(nodeToRemove.isLeaf() && childNode ==
null
) ||
!nodeToRemove.isLeaf();
if
(nodeToRemove == getRootNode())
setRootNode(childNode);
else
if
(parentNode.getLeftChild() == nodeToRemove)
parentNode.setLeftChild(childNode);
else
parentNode.setRightChild(childNode);
}
// end removeNode
Each of the operations
add
,
remove
, and
getEntry
requires a search that begins at the root of the
tree. When adding an entry, the search ends at a leaf if the entry is not already in the tree; otherwise,
the search can end sooner. When removing or retrieving an entry, the search ends at a leaf if it is
unsuccessful; a successful search can end sooner. So in the worst case, these searches begin at the
root and examine each node on a path that ends at a leaf. The longest path from the root to a leaf has
a length that equals the height of the tree. Thus, the maximum number of comparisons that each
operation requires is directly proportional to the height
h
of the tree. That is, the operations
add
,
remove
, and
getEntry
are O(
h
).
Recall that several different binary search trees can contain the same data. Figure 25-13 con-
tains two such trees. Figure 25-13a is the shortest binary search tree that we can form from this
data; Figure 25-13b is the tallest such tree.
The tallest tree has height
n
if it contains
n
nodes. In fact, this tree looks like a linked chain,
and searching it is like searching a linked chain. It is an O(
n
) operation. Thus,
add
,
remove
, and
getEntry
for this tree are also O(
n
) operations.
In contrast, the shortest tree is full. Searching this tree will be as efficient as possible. In
Chapter 23, we saw that the height of a full tree containing
n
nodes is log
2
(
n
+
1). Thus, in the
worst case, searching a full binary search tree is an O(log
n
) operation. So
add
,
remove
, and
getEntry
are O(log
n
) operations in this case.
Question 11
Using Big Oh notation, what is the time complexity of the method
contains
?
Question 12
Using Big Oh notation, what is the time complexity of the method
isEmpty
?
