字典树

概念

字典树，也称为前缀树（Trie树），是一种用于存储和管理一组字符串数据的树状数据结构。字典树的主要特点是能够有效地支持字符串的插入和查找操作，以及高效地完成具有相同前缀的字符串的检索。

字典树是一种多叉树结构，每个节点代表一个字符，根节点通常为空。从根节点到某个节点的路径上的字符连接起来即构成一个字符串。

模板

添加和搜索操作的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Trie {
    class TrieNode {
        boolean end;
        // int cnt;  // 维护节点数量
        TrieNode[] children = new TrieNode[26];
    }
    TrieNode root = new TrieNode();
    void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int index = (int) c - 97;
            if (cur.children[index] == null) {
                cur.children[index] = new TrieNode();
            }
            cur = cur.children[index];
        }
        cur.end = true;
    }
    boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int index = (int) c - 97;
            if (cur.children[index] == null) return false;
            cur = cur.children[index];
        }
        return cur.end;
    }
}

带有删除操作的模板

通过递归的方式删除word

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Trie {
    class TrieNode {
        boolean end;
        // int cnt;  // 维护节点数量
        TrieNode[] children = new TrieNode[26];
    }
    TrieNode root = new TrieNode();
    void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int index = (int) c - 97;
            if (cur.children[index] == null) {
                cur.children[index] = new TrieNode();
            }
            cur = cur.children[index];
        }
        cur.end = true;
    }
    boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int index = (int) c - 97;
            if (cur.children[index] == null) return false;
            cur = cur.children[index];
        }
        return cur.end;
    }
    public void delete(String word) {
        deleteHelper(root, word, 0);
    }
    private boolean deleteHelper(TrieNode node, String word, int depth) {
        if (node == null) return false;
        if (depth == word.length()) {
            if (!node.end) return false;
            node.end = false;
            return allNull(node.children);  // If the current node has no other children, it can be safely removed.
        }
        int index = word.charAt(depth) - 'a';
        if (deleteHelper(node.children[index], word, depth + 1)) {  // After the recursive call, the child node can be safely removed.
            node.children[index] = null;
            return !node.end && allNull(node.children);
        }
        return false;
    }
    private boolean allNull(TrieNode[] arr) {
        for (TrieNode node : arr) {
            if (node != null) return false;
        }
        return true;
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();

        // Insert words
        trie.insert("apple");
        trie.insert("app");
        trie.insert("banana");

        // Search words
        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("app"));     // true
        System.out.println(trie.search("orange"));  // false

        // Delete words
        trie.delete("apple");
        System.out.println(trie.search("apple"));   // false
        System.out.println(trie.search("app"));     // true
    }
}

相关题解