Java Reference
In-Depth Information
You can implement the method
addEntry
iteratively. We will mimic the logic of the recursive ver-
sion of
addEntry
given earlier, so you can compare the two approaches. Exercise 12 at the end of
this chapter suggests another iterative algorithm.
25.17
An iterative algorithm for adding a new entry.
The following iterative algorithm adds a new
entry to a binary search tree that is not empty:
Algorithm
addEntry(binarySearchTree, newEntry)
//
Adds a new entry to a binary search tree that is not empty.
//
Returns
null
if
newEntry
did not exist already in the tree. Otherwise, returns the
//
tree entry that matched and was replaced by
newEntry
.
result =
null
currentNode =
root node of
binarySearchTree
found =
false
while
(found
is false
)
{
if
(newEntry
matches the entry in
currentNode)
{
found =
true
result =
entry in
currentNode
Replace entry in
currentNode
with
newEntry
}
else if
(newEntry <
entry in
currentNode)
{
if
(currentNode
has a left child
)
currentNode =
left child of
currentNode
else
{
found =
true
Give
currentNode
a left child containing
newEntry
}
}
else
// newEntry >
entry in
currentNode
{
if
(currentNode
has a right child
)
currentNode =
right child of
currentNode
else
{
found =
true
Give
currentNode
a right child containing
newEntry
}
}
}
return
result
The
while
loop tries to match the new entry with an existing entry in the tree. If the new entry
is not in the tree already, the search for it ends at a node's
null
child reference. This is where a new
node belongs. But if the new entry matches an entry in the tree, we return the existing entry and
replace it in the tree with the new entry.
25.18
An iterative implementation of the method
addEntry
.
The Java implementation of the previous
algorithm closely follows the algorithm's logic. Note the use of the protected method
getRootNode
that is inherited from
BinaryTree
.
