Trie(字典树)

0
字数 372
阅读时间 1 分钟

trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie

不携带数据的 Trie 简单实现

package com.github.liuzhuoming23.trie;

import java.util.HashMap;
import java.util.Map;

/**
* trie
*
* @author liuzhuoming
* @version 0.0.1
* @datetime 2019/9/12 15:25
*/
public class Trie {

/**
* root trie node
*/
private TrieNode root = new TrieNode(false, new HashMap<>());

/**
* put word in trie
*
* @param word word
*/
public void put(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.nodes.containsKey(c)) {
node.nodes.put(c, new TrieNode(false, new HashMap<>()));
}
node = node.nodes.get(c);
}
node.containsTail = true;
}

/**
* the trie contains the word
*
* @param word word
* @return true:contains;false:not
*/
public boolean contains(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.nodes.containsKey(c)) {
return false;
}
node = node.nodes.get(c);
}
return node.containsTail;
}

/**
* remove data from trie
*
* @param word word
*/
public void remove(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.nodes.containsKey(c)) {
return;
}
node = node.nodes.get(c);
}
node.containsTail = false;
}
}

/**
* trie node
*
* @author liuzhuoming
* @version 0.0.1
* @datetime 2019/9/12 15:27
*/
class TrieNode {

/**
* contains a word's tail
*/
boolean containsTail;
/**
* trie nodes
*/
Map<Character, TrieNode> nodes;

TrieNode(boolean containsTail, HashMap<Character, TrieNode> nodes) {
this.containsTail = containsTail;
this.nodes = nodes;
}
}

TestCase

package com.github.liuzhuoming23;

import com.github.liuzhuoming23.trie.Trie;
import org.junit.jupiter.api.Test;

/**
* @author liuzhuoming
* @version 0.0.1
* @datetime 2019/9/12 17:17
*/
public class TrieTest {

@Test
public void test01() {
Trie trie = new Trie();
System.out.println(trie.contains("test"));
trie.put("test");
System.out.println(trie.contains("test"));
trie.remove("test");
System.out.println(trie.contains("test"));
}
}

运行结果为:

false
true
false
  1. 在存储空间比较拮据或者字符串重合度比较高的场景下可以使用 Trie(比如 汉字词组,英语单词 的匹配),否则使用 HashMap 就可以了;
  2. 绑定数据需要在 TrieNode 添加新属性并添加根据 word 获取数据的方法,很简单就不演示了,还是演示一下绑定数据和测试示例吧。

携带数据的 Trie 简单实现

package com.github.liuzhuoming23.trie;

import java.util.HashMap;
import java.util.Map;

/**
* trie
*
* @author liuzhuoming
* @version 0.0.1
* @datetime 2019/9/12 15:25
*/
public class Trie<V> {

/**
* root trie node
*/
private TrieNode<V> root = new TrieNode<>(false, new HashMap<>());

/**
* put word:data in trie
*
* @param word word
* @param data data
*/
public void put(String word, V data) {
TrieNode<V> node = root;
for (char c : word.toCharArray()) {
if (!node.nodes.containsKey(c)) {
node.nodes.put(c, new TrieNode<V>(false, new HashMap<>()));
}
node = node.nodes.get(c);
}
node.containsTail = true;
node.data = data;
}

/**
* get data by word from the trie
*
* @param word word
*/
public V get(String word) {
TrieNode<V> node = root;
for (char c : word.toCharArray()) {
if (!node.nodes.containsKey(c)) {
return null;
}
node = node.nodes.get(c);
}
return node.containsTail ? node.data : null;
}

/**
* the trie contains the word
*
* @param word word
* @return true:contains;false:not
*/
public boolean contains(String word) {
TrieNode<V> node = root;
for (char c : word.toCharArray()) {
if (!node.nodes.containsKey(c)) {
return false;
}
node = node.nodes.get(c);
}
return node.containsTail;
}

/**
* remove data from trie
*
* @param word word
*/
public void remove(String word) {
TrieNode<V> node = root;
for (char c : word.toCharArray()) {
if (!node.nodes.containsKey(c)) {
return;
}
node = node.nodes.get(c);
}
node.containsTail = false;
node.data = null;
}
}

/**
* trie node
*
* @author liuzhuoming
* @version 0.0.1
* @datetime 2019/9/12 15:27
*/
class TrieNode<V> {

/**
* contains a word's tail
*/
boolean containsTail;
/**
* mount data
*/
V data;
/**
* trie nodes
*/
Map<Character, TrieNode<V>> nodes;

/**
* just for construct root node
*
* @param containsTail containsTail
* @param nodes nodes
*/
TrieNode(boolean containsTail, HashMap<Character, TrieNode<V>> nodes) {
this.containsTail = containsTail;
this.nodes = nodes;
}
}

TestCase

package com.github.liuzhuoming23;

import com.github.liuzhuoming23.trie.Trie;
import java.util.Arrays;
import org.junit.jupiter.api.Test;

/**
* @author liuzhuoming
* @version 0.0.1
* @datetime 2019/9/12 17:17
*/
public class TrieTest {

@Test
public void test01() {
Trie<String[]> trie = new Trie<>();
System.out.println(trie.contains("test"));
trie.put("test", new String[]{"测试"});
System.out.println(trie.contains("test"));
System.out.println(Arrays.toString(trie.get("test")));
trie.put("test", new String[]{"@测试", "@Test"});
System.out.println(Arrays.toString(trie.get("test")));
trie.remove("test");
System.out.println(Arrays.toString(trie.get("test")));
}
}

运行结果为:

false
true
[测试]
[@测试, @Test]
null

参考来源

  1. Trie - 维基百科,自由的百科全书

系列文章 #数据结构与算法

(1)Bloom filter(布隆过滤器)

(2)Trie(字典树)

(3)岛屿问题(扫雷)

(4)HOTP&TOTP(短信验证码&两步验证码)


打包Github的项目上传到Maven中央仓库 监控中心-Admin