Java Reference
In-Depth Information
Let us trace the calls to
addNode
when inserting
Romeo
into the tree in
Figure 9
.
The first call to
addNode
is
root.addNode(newNode)
Because
root
points to
Juliet
, you compare
Juliet
with
Romeo
and find that
you must call
root.right.addNode(newNode)
The node
root.right
is
Tom
. Compare the data values again (
Tom
vs.
Romeo
)
and find that you must now move to the left. Since
root.right.left
is
null
,
set
root.right.left
to
newNode
, and the insertion is complete (see
Figure 10
).
724
725
Unlike a linked list or an array, and like a hash table, a binary tree has no insert
positions. You cannot select the position where you would like to insert an element
into a binary search tree. The data structure is self-organizing; that is, each element
finds its own place.
We will now discuss the removal algorithm. Our task is to remove a node from the
tree. Of course, we must first find the node to be removed. That is a simple matter,
due to the characteristic property of a binary search tree. Compare the data value to be
removed with the data value that is stored in the root node. If it is smaller, keep
looking in the left subtree. Otherwise, keep looking in the right subtree.
Let us now assume that we have located the node that needs to be removed. First, let
us consider an easy case, when that node has only one child (see
Figure 11
).
To remove the node, simply modify the parent link that points to the node so that it
points to the child instead.
If the node to be removed has no children at all, then the parent link is simply set to
null
.
When removing a node with only one child from a binary search tree, the child
replaces the node to be removed.
The case in which the node to be removed has two children is more challenging.
Rather than removing the node, it is easier to replace its data value with the next
