字典树也叫前缀树用法

2023-04-24 15:51| 来源: 网络整理| 查看: 265

字典树

Trie树叫字典树也叫前缀树是一种多叉树形结构，是哈希树的变种。

Tire树典型应用于快速体检索，统计，排列和保存大量的字符串。其优点是最大限度减少无谓的字符串比较，查询效率比较高。

Tire树的核心思想是空间换时间，利用字符串的公共前缀和来降低查询时间的开销提高效率。

Tire树的三个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。

从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

每个节点的所有子节点包含的字符都不相同。

有点不好理解就想，一棵树开了26个枝丫，有的有果子，有的没有，每个枝丫上还有26个小枝以此类推。

可以把Trie树看成一个最多26叉树，每个节点的子节点可以最多有有26个。

public class Trie { private Trie[] children; private boolean isEnd; public Trie() { children = new Trie[26];//表示26个字母子节点 isEnd = false; } public void insert(String word) { Trie node = this;//指向当前的根节点 for (int i = 0; i node.children[index] = new Trie();//插入这个字母 } node = node.children[index];//指向对应的子节点 } node.isEnd = true;//记录单词结束位置 } //查询单词是否在Trie树中 public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } //查询单词的前缀prefix是否在Trie树中。 public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } //查询单词前缀和是否在Trie树中。 private Trie searchPrefix(String prefix) { Trie node = this; for (int i = 0; i return null; } node = node.children[index]; } return node; } }

【本文地址】

公司简介

联系我们