字典树（Trie树）的Java实现
先上张图，从百度百科盗过来的。
字典树
又称单词查找树，是一种[树形结构]，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。
图中红点表示有单词结尾，比如两个单词app跟apple，其实apple是涵盖了app的，所以必须得有一个End来表示单词是否结尾，一个end来表示一个单词。
这里我们用Java来模拟一个Trie树
class TrieNode {
TrieNode preNode = null;
boolean isEnd = false;
int deep = 0;//做hash使用，防止一个单词里面有多个char的时候hash是一样的，可能导致删除出错
char content = 0;
LinkedList child = new LinkedList<>();
}
其实就几个必要的东西：
1. isEnd：是否是红点，也就是是否是word的结尾
2. content：当前节点到parent节点存储的字母
3. LinkedList
其实字典树最常见的两个操作是 查询 跟 添加 操作，其实就是很简单的逻辑了，代码贴在下面。
稍微复杂些的是删除的操作，比如我有这么一个树，树中有这么两个单词apple跟app：
字典树
如果我需要删除 app这个单词，我只需要把 红点 p这个节点由红色变为白色就好了，就可以了。
但如果我需要删掉apple，那我要做的不止要把e变为白色，还需要找到父节点l，把l也删掉。
当然如果我要删掉apk这个树中不存在的单词，显然也是失败的。
所以移除word，三种情况：
- word在list中不存在，直接返回失败
- word最后一个char 没有child，则删掉此节点并朝 root 查找没有child && isEnd=false 的节点都删掉
- word最后一个char 有child，则把isEnd置为false
而为了能找到父节点，我在Node中加了个parentNode属性，可能还有更好的解决办法。
还有个稍微复杂些的是遍历操作，树的遍历需要用到递归，说到递归，就得想到回溯法，可以看一下我写的回溯法的一个文章。
import util.LogUtil;
import java.util.LinkedList;
/**
* Created by yocn on 2019/6/13.
* 字典树实现
*/
public class TrieTree {
private TrieNode root = new TrieNode();
public void test() {
addWord("abc");
addWord("abcd");
addWord("abe");
// addWord("akl");
// addWord("apple");
// addWord("world");
// addWord("word");
// traverseTree();
// removeWord("abcd");
removeWord("abc");
traverseTree();
}
static class TrieNode {
TrieNode preNode = null;
boolean isEnd = false;
int deep = 0;//做hash使用，防止一个单词里面有多个char的时候hash是一样的，可能导致删除出错
char content = 0;
LinkedList child = new LinkedList<>();
TrieNode() {
}
TrieNode(char content) {
this.content = content;
}
@Override
public String toString() {
return "/n" + "{" +
"End=" + isEnd +
", d=" + deep +
", c=" + content +
", c=" + child +
'}';
}
public String toSimpleString() {
return "/n" + "{" +
"End=" + isEnd +
", d=" + deep +
", c=" + content +
'}';
}
@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 查找没有child && 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) {
// 把isEnd置为false
currNode.isEnd = false;
if (currNode.child.size() > 0) {
//3、word最后一个char 有child，结束
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;
parent = currNode.preNode;
} else {
parent.removeChild(currNode);
return true;
}
}
}
}
deep++;
}
return false;
}
/**
* 前序遍历所有节点，需要用到回溯法
*/
public void traverseTree() {
visitNode(root, "");
}
private void visitNode(TrieNode node, String result) {
LogUtil.Companion.d(node.toSimpleString());
String re = result + node.content;
for (TrieNode n : node.child) {
visitNode(n, re);
// LogUtil.Companion.d("result->" + re);
}
}
}
共有 0 条评论