Trie 删除函数的意外运行

Question

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

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

下一个节点[]：大小为2的数组指向下一个节点
int visCnt : 一个节点被访问的次数，这将是
用于稍后删除节点（检查下面的删除功能）
int number : 叶子节点存储的数字，例如，如果我们向 trie 中插入 5，则叶子节点的 'number' 的值为 5同时，从根到叶的所有其他节点的默认值为 -1

我实现的功能有

void insert(int num) : 插入 'num' 到全局 trie
void remove(int num, Node A,int ind) : 删除数字的递归函数存在于全局树中。对于节点 A ，我传递了根（全局树的）从main开始，到达要删除的节点。从叶子，节点通过检查 visCnt 的值自下而上删除。
boolean isExist(int num) : 检查 num 是否存在于全局 trie

实现中的remove函数没有按预期工作，我把代码贴在下面供参考，（你可以在onlineGDB这样的网站上试试运行，它可以正常工作）。在我插入（4）然后删除（4）之后的主要功能中，我希望 isExist（4）为 return false 但事实并非如此，它 returns 为真。将节点对象设置为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;
}

当您将 null 放入引用 A 时，那么 A 的父级没有得到它。因为 Java 是 按值调用 ，而不是 按引用调用 。所以你需要这样做：

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

其余代码是为了应对变化。我希望，你明白原因了。

Trie 删除函数的意外运行

Unexpected functioning of Trie delete function

java

algorithm

implementation

trie

data-structures