如何在Trie数据结构中实现删除方法？

I am trying to implement PatriciaTrie data structure. I was recently asked this question in a coding interview through Google Docs. But I was not able to answer this.

我正在尝试实现PatriciaTrie数据结构。最近我通过Google Docs在编码访谈中问过这个问题。但我无法回答这个问题。

I made some progress by adding insert method in the below code but got stuck on the remove method in the PatriciaTrie code - not sure how to implement that -

我通过在下面的代码中添加insert方法取得了一些进展，但是卡在了PatriciaTrie代码中的remove方法 - 不确定如何实现 -

Below is my PatriciaTrie code -

以下是我的PatriciaTrie代码 -

public class PatriciaTrie {

    protected static class Edge {
        Node target;
        TTString label;
        public Edge(Node target, TTString label) {
            this.target = target;
            this.label = label;
        }
    }

    protected static class Node {
        Edge[] edges;           // the children of this node
        int numberOfChildren;   // the number of children
        public Node() {
            edges = new Edge[128];
            numberOfChildren = 0;
        }
    }

    /**
     * number of strings stored in the trie
     */
    protected int number;

    /**
     * This is root
     */
    protected Node root;

    public PatriciaTrie() {
        root = new Node();
        number = 0;
    }

    /** 
     * Add the x to this trie
     * @param x the string to add
     * @return true if x was successfully added or false if x is already in the trie
     */
    public boolean insert(TTString x) {
        Node current = root;
        for (int i = 0; i < x.length(); i++) {
            TTString ch = x.subString(i, 1);
            if (current.edges[x.charAt(i)] != null) {
                Node child = current.edges[x.charAt(i)].target;
                current = child;
            } else {
                current.edges[x.charAt(i)] = new Edge(new Node(), ch);
                current.numberOfChildren++;
                current = current.edges[x.charAt(i)].target;
            }
            if (i == x.length() - 1)
                return true;
        }
        return false;
    }

    /** 
     * Remove x from this trie
     * @param x the string to remove
     * @return true if x was successfully removed or false if x is not stored in the trie
     */
    public boolean remove(TTString x) {
        // not sure how to do this

        return false;
    }       
}

And below is my TTString class -

以下是我的TTString类 -

public class TTString {
    int i;        // index of first character  
    int m;        // length
    byte[] data;  // data 

    public TTString(String s) {
        data = s.getBytes();
        i = 0;
        m = s.length();
    }

    protected TTString(byte[] data, int i, int m) {
        this.data = data;
        this.i = i;
        this.m = m;
    }

    public TTString subString(int j, int n) {
        if (j < 0 || j >= m) throw new IndexOutOfBoundsException();
        if (n < 0 || j + n > m) throw new IndexOutOfBoundsException();
        return new TTString(data, i+j, n);
    }

    /**
     * The length of this string
     * @return
     */
    public int length() {
        return m;
    }

    /**
     * Return the character at index j
     * @param j
     * @return
     */
    public char charAt(int j) {
        return (char)data[i+j];
    }
}

Any thoughts on how to implement remove method here?

关于如何在这里实现删除方法的任何想法？

3 个解决方案

#1

