Trie 树的基本操作

1. Trie 树概述

Trie（又称字典树、前缀树）是一种树形数据结构，主要用于存储集合中的字符串。Trie 树的每个节点代表一个字符，字符串可以通过从根节点到某个节点的路径来表示。Trie 树在进行字符串的存储、查找和前缀匹配时非常高效，特别适用于处理大量字符串集合的场景，比如自动补全、拼写检查等。

Trie 树的特点

每个节点代表一个字符。
从根节点到某一节点的路径，代表一个字符串。
相同前缀的字符串会共享相同的路径节点。
不同的字符串在树中按字符逐层存储。

2. Trie 树的基本操作

Trie 树的主要操作包括插入字符串、查找字符串、删除字符串以及前缀查找。接下来我们逐一介绍这些基本操作。

2.1 插入操作

插入一个字符串的过程是从根节点开始，逐字符地遍历字符串。如果当前字符的节点不存在，则创建一个新的节点。这个过程保证了相同前缀的字符串会共享相同的路径节点。

2.2 查找操作

查找一个字符串的过程是从根节点开始，逐字符地遍历字符串。如果字符串中某个字符的节点不存在，表示该字符串不在 Trie 树中；如果能够找到字符串的结尾，表示该字符串存在于 Trie 树中。

2.3 删除操作

删除一个字符串的过程稍微复杂一些。首先我们查找到该字符串在 Trie 树中的路径，然后逐层删除节点，直到该路径上的节点不再有其他的子树或没有共享的路径为止。

2.4 前缀查找操作

前缀查找操作用于检查是否存在某个给定前缀的字符串。与查找操作不同的是，前缀查找只需要确保该前缀的路径在 Trie 树中存在即可，而不必关心该前缀是否构成一个完整的字符串。

3. Trie 树的 Java 代码实现

下面我们通过 Java 代码来实现 Trie 树的基本操作。

// 定义 Trie 树节点类
class TrieNode {
    TrieNode[] children; // 子节点
    boolean isEndOfWord; // 是否为单词的结尾

    // 构造函数，初始化一个 Trie 节点
    public TrieNode() {
        children = new TrieNode[26]; // 假设字母仅限小写字母 a-z
        isEndOfWord = false;
    }
}

// 定义 Trie 树类
public class Trie {
    private TrieNode root;

    // 构造函数，初始化 Trie 树
    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; // 如果找不到该字符，返回 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; // 如果找不到前缀，返回 false
            }
            current = current.children[index];
        }

        return true; // 如果遍历完前缀，说明存在该前缀
    }

    // 删除操作
    public boolean delete(String word) {
        return delete(root, word, 0);
    }

    private boolean delete(TrieNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord) {
                return false; // 如果当前节点不是单词结尾，说明要删除的单词不存在
            }
            current.isEndOfWord = false; // 标记为不是单词结尾

            // 如果当前节点没有任何子节点，返回 true，允许删除当前节点
            return isLeafNode(current);
        }

        char c = word.charAt(index);
        int childIndex = c - 'a';
        TrieNode childNode = current.children[childIndex];

        if (childNode == null) {
            return false; // 如果当前字符的节点不存在，返回 false
        }

        boolean shouldDeleteChildNode = delete(childNode, word, index + 1);

        // 如果子节点删除成功，检查当前节点是否可以删除
        if (shouldDeleteChildNode) {
            current.children[childIndex] = null; // 删除子节点

            // 如果当前节点没有任何子节点，并且不是单词结尾，则可以删除
            return !current.isEndOfWord && isLeafNode(current);
        }

        return false;
    }

    private boolean isLeafNode(TrieNode node) {
        for (TrieNode child : node.children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }
}

3.1 代码解释

TrieNode 类是 Trie 树的基本节点类，每个节点包含 26 个指向子节点的指针和一个布尔值 isEndOfWord，用于标记该节点是否为一个单词的结尾。
Trie 类实现了 Trie 树的操作，包括插入、查找、前缀查找和删除操作。
insert 方法逐字符遍历字符串，如果字符对应的子节点不存在，则创建新节点，最终标记单词结尾。
search 方法用来查找某个单词是否存在，返回布尔值。
startsWith 方法用来查找某个前缀是否存在。
delete 方法用于删除一个单词。如果删除成功，返回 true，否则返回 false。