1. 概述
数据结构是计算机编程中的重要分支，知道何时以及为何使用它们非常重要。
本文简单介绍一下trie(发音为“try”)数据结构，以及它的实现和复杂度分析。
2. 字典树
字典树是一种离散数据结构，在典型的算法课程中不太为人所知或被广泛提及，但却是一种重要的数据结构。
字典树(也称为数字树)，有时甚至是基数树或前缀树(因为它们可以通过前缀进行搜索)，是一种有序树结构，它利用其存储的键-通常是字符串。
节点在树中的位置定义了与该节点关联的键，这使得trie与二叉搜索树不同，在二叉搜索树中，节点存储仅与该节点对应的键。
节点的所有后代都具有与该节点关联的字符串的公共前缀，而根与空字符串关联。
这里我们对TrieNode进行了预览，我们将在Trie的实现中使用它：
public class TrieNode {
private HashMap<Character, TrieNode> children;
private String content;
private boolean isWord;
// ...
}
在某些情况下，字典树可能是二叉搜索树，但通常情况下，它们是不同的。二叉搜索树和字典树都是树，但二叉搜索树的每个节点总是有两个子节点，而字典树的节点则可以有多个。
在字典树中，每个节点(根节点除外)都存储一个字符或数字。通过从根节点向下遍历字典树到特定节点n，可以形成一个由字符或数字组成的公共前缀，该前缀也由字典树的其他分支共享。
通过从叶节点到根节点遍历字典树，可以形成一个字符串或数字序列。
下面是Trie类，它代表trie数据结构的一种实现：
public class Trie {
private TrieNode root;
// ...
}
3. 常用操作
现在，我们来看看如何实现基本操作。
3.1 插入元素
我们将描述的第一个操作是插入新节点。
在开始实现之前，了解算法非常重要：
- 将当前节点设置为根节点
- 将当前字母设置为单词的首字母
- 如果当前节点已经存在对当前字母的引用(通过“children”字段中的某个元素)，则将当前节点设置为该引用节点。否则，创建一个新节点，将字母设置为当前字母，并将当前节点初始化为该新节点
- 重复步骤3，直到遍历完key
此操作的复杂度为O(n)，其中n表示键大小。
以下是该算法的实现：
public void insert(String word) {
TrieNode current = root;
for (char l: word.toCharArray()) {
current = current.getChildren().computeIfAbsent(l, c -> new TrieNode());
}
current.setEndOfWord(true);
}
现在让我们看看如何使用这种方法在trie中插入新元素：
private Trie createExampleTrie() {
Trie trie = new Trie();
trie.insert("Programming");
trie.insert("is");
trie.insert("a");
trie.insert("way");
trie.insert("of");
trie.insert("life");
return trie;
}
我们可以通过以下测试来测试trie是否已经填充了新节点：
@Test
public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() {
Trie trie = createTrie();
assertFalse(trie.isEmpty());
}
3.2 查找元素
现在让我们添加一个方法来检查特定元素是否已经存在于trie中：
- 获取根的子级
- 遍历字符串的每个字符
- 检查该字符是否已存在于子字典树中，如果该字符不在字典树中，则停止搜索并返回false
- 重复第二步和第三步，直到字符串中没有任何字符，如果到达字符串末尾，则返回true
该算法的复杂度为O(n)，其中n表示键的长度。
Java实现如下：
public boolean find(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.getChildren().get(ch);
if (node == null) {
return false;
}
current = node;
}
return current.isEndOfWord();
}
实际操作如下：
@Test
public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() {
Trie trie = createExampleTrie();
assertFalse(trie.containsNode("3"));
assertFalse(trie.containsNode("vida"));
assertTrue(trie.containsNode("life"));
}
3.3 删除元素
除了插入和查找元素之外，显然我们还需要能够删除元素。
对于删除过程，我们需要遵循以下步骤：
- 检查该元素是否已经是trie的一部分
- 如果找到该元素，则将其从trie中移除
该算法的复杂度为O(n)，其中n表示键的长度。
让我们快速看一下实现情况：
public void delete(String word) {
delete(root, word, 0);
}
private boolean delete(TrieNode current, String word, int index) {
if (index == word.length()) {
if (!current.isEndOfWord()) {
return false;
}
current.setEndOfWord(false);
return current.getChildren().isEmpty();
}
char ch = word.charAt(index);
TrieNode node = current.getChildren().get(ch);
if (node == null) {
return false;
}
boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord();
if (shouldDeleteCurrentNode) {
current.getChildren().remove(ch);
return current.getChildren().isEmpty();
}
return false;
}
实际操作如下：
@Test
void whenDeletingElements_ThenTreeDoesNotContainThoseElements() {
Trie trie = createTrie();
assertTrue(trie.containsNode("Programming"));
trie.delete("Programming");
assertFalse(trie.containsNode("Programming"));
}
4. 总结
在本文中，我们简要介绍了trie数据结构及其最常见的操作及其实现。
Post Directory
