Java Reference
In-Depth Information
37
24
42
40
42
7
32
120
2
35
Figure5.15
An example of BST insertion. A record with value 35 is inserted
into the BST of Figure 5.13(a). The node with value 32 becomes the parent of the
new node containing 35.
Inserting a record with key value k requires that we first find where that record
would have been if it were in the tree. This takes us to either a leaf node, or to an
internal node with no child in the appropriate direction.
3
Call this node R
0
. We then
add a new node containing the new record as a child of R
0
. Figure 5.15 illustrates
this operation. The value 35 is added as the right child of the node with value 32.
Here is the implementation for
inserthelp
:
/
**
@returnThecurrentsubtree,modifiedtocontain
thenewitem
*
/
privateBSTNode<Key,E>inserthelp(BSTNode<Key,E>rt,
Keyk,Ee){
if(rt==null)returnnewBSTNode<Key,E>(k,e);
if(rt.key().compareTo(k)>0)
rt.setLeft(inserthelp(rt.left(),k,e));
else
rt.setRight(inserthelp(rt.right(),k,e));
returnrt;
}
You should pay careful attention to the implementation for
inserthelp
.
Note that
inserthelp
returns a pointer to a
BSTNode
. What is being returned
is a subtree identical to the old subtree, except that it has been modified to contain
the new record being inserted. Each node along a path from the root to the parent
of the new node added to the tree will have its appropriate child pointer assigned
to it. Except for the last node in the path, none of these nodes will actually change
their child's pointer value. In that sense, many of the assignments seem redundant.
However, the cost of these additional assignments is worth paying to keep the inser-
tion process simple. The alternative is to check if a given assignment is necessary,
which is probably more expensive than the assignment!
3
This assumes that no node has a key value equal to the one being inserted. If we find a node that
duplicates the key value to be inserted, we have two options. If the application does not allow nodes
with equal keys, then this insertion should be treated as an error (or ignored). If duplicate keys are
allowed, our convention will be to insert the duplicate in the right subtree.
