一、Trie 字典树
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。[wikipedia]
Trie的典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。[百度百科]
红色节点表示一个单词的结尾。
二、节点的设计
第一版
每个节点包含该节点的值，是否为单词的结尾，该节点的子节点。设计如下：
class Node{
private boolean isWord;
private char val;
private char[26] next;
}
问题所在：
- 多余的val，实际上指向该节点的引用中就包含了该节点的值是多少 ，所以val是多余的；
- 使用数组不合理，实际需求中不可能只有26个字母，也许有大小写，也许有其他符号，所以需要使用其他数据结构。
第二版
class Node{
public boolean isWord;
public Map<Character,Node> next;
}
舍去了val，将指向下一节点的引用放在map里。此时暂时只考虑英文字符不考虑其他语言（中文等等）。
三、Trie的实现
3.1 Trie的基础实现
public class Trie {
private class Node{
//true表示一个单词结尾，false表示非单词结尾
private boolean isWord;
//k表示单词的组成字符, Node表示组成单词的剩余字符
private Map<Character, Node> next;
public Node(){
this(false);
}
public Node(boolean isWord){
this.isWord = isWord;
this.next = new TreeMap<>();
}
}
//Trie数据结构的根节点
private Node root;
//Trie存储个多少个单词
private int size;
//初始化Trie, root节点不存储数据
public Trie(){
this.root = new Node();
this.size = 0;
}
/**
* 获得Trie中存储的单词数量
* @return
*/
public int getSize(){
return size;
}
}
3.2 添加元素
- 往Trie 字典树中添加节点，步骤如图所示：
/**
* 向Trie中添加一个新的单词word
* @param word
*/
public void add(String word){
//从根节点开始添加单词
Node cur = root;
for (int i = 0; i < word.length(); i++) {
//提取单词中的字母
char ch = word.charAt(i);
//如果root.next指向的TreeMap中不包含ch
if(cur.next.get(ch) == null){
//直接创建一个新的节点映射
cur.next.put(ch, new Node());
}
//存在ch节点，移动cur，继续查找下一字符的映射节点，重复循环
cur = cur.next.get(ch);
}
//如果不存在该单词，存在的话size不能加1
if(!cur.isWord){
//循环完成之后，表示单词添加成功
cur.isWord = true;
size++;
}
}
3.3 查找单词
- 查询Trie中是否包含该单词。
/**
* 查询单词word是否在Trie中
* @param word
* @return
*/
public boolean contains(String word){
//从根节点开始
Node cur = root;
for (int i = 0; i < word.length(); i++) {
//提取单词中的字母
char ch = word.charAt(i);
//如果root.next指向的TreeMap中不包含ch
if(cur.next.get(ch) == null){
//直接返回false
return false;
}
//存在ch节点，移动cur，继续查找下一字符的映射节点，重复循环
cur = cur.next.get(ch);
}
//直接返回cur.isWord
// 如果不存在该单词,该值为false, 存在则返回true
return cur.isWord;
}
3.4 判断前缀
- 查询是否在Trie中有单词以prefix为前缀。
- 与查询单词方法大同小异。
/**
* 查询是否在Trie中有单词以prefix为前缀
* @param prefix
* @return
*/
public boolean isPrefix(String prefix){
//从根节点开始
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
//提取单词中的字母
char ch = prefix.charAt(i);
//如果root.next指向的TreeMap中不包含ch
if(cur.next.get(ch) == null){
//直接返回false
return false;
}
//存在ch节点，移动cur，继续查找下一字符的映射节点，重复循环
cur = cur.next.get(ch);
}
//循环走完，则表示Trie中有单词以prefix为前缀
return true;
}
3.5 删除单词
删除节点的情况共有如下四种情况：
- 情况一：逐一将节点去除即可；
- 情况二：直接将isWord置为false即可；
- 情况三：逐一删除节点，如果待删除节点是另外一个单词结尾则停止删除；
- 情况四：逐一删除节点，但是如果待删除节点还有其他孩子节点则停止删除。
/**
* 删除Trie中word单词
* @param word
*/
public void delete(String word){
//删除前查找是否存在这个单词，存在才能删除
if(!contains(word)){
//不存在该单词，直接返回
return;
}
Stack<Node> preNodes = new Stack<>();
//存在word单词
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
//添加前驱节点
preNodes.push(cur);
cur = cur.next.get(ch);
}
//到了单词末尾，节点是叶子节点
if(cur.next.size() == 0){
for (int i = word.length() - 1; i >= 0; i--) {
char ch = word.charAt(i);
//获得前驱节点
Node pre = preNodes.pop();
//判断是否为其他单词的结尾，是则停止删除节点
//判断待删除节点是否还有其他孩子，有则停止删除节点
if((i != word.length() - 1 && pre.next.get(ch).isWord) || pre.next.get(ch).next.size() != 0){
break;
}
pre.next.remove(ch);//删除节点
}
}else {
//不是单词末尾，节点不是叶子节点
cur.isWord = false;
}
size--;
}
3.6 Trie完整实现代码
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;
/**
* @Author: huangyibo
* @Date: 2022/2/25 23:03
* @Description: Trie
*/
public class Trie {
private class Node{
//true表示一个单词结尾，false表示非单词结尾
private boolean isWord;
//k表示单词的组成字符, Node表示组成单词的剩余字符
private Map<Character, Node> next;
public Node(){
this(false);
}
public Node(boolean isWord){
this.isWord = isWord;
this.next = new TreeMap<>();
}
}
//Trie数据结构的根节点
private Node root;
//Trie存储个多少个单词
private int size;
//初始化Trie, root节点不存储数据
public Trie(){
this.root = new Node();
this.size = 0;
}
/**
* 获得Trie中存储的单词数量
* @return
*/
public int getSize(){
return size;
}
/**
* 向Trie中添加一个新的单词word
* @param word
*/
public void add(String word){
//从根节点开始添加单词
Node cur = root;
for (int i = 0; i < word.length(); i++) {
//提取单词中的字母
char ch = word.charAt(i);
//如果root.next指向的TreeMap中不包含ch
if(cur.next.get(ch) == null){
//直接创建一个新的节点映射
cur.next.put(ch, new Node());
}
//存在ch节点，移动cur，继续查找下一字符的映射节点，重复循环
cur = cur.next.get(ch);
}
//如果不存在该单词，存在的话size不能加1
if(!cur.isWord){
//循环完成之后，表示单词添加成功
cur.isWord = true;
size++;
}
}
/**
* 查询单词word是否在Trie中
* @param word
* @return
*/
public boolean contains(String word){
//从根节点开始
Node cur = root;
for (int i = 0; i < word.length(); i++) {
//提取单词中的字母
char ch = word.charAt(i);
//如果root.next指向的TreeMap中不包含ch
if(cur.next.get(ch) == null){
//直接返回false
return false;
}
//存在ch节点，移动cur，继续查找下一字符的映射节点，重复循环
cur = cur.next.get(ch);
}
//直接返回cur.isWord
// 如果不存在该单词,该值为false, 存在则返回true
return cur.isWord;
}
/**
* 查询是否在Trie中有单词以prefix为前缀
* @param prefix
* @return
*/
public boolean isPrefix(String prefix){
//从根节点开始
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
//提取单词中的字母
char ch = prefix.charAt(i);
//如果root.next指向的TreeMap中不包含ch
if(cur.next.get(ch) == null){
//直接返回false
return false;
}
//存在ch节点，移动cur，继续查找下一字符的映射节点，重复循环
cur = cur.next.get(ch);
}
//循环走完，则表示Trie中有单词以prefix为前缀
return true;
}
/**
* 删除Trie中word单词
* @param word
*/
public void delete(String word){
//删除前查找是否存在这个单词，存在才能删除
if(!contains(word)){
//不存在该单词，直接返回
return;
}
Stack<Node> preNodes = new Stack<>();
//存在word单词
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
//添加前驱节点
preNodes.push(cur);
cur = cur.next.get(ch);
}
//到了单词末尾，节点是叶子节点
if(cur.next.size() == 0){
for (int i = word.length() - 1; i >= 0; i--) {
char ch = word.charAt(i);
//获得前驱节点
Node pre = preNodes.pop();
//判断是否为其他单词的结尾，是则停止删除节点
//判断待删除节点是否还有其他孩子，有则停止删除节点
if((i != word.length() - 1 && pre.next.get(ch).isWord) || pre.next.get(ch).next.size() != 0){
break;
}
pre.next.remove(ch);//删除节点
}
}else {
//不是单词末尾，节点不是叶子节点
cur.isWord = false;
}
size--;
}
}
四、Trie应用
leetcode 211. 添加与搜索单词 - 数据结构设计
import java.util.Map;
import java.util.TreeMap;
/**
* @Author: huangyibo
* @Date: 2022/2/26 0:51
* @Description: leetcode 211. 添加与搜索单词 - 数据结构设计
* 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配
* 实现词典类 WordDictionary ：
*
* WordDictionary() 初始化词典对象
* void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
* bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
*/
public class WordDictionary {
private class Node{
public boolean isword;
public Map<Character,Node> next;
public Node(){
this(false);
}
public Node(boolean isword){
this.isword = isword;
next = new TreeMap<>();
}
}
private Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if(cur.next.get(ch) == null){
cur.next.put(ch,new Node());
}
cur = cur.next.get(ch);
}
if(!cur.isword){
cur.isword = true;
}
}
/**
* Returns if the word is in the data structure.
* A word could contain the dot character '.' to represent any one letter.
*/
public boolean search(String word) {
return match(root,word,0);
}
private boolean match(Node node,String word,int index){
if(index == word.length()){
return node.isword;
}
char ch = word.charAt(index);
if(ch != '.'){
if(node.next.get(ch) == null){
return false;
}
return match(node.next.get(ch),word,index + 1);
}else {
for (Character nextChar : node.next.keySet()) {
if(match(node.next.get(nextChar),word,index + 1)){
return true;
}
}
return false;
}
}
}
leetcode 677. 键值映射
import java.util.Map;
import java.util.TreeMap;
/**
* @Author: huangyibo
* @Date: 2022/2/26 1:04
* @Description: leetcode 677. 键值映射
*
* 设计一个 map ，满足以下几点:
* 字符串表示键，整数表示值
* 返回具有前缀等于给定字符串的键的值的总和
*
* 实现一个 MapSum 类：
* MapSum() 初始化 MapSum 对象
* void insert(String key, int val) 插入 key-val 键值对，
* 字符串表示键 key ，整数表示值 val 。
* 如果键 key 已经存在，那么原来的键值对 key-value 将被替代成新的键值对。
* int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
*
*/
public class MapSum {
private class Node{
public int value;
public Map<Character,Node> next;
public Node(){
this(0);
}
public Node(int value){
this.value = value;
next = new TreeMap<>();
}
}
private Node root;
/** Initialize your data structure here. */
public MapSum() {
root = new Node();
}
public void insert(String key, int val) {
Node cur = root;
for (int i = 0; i < key.length(); i++) {
char ch = key.charAt(i);
if(cur.next.get(ch) == null){
cur.next.put(ch,new Node());
}
cur = cur.next.get(ch);
}
cur.value = val;
}
public int sum(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
if(cur.next.get(ch) == null){
return 0;
}
cur = cur.next.get(ch);
}
return sum(cur);
}
private int sum(Node node){
int res = node.value;
for (Character ch : node.next.keySet()) {
res += sum(node.next.get(ch));
}
return res;
}
}
参考：
https://blog.csdn.net/qq_25343557/article/details/88797312
网友评论