JAVA 字典树算法 实现

发布时间:2024-01-31 10:01:11

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

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

2. 2.1字典树的基本概念 字典树的定义

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

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

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

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表示节点是否为字符串的结尾。

3.2 插入字典树

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

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;    }}
3.3 搜索字典树的操作

搜索操作从字典树的根节点开始,逐步搜索字符。如果某个节点的子节点中没有当前字符,请返回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;    }}
3.4 删除字典树

删除操作类似于插入操作。从字典树的根节点逐步找到字符。在找到字符串的最后一个字符所在的节点后,将其删除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;    }}
4. 流程图

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

flowchart TD    subgraph 字典树

上一篇 JAVA 线程池 子线程 interrupt
下一篇 JAVA8 判断一个日期是否在今天之后

文章素材均来源于网络,如有侵权,请联系管理员删除。

标签: Java教程Java基础Java编程技巧面试题Java面试题