Java Reference
In-Depth Information
37 40
24
42
40
42
7
32
120
2
Figure5.17
An example of removing the value 37 from the BST. The node
containing this value has two children. We replace value 37 with the least value
from the node's right subtree, in this case 40.
/
**
Removeanodewithkeyvaluek
@returnThetreewiththenoderemoved
*
/
privateBSTNode<Key,E>removehelp(BSTNode<Key,E>rt,Keyk){
if(rt==null)returnnull;
if(rt.key().compareTo(k)>0)
rt.setLeft(removehelp(rt.left(),k));
elseif(rt.key().compareTo(k)<0)
rt.setRight(removehelp(rt.right(),k));
else{//Foundit
if(rt.left()==null)returnrt.right();
elseif(rt.right()==null)returnrt.left();
else{//Twochildren
BSTNode<Key,E>temp=getmin(rt.right());
rt.setElement(temp.element());
rt.setKey(temp.key());
rt.setRight(deletemin(rt.right()));
}
}
returnrt;
}
Figure5.18
Implementation for the BST
removehelp
method.
from the right subtree. To see why, call the greatest value in the left subtree G.
If multiple nodes in the left subtree have value G, selecting G as the replacement
value for the root of the subtree will result in a tree with equal values to the left of
the node now containing G. Precisely this situation occurs if we replace value 120
with the greatest value in the left subtree of Figure 5.13(b). Selecting the least value
from the right subtree does not have a similar problem, because it does not violate
the Binary Search Tree Property if equal values appear in the right subtree.
From the above, we see that if we want to remove the record stored in a node
with two children, then we simply call
deletemin
on the node's right subtree
and substitute the record returned for the record being removed. Figure 5.18 shows
an implementation for
removehelp
.
The cost for
findhelp
and
inserthelp
is the depth of the node found or
inserted. The cost for
removehelp
is the depth of the node being removed, or
