BST节点删除

Question

我正在读"Data structures and algorithm analysis in Java-Person (2012), Mark Allen Weiss"的书。

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 );
    }

我了解到删除节点的一般方法是将删除节点的值替换为右边的最小值。

我的问题是 "else statement" 有什么用？例如，

如果我想去掉8，第一步应该换成9

然后在11的叶子中找到9置为null，

所以我不明白为什么是

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

而不是

else 
     t = null

Answer 1

您提到的 else 语句是针对节点只有一个 children 的情况执行的（因为针对 two-children 情况的 if else 语句不会' t 被评估为 true)。

因此，这里要分配non-Null节点，所以做：

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

表示如果 left 不是 null，则将 left 分配给 t，否则将 right 分配给 t。这里我们知道我们正好有一个 child，因此只有 left 或 right 不为空。

所以如果我们这样做了：

t = null;

那是错误的。

BST节点删除

BST node deletion

java

binary-search-tree