Java : BST - 删除没有 children 的节点不起作用

Question

我正在使用链接节点来表示 BST。我可以找到一个没有 children 的节点，但是这个节点的 remove 方法不起作用：

我添加了一个值为"cat"的节点后，所以我的BST只有一个没有children的节点。

我尝试删除"cat"节点，结果发现删除方法不起作用——"cat"节点还在BST中。

有人知道如何解决这个问题吗？谢谢

public class BinarySearchTree {

Node root;

public BinarySearchTree() {
    root = null;
}

/*
 * Adds the specified node to the BST
 */
public String add(String value) {
    if (root == null) {
        root = new Node(value);
        return value;
    }
    return add(root, value);
}

public String add(Node root, String value) {
    int comparision = value.compareTo(root.data);

    if (comparision < 0) {
        if (root.left != null)
            return add(root.left, value);
        root.left = new Node(value);
        return value;
    }

    if (comparision > 0) {
        if (root.right != null)
            return add(root.right, value);
        root.right = new Node(value);
        return value;
    }
    return value;// not allow duplicate
}

/*
 * Returns true if the string is found in the BST
 */
public boolean contains(String value) {
    return contains(root, value);
}

private boolean contains(Node root, String value) {
    if (root == null) {
        return false;
    }

    int comparison = value.compareTo(root.data);
    if (comparison == 0) {
        return true;
    }
    if (comparison < 0) {
        return contains(root.left, value);
    } else {
        return contains(root.right, value);
    }
}

/*
 * Checks whether the tree is empty or not
 */
public boolean isEmpty() {
    return root == null;
}

/*
 * Removes the specified string from the BST
 */
public boolean remove(String s) {
    if (contains(s) == false) {
        return false;
    }
    return remove(root, s);
}

public boolean remove(Node root, String s) {
    if (root == null) {
        return false;
    }

    int comparision = s.compareTo(root.data);

    if (comparision == 0) {
        if (root.left == null && root.right == null) {
            System.out.println("----------------------------------");
            root = null;
            return true;
        } else if (root.left != null && root.right != null) {
            Node temp = root;
            String min = minValue(temp.right).data;
            root.data = min;
            removemin(root.right);
            return true;
        }
    }

    if (comparision < 0) {
        if (root.left.data.equals(s)) {
            if (root.left.left == null || root.left.right == null) {
                root.left = root.left.right;
                return true;
            }
        }
        return remove(root.left, s);
    }

    if (comparision > 0) {
        if (root.right.data.equals(s)) {
            if (root.right.right == null || root.right.left == null) {
                root.right = root.right.left;
                return true;
            }
        }
        return remove(root.right, s);
    }
    return false;
}

public Node minValue(Node root) {
    if (root.left == null) {
        return root;
    } else
        return minValue(root.left);
}

public static void removemin(Node root) {
    if (root.left == null) {
        root = null;
    } else
        removemin(root.left);
}

/**
 * Prints the inorder traversal of this tree
 */
public void inorderTraversal() {
    inorderTraversal(root);
}

private void inorderTraversal(Node root) {
    if (root == null)
        return;
    inorderTraversal(root.left);
    System.out.print(root.data + " ");
    inorderTraversal(root.right);
}

private class Node {
    String data;
    Node left;
    Node right;

    public Node(String data) {
        this.data = data;
    }
}

/*
 * Returns the height of the tree
 */
public int getHeight() {
    return getHeight(root);
}

private int getHeight(Node root) {
    if (root == null)
        return 0;
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));

}

Answer 1

在您的 remove(Node root, String s) 方法中，在确定 root 包含 s 的值后，您只需将变量 root 更改为引用 null。这不会影响根的左侧或右侧 child 的 parent，因为它从不引用它们。

典型的 BST 删除方法将 return 一个节点，这样您就可以执行如下操作：

//...
if(valueToDelete.compareTo(root.value) == 0){
  if(root.left == null && root.right == null){
    return null;
  }
  // Otherwise some juggling of children into a new shape
  // ... actual code here
  return someNodeThatWasDescendantOfRoot
}else if(valueToDelete.compareTo(root.value) < 0){
  root.left = delete(root.left, valueToDelete)
  return root;
}else{
  root.right = delete(root.right, valueToDelete)
  return root;
}
//...

分配给可能受影响的 child 节点允许删除结果在必要时更新其 parent，而不需要 children 引用它们的 parents.

Answer 2

问题出在这部分的移除方法：

if (root.left == null && root.right == null) {
    System.out.println("----------------------------------");
    root = null;
    return true;
}

你期望删除根，但它没有删除，因为 java is pass by value. 所以当你做 root = null; 时，你正在设置复制变量为 null 而不是 BST 的 root.

这是您更新后的 remove 方法。为了减少混淆，我已将 root 重命名为 node。

public boolean remove(Node node, String s) {
    if (node == null) {
        return false;
    }

    int comparision = s.compareTo(node.data);

    if (comparision == 0) {
        if (node.left == null && node.right == null) {
            System.out.println("----------------------------------");
            if (node.equals(root))
                this.root = null;
            node = null;
            return true;
        } else if (node.left != null && node.right != null) {
            Node temp = node;
            String min = minValue(temp.right).data;
            node.data = min;
            removemin(node.right);
            return true;
        }
    }

    if (comparision < 0) {
        if (node.left.data.equals(s)) {
            if (node.left.left == null || node.left.right == null) {
                node.left = node.left.right;
                return true;
            }
        }
        return remove(node.left, s);
    }

    if (comparision > 0) {
        if (node.right.data.equals(s)) {
            if (node.right.right == null || node.right.left == null) {
                node.right = node.right.left;
                return true;
            }
        }
        return remove(node.right, s);
    }
    return false;
}

注意这部分代码，我将 this.root 设置为 null。

if (node.equals(root))
    this.root = null;

Java : BST - 删除没有 children 的节点不起作用

Java : BST - removing a node with no children doesn't work

java

binary-tree

nodes

binary-search-tree

data-structures