JAVA 字典树算法 实现

JAVA 实现字典树算法1. 引言

字典树（Trie Tree），前缀树或字典树也被称为处理字符串匹配问题的数据结构。它能有效地支持字符串的插入、删除和搜索，是解决许多字符串问题的有力工具。本文将介绍字典树的基本概念和实现方法，并提供JAVA代码示例。

字典树是一种多叉树，每个节点都包含一个字符和指向子节点的指针。根节点不包含字符，每个非根节点的字符都是其父节点字符的后缀。字典树的每条路径都代表一个字符串，从根节点连接到某个节点的路径是节点所代表的字符串。

• 共享前缀:字典树中的节点可以共享相同的前缀，节省空间。
• 高效搜索：字典树可以使用字符串的前缀进行搜索，时间复杂度为O(k)，k是字符串的长度。
• 插入和删除操作的时间复杂度为O(k)，与字符串的长度成正比。

首先，我们需要定义字典树的节点类，包括字符和指向子节点的指针。

class TrieNode {    private char val;    private TrieNode[] children;    private boolean isEnd;    public TrieNode(char val) {        this.val = val;        this.children = new TrieNode[26];        this.isEnd = false;    }}

其中，val表示节点的字符值，children用于存储指向子节点的指针是一个长度为26的数组，isEnd表示节点是否为字符串的结尾。

接下来，我们将实现字典树的插入操作。插入操作从字典树的根节点逐步插入字符。如果某个节点的子节点中没有当前字符，则建立一个新的节点并插入。

class Trie {    private TrieNode root;    public Trie() {        this.root = new TrieNode('/');    }    public void insert(String word) {        TrieNode node = root;        char[] chars = word.toCharArray();        for (char c : chars) {            int index = c - 'a';            if (node.children[index] == null) {                node.children[index] = new TrieNode(c);            }            node = node.children[index];        }        node.isEnd = true;    }}

搜索操作从字典树的根节点开始，逐步搜索字符。如果某个节点的子节点中没有当前字符，请返回false。最后，判断最后一个字符所在的节点是否是字符串的结尾。

class Trie {    // ...    public boolean search(String word) {        TrieNode node = root;        char[] chars = word.toCharArray();        for (char c : chars) {            int index = c - 'a';            if (node.children[index] == null) {                return false;            }            node = node.children[index];        }        return node.isEnd;    }}

删除操作类似于插入操作。从字典树的根节点逐步找到字符。在找到字符串的最后一个字符所在的节点后，将其删除isEnd属性为false。

class Trie {    // ...    public void delete(String word) {        TrieNode node = root;        char[] chars = word.toCharArray();        for (char c : chars) {            int index = c - 'a';            if (node.children[index] == null) {                return;            }            node = node.children[index];        }        node.isEnd = false;    }}

以下是字典树插入、搜索和删除操作的流程图：

flowchart TD    subgraph 字典树