Trie树

Trie 树，也称为字典树或前缀树，是一种用于存储和检索字符串集合的数据结构。它的主要优势是可以高效地进行字符串的插入、删除和搜索操作，特别适用于大量字符串的快速查找。Trie 树的基本思想是将字符串按照字符逐层存储，每个节点代表一个字符，从根节点到叶子节点的路径表示一个完整的字符串。

以下是一个简单的 Java 实现示例：

class TrieNode {
    private final int ALPHABET_SIZE = 26;
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[ALPHABET_SIZE];
        isEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 输出 true
        System.out.println(trie.search("app"));     // 输出 false
        System.out.println(trie.startsWith("app")); // 输出 true
        trie.insert("app");
        System.out.println(trie.search("app"));     // 输出 true
    }
}

在这个示例中，我们创建了一个 TrieNode 类来表示 Trie 树的节点。每个节点都包含一个字符数组作为子节点，并有一个标志来指示当前节点是否是一个单词的结尾。然后，我们创建了一个 Trie 类来实现 Trie 树的插入、搜索和前缀搜索功能。

请注意，这只是 Trie 树的一个简单实现示例。在实际应用中，您可能需要进行更多的优化和功能扩展，以适应特定的需求。