Trie删除功能的意外功能

Question

我是一个新的编程在Java中，我写的代码为Trie存储数字作为位（最后31位从右）。因此，每个节点只有两个可能的孩子在最大，0或1。

每个Trie节点的节点有以下属性

• 节点 next[] ：指向下一个节点的大小为2的数组。
• int visCnt : 一个节点被访问的次数，这将用于以后删除该节点（请查看下面的删除功能）。
• 人数 ：叶子节点上存储的数字，例如，如果我们将5插入到Trie中，叶子节点的'number'值为5，而从根节点到叶子节点的所有其他节点的默认值为-1。

我已经实现的功能是

• 空白插入(int num) ：将 "num "插入到全局的trie中。
• void remove(int num, Node A,int ind) : 递归函数，用于删除全局Trie中存在的数字。对于节点A，从main传递（全局Trie的）根节点，到达要删除的节点。从叶子开始，通过检查visCnt的值，从下往上删除节点。
• 布尔运算 isExist(int num) : 检查全局Trie中是否存在num。

实现中的remove函数没有达到预期的效果，我把代码粘贴到下面，供大家参考，（大家可以尝试在onlineGDB这样的网站上运行，那里会很好用）。在主函数中，我在insert(4)之后，然后remove(4)，我希望isExist(4)返回false，但事实并非如此，它返回的是true。将节点对象设置为null是否不会删除节点？

Code.Impert(4)和remove(4)

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;
    }
}

Ouput

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

Answer 1

我改变了你的 移除() 到这个。

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父的 A 是没有得到它。由于Java是 按价值调用，不 呼叫. 所以你需要这样做。

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

和休息代码是为了应对变化。我希望，你得到的原因。