Java Reference
In-Depth Information
10.
private
NodePair findNode(T entry)
{
NodePair result =
new
NodePair();
boolean
found =
false
;
BinaryNodeInterface<T> currentNode = getRootNode();
BinaryNodeInterface<T> parentNode =
null
;
while
(!found && (currentNode !=
null
) )
{
T currentEntry = currentNode.getData();
int
comparison = entry.compareTo(currentEntry);
if
(comparison < 0)
{
parentNode = currentNode;
currentNode = currentNode.getLeftChild();
}
else if
(comparison > 0)
{
parentNode = currentNode;
currentNode = currentNode.getRightChild();
}
else
// comparison == 0
found =
true
;
}
// end while
if
(found)
result =
new
NodePair(currentNode, parentNode);
// found entry is currentNode.getData()
return
result;
}
// end findNode
11.
Since the method
contains
invokes
getEntry
, the efficiency of these methods is the same. So if the tree's height
is as small as possible, the efficiency is O(log
n
). If the tree's height is as large as possible, the efficiency is O(
n
).
12.
O(1).
13.
public int
getSize()
{
return
bst.getNumberOfNodes();
}
// end getSize
public boolean
isEmpty()
{
return
bst.isEmpty();
}
// end isEmpty
public boolean
contains(K key)
{
Entry<K, V> findEntry =
new
Entry<K, V>(key,
null
);
return
bst.contains(findEntry);
}
// end contains
