我需要实现 Trie (在 Java 中)用于大学项目。 Trie 应该能够添加和删除字符串(对于阶段 1)。
我每天(过去几天)都花几个小时试图弄清楚如何做到这一点,但每次都惨遭失败。
我需要一些帮助,互联网上的示例和我的教科书(Adam Drozdek 的 Java 中的数据结构和算法)都没有帮助。
信息
我正在使用的节点类:
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 的图像。
我知道如果这样实现 Trie 树仍然效率低下,但目前我不必担心这一点。
这本书提供了一个与我需要做的类似的实现,但不使用单词结尾字符('$')并且仅将不带前缀的单词存储在子节点中
http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java
约束
- 我需要用 JAVA 实现 trie。
- 我不得导入或使用 Java 的任何内置数据结构。 (即没有 Map、HashMap、ArrayList 等)
- 我可能会使用数组、Java 原始类型和 Java 字符串。
- Trie 必须使用
$
(美元)符号来指示词尾。 (见下图)
- 我假设现在将插入包含
$
符号的单词。 - 我需要以与本书相同的风格实现 Trie it。
- 单词的大小写无关紧要,即。所有单词都将被视为小写
- Trie 应该只存储词尾字符和适用于单词的字符,而不是整个字母表(如某些实现)。
我不希望任何人为我做实现(除非他们身边有人 :P)我真的需要帮助。
最佳答案
首先,我不认为你应该让叶节点和内部节点分开类。我建议使用 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 个 child 的节点,我们就停止。
与 Insert 一样,我们可以轻松地扩充此伪代码以在删除不成功时返回 false:
- 如果输入字符串为空则返回false
- 如果输入的字符串包含无效字符则返回false
- 如果输入字符串指向不存在的节点,则返回 false
如果您的 Node 类具有父字段,则最容易实现删除。但是,没有父点的方法是可以实现的,只是比较困难。您可以看到一个更棘手的实现示例 here .
关于java - "Simple"Trie实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23182614/