CODEWITHSUNDEEP
javabinary-search-tree
Jackson Xie
Jackson Xie

Reputation: 87

BST node deletion

I am reading the book of "Data structures and algorithm analysis in Java-Person (2012), Mark Allen Weiss".

The code for delete node in BST 

  /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
    {
        if( t == null )
            return t;   // Item not found; do nothing

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            t.left = remove( x, t.left );
        else if( compareResult > 0 )
            t.right = remove( x, t.right );
        else if( t.left != null && t.right != null ) // Two children
        {
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }
        else
            t = ( t.left != null ) ? t.left : t.right;
        return t;
    }
    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the subtree.
     * @return node containing the smallest item.
     */
    private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
    {
        if( t == null )
            return null;
        else if( t.left == null )
            return t;
        return findMin( t.left );
    }

I understand that the general method for deleting a node is to replace the value of deleting node by the minimum value on the right side.

My question is that what is "else statement" for? For example, 

       13
      /  \
     8   14
    / \ 
   6   11
      /  \
     9    12

if I wish to remove 8, the first step should be replaced by 9

       13
      /  \
     9   14
    / \ 
   6   11
      /  \
     9    12

and then find 9 in the leaf of 11 and set it null, 

       13
      /  \
     9   14
    / \ 
   6   11
      /  \
     null 12

So I don't understand why it is 

else
     t = ( t.left != null ) ? t.left : t.right;

rather than

else 
     t = null

Upvotes: 1

Views: 142

Answers (1)

gsamaras
gsamaras

Reputation: 73444

That else statement you are mentioning is meant to be executed for the case that a node has only one children (since the if else statement that is meant for the two-children case won't be evaluated to true).

As a result, here you want to assign the non-Null node, so you do:

t = ( t.left != null ) ? t.left : t.right;

which says that if left is not null, then assign left to t, else assign right to t. Here we know that we have exactly one child, thus only left or right will be not null.

So if we did:

t = null;

that would be wrong.

Upvotes: 1

Related Questions