简介
Trie树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中保存的通常是字符串。
核心知识
空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。
构建流程图解
其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串(注意:红色节点并不都是叶子节点)。
存储方式
class TrieNode {
TrieNode preNode = null;//父母节点
boolean isEnd = false;//是否是红点，也就是是否是word的结尾
int deep = 0;//做hash使用，防止一个单词里面有多个char的时候hash是一样的，可能导致删除出错
char content = 0;//当前节点存储的字母
LinkedList<TrieNode> child = new LinkedList<>();//子节点，当前节点后续节点
}
1.preNode：父母节点
2.isEnd ：是否是红点，也就是是否是word的结尾
3.deep ：做hash使用，防止一个单词里面有多个char的时候hash是一样的，可能导致删除出错
4.content ：当前节点存储的字母
5.child：子节点，当前节点后续节点
节点的删除操作
所以移除word，三种情况：
word在list中不存在，直接返回失败word最后一个char 没有child，则删掉此节点。并向上往 root 查找没有孩子 && isEnd=false 的节点都删掉word最后一个char 有child，则把isEnd置为false
代码实现
package wgzyx;
import java.util.LinkedList;
public class TrieTree {
private TrieNode root = new TrieNode();
class TrieNode {
TrieNode preNode = null;
boolean isEnd = false;
int deep = 0;//做hash使用，防止一个单词里面有多个char的时候hash是一样的，可能导致删除出错
char content = 0;
LinkedList<TrieNode> child = new LinkedList<>();
TrieNode() {
}
TrieNode(char content) {
this.content = content;
}
@Override
public String toString() {
String reg = "";
reg+=content;
reg+=" deep=";
reg+=deep;
reg+=" isEnd=";
reg+=String.format("%5s",isEnd);
reg+=" child=";
for(TrieNode temp:child) {
if(temp!=null) {
reg+=" ";
reg+=temp.content;
}
}
return reg;
}
@Override
public int hashCode() {
return content + deep;
}
@Override
public boolean equals(Object obj) {
return obj instanceof TrieNode && (((TrieNode) obj).content == content);
}
void setPreNode(TrieNode node) {
preNode = node;
}
TrieNode getPreNode() {
return preNode;
}
/**
* child中删掉某个Node
*
* @param node 需要删掉的node
*/
void removeChild(TrieNode node) {
for (TrieNode aChild : child) {
if (aChild.content == node.content) {
child.remove(aChild);
break;
}
}
}
/**
* child中是否有此Node
*
* @param character 保存的char
* @return 存在返回不存在返回Null
*/
TrieNode getNode(Character character) {
for (TrieNode aChild : child) {
if (aChild.content == character) {
return aChild;
}
}
return null;
}
}
/**
* 添加一个word
* apple
*
* @param word 需要添加的词
*/
public void addWord(String word) {
int deep = 0;
TrieNode currNode = root;
while (deep < word.length()) {
/*
* 判断当前node的child，如果为空直接添加，不为空，查找是否含有，不含有则添加并设为currNode，含有则找到并设置为currNode
*/
char c = word.charAt(deep);
if (currNode.child.contains(new TrieNode(c))) {
currNode = currNode.getNode(c);
} else {
TrieNode node = new TrieNode(c);
node.setPreNode(currNode);
node.deep = deep + 1;
currNode.child.add(node);
currNode = node;
}
if (deep == word.length() - 1) {
currNode.isEnd = true;
}
deep++;
}
}
/**
* word在map中是否存在
*
* @param word 需要查找的word
* @return 是否存在
*/
public boolean hasWord(String word) {
int deep = 0;
TrieNode currNode = root;
while (deep < word.length()) {
char c = word.charAt(deep);
if (currNode.child.contains(new TrieNode(c))) {
currNode = currNode.getNode(c);
} else {
return false;
}
if (deep == word.length() - 1) {
return currNode.isEnd;
}
deep++;
}
return false;
}
/**
* 移除word，几种情况：
* 1、word在list中不存在，直接返回失败
* 2、word最后一个char 没有child，则删掉此节点并朝 root 查找没有孩子 && isEnd=false 的节点都删掉
* 3、word最后一个char 有child，则把isEnd置为false
*
* @param word 需要移除的word
* @return 是否移除成功
*/
public boolean removeWord(String word) {
if (word == null || word.trim().equals("")) {
return false;
}
if (hasWord(word)) {
return false;
}
int deep = 0;
TrieNode currNode = root;
while (deep < word.length()) {
char c = word.charAt(deep);
if (currNode.child.contains(new TrieNode(c))) {
currNode = currNode.getNode(c);
} else {
return false;
}
if (deep == word.length() - 1) {
if (currNode.child.size() > 0) {
//3、word最后一个char 有child，则把isEnd置为false
currNode.isEnd = false;
return true;
} else {
//2、word最后一个char 没有child，则删掉此节点并朝 root 查找没有child && isEnd=false 的节点都删掉
TrieNode parent = currNode.getPreNode();
while (parent != null) {
if (parent.child.size() == 0 && !parent.isEnd) {
parent.removeChild(currNode);
currNode = parent;
} else {
return true;
}
}
}
}
deep++;
}
return false;
}
/**
* 前序遍历所有节点
*/
public void traverseTree() {
visitNode(root, "");
}
private void visitNode(TrieNode node, String result) {
//显示每个节点的字母
System.out.println("node.content->" + node.toString());
String re = result + node.content;
//到此节点组成的单词
// System.out.println("result->" + re);
for (TrieNode n : node.child) {
visitNode(n, re);
}
}
}
文章参考：
https://www.jianshu.com/p/183649a2150e
https://www.jianshu.com/p/6c8b18c5947b
网友评论