信息

我正在使用的节点类：

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

以下是我需要遵循的插入伪代码:(警告它很模糊）

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

我需要实现以下方法 .

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

我找不到删除伪代码，但如果插入不起作用删除不会帮助我 .
这是我需要实现的Trie应该是什么样子的图像 .

enter image description here

我知道如果像这样实现，Trie仍然效率低下，但目前我不用担心这个问题 .
本书提供的实现类似于我需要做的但不是't use the end of word char (' $'）并且只在子节点中存储没有前缀的单词 http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

约束

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

enter image description here

我可能会认为现在将插入包含 $ 符号的单词 .
我需要以与本书相同的方式实现它 .
单词的情况无关紧要，即 . 所有单词都将被视为小写
Trie应该只存储单词结尾字符和适用于单词而不是整个字母的字符（如某些实现） .

我不希望有人为我做这个实施（除非他们有一个躺着：P）我真的需要帮助 .

1 回答

2
首先，我认为你不应该让叶子节点和内部节点分开类 . 我建议使用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：
- 如果输入字符串为null，则返回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：
- 如果输入字符串为null，则返回false
- 如果输入字符串包含无效字符，则返回false
- 如果输入字符串指向不存在的节点，则返回false
如果您的Node类具有父字段，则最容易实现删除 . 但是，可以在没有父点的情况下实现该方法，但是更加困难 . 您可以看到棘手的实现here的示例 .
回复于 2024-04-29T07:23:56+08:00

“简单”Trie实施

信息

约束

1 回答

相关问题