AVL树节点移除

Question

因此，对于 class，我的任务是创建一个可以 add/remove 节点并以特殊方式打印所有节点的 AVLTree。我做到了这一点。 Eveyrthing 在我的本地计算机上运行良好。但是，当我将代码上传到在线提交服务器，并通过命令行输入进行测试时；我的一项功能停止工作，我希望有人能解释原因。

这是我在电脑上的主要方法：

        AVLTree avl = new AVLTree();
        avl.insert(5, "earl");
        avl.insert(3, "colin");
        avl.insert(6, "fiona");
        avl.show();
        avl.insert(2, "bonnie");
        avl.insert(4, "danielle");
        avl.show();
        avl.insert(1, "alex");
        avl.show();
        avl.delete("bonnie");
        avl.delete("alex");
        avl.show();

这是我用于命令行输入的第二种主要方法

public static void main(String[] args) throws FileNotFoundException{
        Scanner input = new Scanner(new File(args[0]));
        String name = new String();
        int key = 0;
        AVLTree avl = new AVLTree();
        while (input.hasNext()) {
            String opt = input.next().toUpperCase();
            switch(opt)
            {
               case "INSERT":
                  name  = input.next();
                  key = input.nextInt();
                  avl.insert(key, name);
                  break;
                case "REMOVE":
                              name = input.next();
                      System.out.println("***" + avl.search(name));//this is where the problem is. On the server it returns null, on my computer it returns the correct node
                    avl.delete(name);
                    break;
                case "SHOW":
                          avl.show();
                          break;
            }

        }
    }


}

两者主要是不同的，因为我在电脑上没有使用命令行，所以我在电脑版上复制了输入文件，然后手动输入所有内容。

这是输入文件

insert Earl 5
insert Colin 3
insert Fiona 6
show
insert Bonnie 2
insert Danielle 4
show
insert Alex 1
show
remove Bonnie
remove Alex
show

最后是删除节点所需的函数。

public boolean delete(String name) {
        Node target = search(name);
        if (target == null) return false;
        target = deleteNode(target);
        balanceTree(target.parent);
        return true;
    }

    private Node deleteNode(Node target) {
        if (isLeaf(target)) { //leaf
            if (isLeftChild(target)) {
                target.parent.left = null;
            } else {
                target.parent.right = null;
            }
        } else if (target.left == null ^ target.right == null) { //exact 1 child
            Node nonNullChild = target.left == null ? target.right : target.left; 
            if (isLeftChild(target)) {
                target.parent.setLeftChild(nonNullChild); 
            } else {
                target.parent.setRightChild(nonNullChild);
            }
        } else {//2 children
            Node immediatePredInOrder = immediatePredInOrder(target);
            target.value = immediatePredInOrder.value;
            target = deleteNode(immediatePredInOrder);
        }

        reHeight(target.parent);
        return target;
    }   
    public Node search(String name) {
        return binarySearch(root, name);
    }
    private Node binarySearch(Node node, String name) {
        if (node == null) 
        return null;
        if (name == node.name) 
            return node;
        else {
            Node foundNode = binarySearch(node.left, name);
            if(foundNode == null) {
                foundNode = binarySearch( node.right, name);
            }
            return foundNode;

        }

    }

问题是搜索功能找不到服务器版本的节点，我不明白为什么。

此外，这是输出

    Local Version
    earl 5
       colin 3
       fiona 6
    earl 5
       colin 3
          bonnie 2
          danielle 4
       fiona 6
    colin 3
       bonnie 2
          alex 1
       earl 5
          danielle 4
          fiona 6
    ***bonnie 2//the println statement for search

    earl 5
       colin 3

Server Version

Earl 5
   Colin 3
   Fiona 6
Earl 5
   Colin 3
      Bonnie 2
      Danielle 4
   Fiona 6
Colin 3
   Bonnie 2
      Alex 1
   Earl 5
      Danielle 4
      Fiona 6
***null//search println
***null//search println
Colin 3
   Bonnie 2
      Alex 1
   Earl 5
      Danielle 4
      Fiona 6

          danielle 4
       fiona 6

Answer 1

我的教授和我就这些进行了讨论，我们发现问题是因为 java 的版本不同。

我们只是改变了

if (name == node.name)

到

if (name.compareTo(node.name) == 0)

在binarySearch()方法中

AVL树节点移除

AVLTree Node Removal

java

binary-search

avl-tree