Trie数据结构在Java中的实现

1. 概述

数据结构是计算机编程中的核心资产，掌握何时及为何使用它们至关重要。本文将简要介绍字典树（Trie）（发音为"try"）数据结构、其实现及复杂度分析。

2. 字典树（Trie）

字典树是一种离散数据结构，虽然典型算法课程中不常提及，但仍是重要工具。它也被称为数字树（digital tree）、基数树（radix tree）或前缀树（prefix tree）（因支持前缀搜索而得名），是一种有序树结构，能高效利用其存储的键（通常是字符串）。

核心特性

• 节点位置定义键：节点的位置决定了其关联的键，这与二叉搜索树不同（后者节点仅存储自身键值）
• 公共前缀共享：节点的所有后代共享该节点关联字符串的公共前缀，根节点关联空字符串
• 多分支结构：不同于二叉搜索树（每个节点固定两个子节点），字典树节点可有多个子节点

节点设计

public class TrieNode {
    private HashMap<Character, TrieNode> children;
    private String content;
    private boolean isWord;
    
    // ...
}

字典树结构

public class Trie {
    private TrieNode root;
    //...
}

3. 常见操作

下面实现字典树的三大核心操作：插入、查找和删除。

3.1 插入元素

算法步骤：

1. 从根节点开始遍历
2. 逐个字符处理待插入单词
3. 若当前字符已存在于子节点，则移动到该节点；否则创建新节点
4. 重复直到单词结束，标记单词结束标志

时间复杂度：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);
}

使用示例：

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

验证测试：

@Test
public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() {
    Trie trie = createTrie();

    assertFalse(trie.isEmpty());
}

3.2 查找元素

算法步骤：

1. 从根节点开始
2. 逐个字符遍历字符串
3. 若字符不存在于当前子节点，立即返回false
4. 成功遍历所有字符后，检查单词结束标志

时间复杂度：O(n)，n为键长度

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 删除元素

算法步骤：

1. 先验证元素是否存在
2. 递归删除路径上的无用节点（需满足：非其他单词前缀且无子节点）

时间复杂度：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. 总结

本文介绍了字典树的核心概念及三大操作的Java实现。字典树在前缀搜索、自动补全等场景中表现优异，尤其适合字符串集合的高效处理。

完整示例代码可在GitHub仓库获取。