无法删除二进制搜索树中的根节点

Question

我正在尝试删除我的二叉查找树的根，以便我可以更新它的值，但这种方法不能做到这一点。我的想法是删除根，然后将其再次插入二叉查找树中，但使用另一个值。它适用于树中的每个节点，但不是我无法删除它的根本原因。有人知道为什么会发生这种情况吗？谢谢。

public V remove(K key) {
    Node node = remove(key, root);
    return node.value;
}

private Node remove(K key, Node current) {
    if (current == null) { 
        return null;
    }
    if (current.key.equals(key)) { 
        
        if (current.left == null && current.right == null) {
            return null;
        } 
        else if (current.left == null && current.right != null) {
            return current.right;
        } else if (current.left != null && current.right == null) {
            return current.left;
        } else {
            Node plowest = current.right;
            Node parent = current;
            while (plowest.left != null) {
                parent = plowest;
                plowest = plowest.left;
            }
            plowest.left = current.left;
            if (plowest != current.right) {
                parent.left = plowest.right;
                plowest.right = current.right;
            }
            return plowest;
        }
    }
    if (key.compareTo(current.key) < 0) { // Subarbre esquerra
        current.left = remove(key, current.left);                                   
    } else {// Subarbre dret
        current.right = remove(key, current.right);
    }
    return current;
}

这是我调用方法删除任何节点的主代码，在这种情况下，我想删除根。

public static void main(String[] args) {

    BSTMapping<String, Integer> arbre = new BSTMapping();
    arbre.put("G", 4);
    arbre.put("A", 1);
    arbre.put("C", 2);

    arbre.remove("G");

    Iterator it = arbre.iterator();
    while (it.hasNext()) {
        BSTMapping.Pair p = (BSTMapping.Pair) it.next();
        System.out.println(p.getKey() + " - " + p.getValue());
    }

     
}

Answer 1

删除根目录时，remove（K键，当前节点）永远不会到达将节点分配给当前节点的底部。左或当前。右。您可以在适当的情况下，通过直接分配给根变量，在删除（键）中解决此问题。

public V remove(K key) {
    Node node = remove(key, root);
    if (root.key.equals(key)) {
       root=node;
    }
    return node.value;
}