Trie
2021-02-01 本文已影响0人
code希必地
1、概述
- 1、Trie又叫前缀树、字典树、单词查找树。
- 2、Trie搜索字符串的效率主要和搜索字符串的长度有关。
- 3、假设使用Trie存储cat、dog、doggy、does、cast、add六个单词。
image.png
上图中红色表示是一个完整单词的结尾。从上图可知：
- 1、Trie是一个多叉树。
- 2、每个字符都对应一个节点。
- 3、存储的单词是不可能重复的。类似于一个Set一样
2、接口设计
public class Trie<V> {
private int size;
// 返回前缀树中单词的数量
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
size = 0;
}
/**
* @param key
* @return 是否包含某个单词
*/
public boolean contains(String key) {
return false;
}
/**
* 返回key对应的value
* @param key
* @return
*/
public V get(String key) {
return null;
}
/**
* @param key
* @param value
* @return 返回旧的value
*/
public V add(String key, V value) {
return null;
}
/**
* 删除前缀中中存储的单词str并返回对应的value
*
* @param key
* @return
*/
public V remove(String key) {
return null;
}
/**
* 返回前缀树中是否存储有prefix前缀的单词
*
* @param prefix
* @return
*/
public boolean startWith(String prefix) {
return false;
}
}
- 1、既然前缀树的逻辑结构是一个多叉树，那么就需要节点Node。节点中需要存储parent、char、isWord（是否是单词的结尾）、value（value存入单词结尾的节点中，不需要每个节点都存）等信息。
- 2、Trie是一个多叉树，如何维护节点的子树呢？从上图中可知，每个字符对应一个节点，所以这里我们可以使用HashMap<Character,Node>来维护子树。故在Node中增加一个属性：HashMap<Character,Node> children。
private static class Node<V> {
Node<V> parent;
HashMap<Character, Node<V>> children;
Character c;
V value;
// 是否是一个完整单词
boolean isWord;
public Node(Node<V> parent) {
this.parent = parent;
}
}
2.1、get(String key) 和 contains(String key)
方法get()和contains()实现的功能类似，这里可以定义一个方法node(String key)用于获取key对应Node。
/**
* 返回key对应的Node
*
* @param key
* @return
*/
private Node<V> node(String key) {
keyCheck(key);
Node<V> node = root;
int len = key.length();
for (int i = 0; i < len; i++) {
if (node == null || node.children == null || node.children.isEmpty())
return null;
char c = key.charAt(i);
node = node.children.get(c);
}
return node;
}
/**
* @param key
* @return 是否包含某个单词
*/
public boolean contains(String key) {
Node<V> node = node(key);
return node != null && node.isWord;
}
/**
* 返回key对应的value
*
* @param key
* @return
*/
public V get(String key) {
Node<V> node = node(key);
return node != null && node.isWord ? node.value : null;
}
2.2、add(String key, V value)
添加需要遍历key中的字符，如果找不到字符对应的节点就需要创建新的节点，如果之前已经存在单词key，那么就需要对value进行覆盖，如果不是完整的单词需要修改isWorld=true。
/**
* @param key
* @param value
* @return 返回旧的value
*/
public V add(String key, V value) {
keyCheck(key);
// 创建根节点
if (root == null)
root = new Node<>(null);
int len = key.length();
Node<V> node = root;
for (int i = 0; i < len; i++) {
if (node.children == null)
node.children = new HashMap<>();
char c = key.charAt(i);
Node<V> childeNode = node.children.get(c);
if (childeNode == null) {
childeNode = new Node<>(node);
childeNode.character = c;
node.children.put(c, childeNode);
}
node = childeNode;
}
// 单词已经存在
if (node.isWord) {
V oldValue = node.value;
node.value = value;
return oldValue;
}
// 新增一个单词
node.isWord = true;
node.value = value;
size++;
return null;
}
2.3、startWith(String prefix)
该方法是判断是否有前缀为prefix的Node，并不要求prefix是一个完整的单词，所以这里可以使用node(String key)实现
/**
* 返回前缀树中是否存储有prefix前缀的单词
*
* @param prefix
* @return
*/
public boolean startWith(String prefix) {
Node<V> node = node(prefix);
return node != null;
}
2.4、remove(String key)
删除需要先判断下单词是否存在，如果存在且最后一个节点有子节点，那么不能直接删除；否则需要从下向上进行删除，当删除到的节点是另一个单词的末尾或有子节点则不再继续删除。
/**
* 删除前缀树中存储的单词key并返回对应的value
*
* @param key
* @return
*/
public V remove(String key) {
// 找到最后一个节点
Node<V> node = node(key);
// 如果不是单词的末尾不用处理
if (node == null || !node.isWord)
return null;
size--;
V oldValue = node.value;
// 如果node有子节点，说明key是其他单词的一部分所以不能直接删除
if (node.children != null && !node.children.isEmpty()) {
node.isWord = false;
node.value = null;
return oldValue;
}
// 如果node没有子节点，需要从下向上进行删除
Node<V> parent = null;
while ((parent = node.parent) != null) {
parent.children.remove(node.character);
if (parent.isWord || !parent.children.isEmpty())
break;
node = parent;
}
return oldValue;
}
3、完整代码
public class Trie<V> {
private int size;
private Node<V> root;
// 返回前缀树中单词的数量
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
size = 0;
}
/**
* @param key
* @return 是否包含某个单词
*/
public boolean contains(String key) {
Node<V> node = node(key);
return node != null && node.isWord;
}
/**
* 返回key对应的value
*
* @param key
* @return
*/
public V get(String key) {
Node<V> node = node(key);
return node != null && node.isWord ? node.value : null;
}
/**
* @param key
* @param value
* @return 返回旧的value
*/
public V add(String key, V value) {
keyCheck(key);
// 创建根节点
if (root == null)
root = new Node<>(null);
int len = key.length();
Node<V> node = root;
for (int i = 0; i < len; i++) {
if (node.children == null)
node.children = new HashMap<>();
char c = key.charAt(i);
Node<V> childeNode = node.children.get(c);
if (childeNode == null) {
childeNode = new Node<>(node);
childeNode.character = c;
node.children.put(c, childeNode);
}
node = childeNode;
}
// 单词已经存在
if (node.isWord) {
V oldValue = node.value;
node.value = value;
return oldValue;
}
// 新增一个单词
node.isWord = true;
node.value = value;
size++;
return null;
}
/**
* 删除前缀中中存储的单词str并返回对应的value
*
* @param key
* @return
*/
public V remove(String key) {
// 找到最后一个节点
Node<V> node = node(key);
// 如果不是单词的末尾不用处理
if (node == null || !node.isWord)
return null;
size--;
V oldValue = node.value;
// 如果node有子节点，说明key是其他单词的一部分所以不能直接删除
if (node.children != null && !node.children.isEmpty()) {
node.isWord = false;
node.value = null;
return oldValue;
}
// 如果node没有子节点，需要从下向上进行删除
Node<V> parent = null;
while ((parent = node.parent) != null) {
parent.children.remove(node.character);
if (parent.isWord || !parent.children.isEmpty())
break;
node = parent;
}
return oldValue;
}
/**
* 返回前缀树中是否存储有prefix前缀的单词
*
* @param prefix
* @return
*/
public boolean startWith(String prefix) {
Node<V> node = node(prefix);
return node != null;
}
/**
* 返回key对应的Node
*
* @param key
* @return
*/
private Node<V> node(String key) {
keyCheck(key);
Node<V> node = root;
int len = key.length();
for (int i = 0; i < len; i++) {
if (node == null || node.children == null || node.children.isEmpty())
return null;
char c = key.charAt(i);
node = node.children.get(c);
}
return node;
}
private void keyCheck(String key) {
if (key == null || key.length() == 0)
throw new IllegalArgumentException("key must be not null");
}
private static class Node<V> {
Node<V> parent;
HashMap<Character, Node<V>> children;
Character character;
// 当Node对应的是单词的末尾，将key对应的value存入Node中
V value;
// 是否是一个完整单词
boolean isWord;
public Node(Node<V> parent) {
this.parent = parent;
}
}
}
总结：
- 1、Trie的优点：搜索字符串主要和字符串的长度有关。
- 2、Trie的缺点：占用内存较大，每个字符都要创建一个Node对象。
