从二叉搜索树中删除元素

Question

我在做作业，实现自己的二叉查找树。问题是，我们有自己的节点实现，它的父节点是不可直接访问的。

我一直在寻找答案，但我不想完全照搬解决方案，尽管如此，我似乎仍然没有得到正确的答案。我错过了一些元素没有被删除的情况。

你能帮帮我吗？我做错了什么？

这是删除方法：

void remove(E elem) {
    if(elem != null){
        if (root != null && contains(elem)) {  
            removeFromSubtree(elem, root, null);  
        }
    }
}

void removeFromSubtree(E elem, Node<E> current, Node<E> parent) {

    if(elem.less(current.contents)){
        if(current.left == null) return ;
        removeFromSubtree(elem, current.left, current);
    } else if(elem.greater(current.contents)){
        if(current.right == null)return;
        removeFromSubtree(elem, current.right, current);
    } else {
        if(current.left != null && current.right != null){
            //both children
            if(parent == null){
                Node<E> n = new Node<>(null, null);
                n.left = root;
                removeFromSubtree(root.contents, n, null);
                root = n.left;
                root.setParent(null);
            }
            E min = subtreeMin(current.right);
            current.contents = min;
            removeFromSubtree(min, current.right, current);
        } else if(current.left != null){
            //left child
            if (parent == null) {
                    root = current.left;
                    current.left.setParent(null);
                    return ;
                }
            setParentChild(current, parent, current.left);
        } else if(current.right != null){
            //right child
            if (parent == null) {
                root = current.right;
                current.right.setParent(null);
                return ;
            }
            setParentChild(current, parent, current.right);
        } else {
            if (parent == null) {
                root = null;
                return ;
            }
            setParentChild(current, parent, null);
        }
    }
}

节点使用通用接口

class Node<E extends DSAComparable<E>>

只有比较的方法。它看起来像这样

interface DSAComparable<E extends DSAComparable<E>> {
    boolean less(E other); 
    boolean greater(E other);
    boolean equal(E other);
}

我在remove中使用了另一种方法，它设置节点的父节点的子节点，具体取决于它的左子节点还是右子节点。

void setParentChild(Node<E> node, Node<E> parent,Node<E> value){
    if(parent!= null){
        if (parent.left == node) {
            parent.left = value;
        } else {
            parent.right = value;
        }
        if(value!= null) value.setParent(parent);
    }
}

方法subtreeMin（节点节点）查找子树中最小的值（最左边的值）

Answer 1

理解您的代码并不容易，因为它仍然缺乏细节。

我会参考你可以在网上找到的二叉搜索树的这种实现。

例如，参见《算法》第4版中的那篇。