Trie delete函数的意外功能

Question

我是Java编程的新手，我为trie编写了将数字存储为位的代码（右起最后31位）。因此，每个节点在max、0或1处只有两个可能的子节点。

每个trie节点的节点都具有以下属性

• 节点下一个[]：大小为2的数组指向下一个节点

我实现的功能是

• void insert（int num）：在全局trie中插入'num'
• voidremove（intnum，Node A，intind）：递归函数，用于删除全局trie中存在的数字。对于节点A，我从main传递根（全局trie），并到达要删除的节点。从叶中，通过检查visCnt的值，从下到上删除节点
• 布尔isExist（int num）：检查全局trie中是否存在num

实现中的删除功能并不像预期的那样工作，我已经将代码粘贴到下面以供参考，（你可以尝试在像onlineGDB这样的网站上运行，在那里它会正常工作）。在主函数中，我插入（4），然后删除（4），我希望isExist（4）返回false，但事实并非如此，它返回为true。将节点对象设置为null不会删除节点吗？

代码：

import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
    static class Node{
        Node next[] = new Node[2];
        int visCnt=0;
        int number = -1;
    }
    static Node root = new Node();
    void insert(int num){
        System.out.println("added "+num);
        Node cur =root;
        for(int i = 30;i>=0;i--){
            cur.visCnt++;
            int tmp = 1<<i;
            int curBit = ((tmp&num)==0)?0:1;
            if(cur.next[curBit]==null)
                cur.next[curBit] = new Node();
            cur=cur.next[curBit];
        }
        cur.visCnt++;
        cur.number = num;
    }
    void remove(int num, Node A,int ind){
        if(A==null){
            System.out.println("removed "+num);
            return;
        }
        A.visCnt--;
        int curBit = ((1<<ind)&num)==0?0:1;
        remove(num,A.next[curBit],ind-1);
        if(A.visCnt==0){
            A=null;
        }
    }
    boolean isExist(int num){
        System.out.println("checking for  "+num);
        Node cur =root;
        for(int i = 30;i>=0;i--){
            cur.visCnt++;
            int tmp = 1<<i;
            int curBit = ((tmp&num)==0)?0:1;
            if(cur.next[curBit]==null){
                System.out.println(num+ " does not exist in trie ");
                return false;
            }
            cur=cur.next[curBit];
        }
        System.out.println(cur.number+ " exists in trie ");
        return true;
    }
    public static void main(String[] args) {
        Main trie = new Main();
        trie.root.visCnt++;
        trie.insert(1);
        trie.insert(2);
        trie.insert(4);
        trie.remove(4,root,30);
        trie.isExist(4);
        // return ans;
    }
}

输出

added 1
added 2
added 4
removed 4
checking for  4
4 exists in trie 

Answer 1

我将您的remove（）更改为：

void remove(int num, Node A,int ind){
    A.visCnt--;
    if(A.next[0]==null && A.next[1] == null){
        System.out.println("removed " + num);
        return;
    }
    int curBit = ((1<<ind)&num)==0?0:1;
    remove(num,A.next[curBit],ind-1);
    if(A.next[curBit].visCnt == 0){
        A.next[curBit]=null;
    }
}

它正在工作...

added 1
added 2
added 4
added 4
removed 4
checking for  4
4 exists in trie 
removed 4
checking for  4
4 does not exist in trie 

加了两次4。

说明：

你的问题在这里：

if(A.visCnt==0){
    A=null;
}

当您在引用A中输入null时，A的父级无法获得它。因为Java是按值调用的，而不是按引用调用的。因此，您需要这样做：

if(A.next[curBit].visCnt == 0){
    A.next[curBit]=null;
}

而rest代码则是为了应对这些变化。我希望你知道原因。