Binary Trees - Data Structures and Algorithm Analysis - page 167

The shape of a BST depends on the order in which elements are inserted. A new
element is added to the BST as a new leaf node, potentially increasing the depth of
the tree. Figure 5.13 illustrates two BSTs for a collection of values. It is possible
for the BST containing n nodes to be a chain of nodes with height n. This would
happen if, for example, all elements were inserted in sorted order. In general, it is
preferable for a BST to be as shallow as possible. This keeps the average cost of a
BST operation low.
Removing a node from a BST is a bit trickier than inserting a node, but it is not
complicated if all of the possible cases are considered individually. Before tackling
the general node removal process, let us first discuss how to remove from a given
subtree the node with the smallest key value. This routine will be used later by the
general node removal function. To remove the node with the minimum key value
from a subtree, first find that node by continuously moving down the left link until
there is no further left link to follow. Call this node S. To remove S, simply have
the parent of S change its pointer to point to the right child of S. We know that S
has no left child (because if S did have a left child, S would not be the node with
minimum key value). Thus, changing the pointer as described will maintain a BST,
with S removed. The code for this method, named deletemin , is as follows:

privateBSTNode<Key,E>deletemin(BSTNode<Key,E>rt){
if(rt.left()==null)returnrt.right();
rt.setLeft(deletemin(rt.left()));
returnrt;

}

Example5.6 Figure 5.16 illustrates the deletemin process. Beginning
at the root node with value 10, deletemin follows the left link until there
is no further left link, in this case reaching the node with value 5. The node
with value 10 is changed to point to the right child of the node containing
the minimum value. This is indicated in Figure 5.16 by a dashed line.

A pointer to the node containing the minimum-valued element is stored in pa-
rameter S . The return value of the deletemin method is the subtree of the cur-
rent node with the minimum-valued node in the subtree removed. As with method
inserthelp , each node on the path back to the root has its left child pointer
reassigned to the subtree resulting from its call to the deletemin method.
A useful companion method is getmin which returns a reference to the node
containing the minimum value in the subtree.

privateBSTNode<Key,E>getmin(BSTNode<Key,E>rt){
if(rt.left()==null)returnrt;
returngetmin(rt.left());

}