一、Trie
1、什么需求需要用到 Trie 这种数据结构的呢？
- 判断一堆不重复的字符串中，是否存在以某个前缀开头的？
- 如果用 Set\Map 存储字符串，都需要遍历所有字符串进行判断，时间复杂度是 O(n)
- 有没有更优的数据结构实现前缀搜索呢？叮叮叮 -
Trie(前缀树、字典树)闪亮登场
2、Trie 是如何存储数据的？
- Trie 也叫做字典树、前缀树(Prefix Tree)、单词查找树
- Trie 搜索字符串的效率主要跟字符串的长度有关
image.png
3、开发一个东西，首先考虑外部需要怎么调用，这是非常重要的思想，要能理解？？？
image.png
4、在实现 Trie 的 remove 功能的时候，发现对不同节点进行删除情况有很多，这时该怎么办（很重要的思想）？
- 面对这种情况比较多的情景，先对各种情况做好分类总结，然后再写代码
5、在实现 Trie 的 remove 的时候，发现找节点的父节点非常麻烦，这时该怎么解决？
- 方法一：遍历的时候记录父节点，这种方式会将思路搞得比较乱，代码也就比较乱
- 方法二：给节点增加一个 parent 属性，这种思想就很棒，借助一个 parent 属性，思路变得非常清晰
6、Trie 的优缺点各是什么（分别说一点）？
-
优点：搜索前缀的效率主要跟前缀的长度有关，效率高 -
缺点：需要耗费大量内存（因为一个字符作为一个节点，节点会很多）
二、补充内容
1、什么是前缀表达式？中缀表达式？后缀表达式？
image.png
2、什么是表达式树？看着树要能手写出前序遍历，中序遍历、后续遍历？树和方程式要能相互转换？（非常重要，借此回顾二叉树）
image.png
3、前序遍历二叉树，非递归思想？
image.png
image.png
4、中序遍历二叉树，非递归思想
image.png
5、后序遍历二叉树，非递归思想
image.png
6、Trie 的代码实现
import java.util.HashMap;
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;
root = null;
}
public V get(String key) {
Node<V> node = node(key);
return node != null && node.word ? node.value : null;
}
public boolean contains(String key) {
Node<V> node = node(key);
return node != null && node.word;
}
public V add(String key, V value) {
keyCheck(key);
// 创建根节点
if (root == null) {
root = new Node<>(null);
}
Node<V> node = root;
int len = key.length();
for (int i = 0; i < len; i++) {
char c = key.charAt(i);
boolean emptyChildren = node.children == null;
Node<V> childNode = emptyChildren ? null : node.children.get(c);
if (childNode == null) {
childNode = new Node<>(node);
childNode.character = c;
node.children = emptyChildren ? new HashMap<>() : node.children;
node.children.put(c, childNode);
}
node = childNode;
}
if (node.word) { // 已经存在这个单词
V oldValue = node.value;
node.value = value;
return oldValue;
}
// 新增一个单词
node.word = true;
node.value = value;
size++;
return null;
}
public V remove(String key) {
// 找到最后一个节点
Node<V> node = node(key);
// 如果不是单词结尾，不用作任何处理
if (node == null || !node.word) return null;
size--;
V oldValue = node.value;
// 如果还有子节点
if (node.children != null && !node.children.isEmpty()) {
node.word = false;
node.value = null;
return oldValue;
}
// 如果没有子节点
Node<V> parent = null;
while ((parent = node.parent) != null) {
parent.children.remove(node.character);
if (parent.word || !parent.children.isEmpty()) break;
node = parent;
}
return oldValue;
}
public boolean startsWith(String prefix) {
return node(prefix) != null;
}
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 not be empty");
}
}
private static class Node<V> {
Node<V> parent;
HashMap<Character, Node<V>> children;
Character character;
V value;
boolean word; // 是否为单词的结尾（是否为一个完整的单词）
public Node(Node<V> parent) {
this.parent = parent;
}
}
}
