"简单"Trie实施

Question

我需要为大学项目实现Trie(用Java).Trie应该能够添加和删除字符串(适用于阶段1).

我每天花费几个小时(最近几天)试图弄清楚如何做到这一点并且每次都惨不忍睹.

我需要一些帮助,互联网上的例子和我的教科书(Java中的数据结构和算法,Adam Drozdek)没有帮助.

信息

1. 我正在使用的节点类:

   class Node {
       public boolean isLeaf;
   }
   
   class internalNode extends Node {
       public String letters;  //letter[0] = '$' always.
       //See image -> if letter[1] = 'A' then children[1] refers to child node "AMMO"
       //See image -> if letter[2] = 'B' then children[2] refers to internal node "#EU"
       public TrieNode[] children = new TrieNode[2];
   
       public TrieInternalNode(char ch)
       {
           letters = "#" + String.valueOf(ch);//letter[0] = '$' always.
           isLeaf = false;
       }
   }
   
   class leafNode extends Node
   {
       public String word;
       public TrieLeafNode(String word)
       {
           this.word = new String(word);
           isLeaf = true;
       }
   }
   

2. 这里是我需要遵循的插入伪代码:(警告它非常模糊)

   trieInsert(String K)
   {
       i = 0;
       p = the root;
       while (not inserted)
       {
           if the end of word k is reached
               set the end-of-word marker in p to true;
           else if (p.ptrs[K[i]] == 0)
               create a leaf containing K and put its address in p.ptrs[K[i]];
           else if reference p.ptrs[K[i]] refers to a leaf
           {
               K_L = key in leaf p.ptrs[K[i]]
               do
               {
                   create a nonleaf and put its address in p.ptrs[K[i]];
                   p = the new nonleaf;
               } while (K[i] == K_L[i++]);
           }
           create a leaf containing K and put its address in p.ptrs[K[--i]];
           if the end of word k is reached
               set the end-of-word marker in p to true;
           else
               create a leaf containing K_L and put its address in p.ptrs[K_L[i]];
           else
               p = p.ptrs[K[i++]];
       }
   }
   

3. 我需要实现以下方法.

   public boolean add(String word){...}//adds word to trie structure should return true if successful and false otherwise
   
   public boolean remove(String word){...}//removes word from trie structure should return true if successful and false otherwise
   

4. 我找不到删除伪代码,但如果插入不起作用删除不会帮助我.

5. 这是我需要实现的Trie应该是什么样子的图像.

6. 我知道如果像这样实现,Trie仍然效率低下,但目前我不用担心这个问题.

7. 本书提供了一个类似于我需要做的实现,但没有使用单词char('$')的结尾,只存储没有前缀的单词在子节点中 http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

约束

1. 我需要在JAVA中实现trie.
2. 我可能不会导入或使用任何Java的内置数据结构.(即没有Map,HashMap,ArrayList等)
3. 我可以使用Arrays,Java原始类型和Java字符串.
4. Trie必须使用$(美元)符号来表示单词结尾.(见下图)

5. 我可以假设现在$插入包含符号的单词.
6. 我需要以与本书相同的风格实现Trie.
7. 单词的情况无关紧要即.所有单词都将被视为小写
8. Trie应该只存储单词结尾字符和适用于单词而不是整个字母表的字符(如某些实现).

我不希望有人为我执行(除非他们有一个人躺着:P)我真的需要帮助.

Answer 1

首先，我认为您不应该将叶节点和内部节点分开类。我建议使用 isLeaf() 方法创建一个通用节点类。如果节点没有子节点，则此方法将返回 true。

这是您需要实现的功能的一些高级伪代码。为简单起见，我假设存在一个名为 getIndex() 的方法，该方法返回与字符对应的索引。

Insert(String str)
    Node current = null
    for each character in str
        int index = getIndex(character)
        if current.children[index] has not been initialized
            initialize current.children[index] to be a new Node
        current = current.children[index]

您可以轻松地扩展此伪代码以满足您的需求。例如，如果您想在插入不成功时返回 false：

• 如果输入字符串为空则返回 false
• 如果输入字符串包含无效字符，则返回 false

现在，这是一些用于删除的更高级别的伪代码。

Remove(String str)
    Node current = null
    for each character in str
        int index = getIndex(character)
        current = current.children[index] 

    // At this point, we found the node we want to remove. However, we want to 
    // delete as many ancestor nodes as possible. We can delete an ancestor node 
    // if it is not need it any more. That is, we can delete an ancestor node 
    // if it has exactly one child. 

    Node ancestor = current
    while ancestor is not null
        if ancestor has 2 or more children
            break out of loop 
        else if ancestor has less than 2 children
            Node grandAncestor = ancestor.parent
            if grandAncestor is not null
                reinitialize grandAncestor.children // this has the effect of removing ancestor

        ancestor = ancestor.parent   

在非常高的级别上，我们按照输入字符串找到要删除的节点。之后，我们按照父指针向上遍历树，并删除具有 1 个子节点的每个节点（因为不再需要它）。一旦我们到达有 2 个子节点的节点，我们就停止。

与 Insert 一样，我们可以轻松地扩展此伪代码，以便在删除不成功时返回 false：

• 如果输入字符串为空则返回 false
• 如果输入字符串包含无效字符，则返回 false
• 如果输入字符串指向不存在的 Node，则返回 false

如果您的 Node 类有父字段，那么实现删除是最简单的。然而，没有父点的方法也可以实现，但是比较困难。您可以在此处查看更复杂的实现示例。