One idea is: descend from the root to the leaf corresponding to the last character of x (assuming there is path containing x, otherwise there's nothing to change), remembering last fork on your path in the process (first fork is at the root). When you at the leaf, remove all edges/nodes from the last fork till the leaf.

一个想法是：从根到对应于x的最后一个字符的叶子（假设有包含x的路径，否则没有什么可以更改），记住进程中路径上的最后一个fork（第一个fork位于根目录） 。当您在叶子上时，从最后一个叉子中移除所有边缘/节点直到叶子。

#2

I have implemented it in C# on TRIE data structure for the string code is follow. You can see the complete code here http://devesh4blog.wordpress.com/2013/11/16/real-time-auto-complete-using-trie-in-c/

我在CIE上用TRIE数据结构实现了它，字符串代码如下。你可以在这里看到完整的代码http://devesh4blog.wordpress.com/2013/11/16/real-time-auto-complete-using-trie-in-c/

       public void RemoveWord(string word, TRIENode rootNode, string id)
    {
        int len = word.Length;
        if (len == 0)
        {
            rootNode.PrefixCount--;
            if (rootNode.PrefixCount == 0)
                rootNode.IsCompleteWord = false;
            rootNode.Ids.Remove(id);
            return;
        }
        for (int i = 0; i < len; i++)
        {
            string key = word.Substring(i, 1);
            string lowerVersionKey = key.ToLower();
            rootNode.PrefixCount--;
            rootNode = rootNode.Children[lowerVersionKey];
        }
        rootNode.Ids.Remove(id);
        if (rootNode.Ids.Count == 0)
            rootNode.IsCompleteWord = false;
    }

#3

This is my code and sample tests:

这是我的代码和示例测试：

protected static class Edge {
    Node target;
    TTString label;

    public Edge(Node target, TTString label) {
        this.target = target;
        this.label = label;
    }
}

protected static class Node {
    Edge[] edges; // the children of this node
    int numberOfChildren; // the number of children
    // isEnd is true means this node is a string's end node.
    boolean isEnd;

    public Node() {
        edges = new Edge[128];
        numberOfChildren = 0;
        isEnd = false;
    }
}

/**
 * number of strings stored in the trie
 */
protected int number;

/**
 * This is root
 */
protected Node root;

public PatriciaTrie() {
    root = new Node();
    number = 0;
}

/**
 * Add the x to this trie
 * 
 * @param x
 *            the string to add
 * @return true if x was successfully added or false if x is already in the
 *         trie
 */
public boolean insert(TTString x) {
    // not sure what I am supposed to do here?
    Node current = root;
    for (int i = 0; i < x.length(); i++) {
        TTString ch = x.subString(i, 1);
        if (current.edges[x.charAt(i)] != null) {
            Node child = current.edges[x.charAt(i)].target;
            current = child;
        } else {
            current.edges[x.charAt(i)] = new Edge(new Node(), ch);
            current.numberOfChildren++;
            current = current.edges[x.charAt(i)].target;
        }
        if (i == x.length() - 1) {
            // mark this node is the string x's end node.
            current.isEnd = true;
            return true;
        }
    }
    return false;
}

// find the string x in the trie, if true, return the x.
public TTString find(TTString x) {
    boolean isOk = false;
    Node current = root;
    for (int i = 0; i < x.length(); i++) {
        if (current.edges[x.charAt(i)] != null) {
            current = current.edges[x.charAt(i)].target;
        } else {
            isOk = false;
        }
        if (i == x.length() - 1 && current.isEnd == true) {
            isOk = true;
        }
    }
    if (isOk == false)
        return null;
    else
        return x;
}

public boolean remove(TTString x) {
    Node current = root;
    for (int i = 0; i < x.length(); i++) {
        if (current.edges[x.charAt(i)] != null) {
            current = current.edges[x.charAt(i)].target;
        } else {
            return false;
        }
        if (i == x.length() - 1) {
            // delete the string x.
            current.isEnd = false;
            return true;
        }
    }
    return false;
}

void run() {
    /*
     * Here is the sample patricialTrie whose edges are labeled with
     * letters.
     */
    TTString tmp = new TTString("ABCD");
    System.out.println(insert(tmp) ? "YES" : "NO");
    Node current = root;
    for (int i = 0; i < tmp.length(); i++) {
        System.out.println(current.edges[tmp.charAt(i)].label.charAt(0));
        current = current.edges[tmp.charAt(i)].target;
    }
    tmp = new TTString("ABCDE");
    insert(tmp);
    tmp = new TTString("ABDF");
    insert(tmp);

    /*
     * remove method
     */
    tmp = new TTString("ABCDE");
    System.out.println(remove(tmp) ? "YES" : "NO");
    System.out.println(find(tmp) == null ? "NULL" : find(tmp));
    tmp = new TTString("ABCD");
    System.out.println(find(tmp) == null ? "NULL" : find(tmp));
}

public static void main(String args[]) {
    new PatriciaTrie().run();
}