可持久化Trie（Persistent Trie）是一种函数式数据结构，每次修改操作都会创建一个新版本，同时共享未变化的节点。这使得我们可以高效地查询任意历史版本的字符串集合状态，广泛应用于版本控制、离线查询和可持久化数据处理场景。
数据结构原理
普通Trie的每次插入会修改节点。可持久化Trie的核心思想是路径复制：
– 插入新字符串时，从根到插入路径上的每个节点都创建新副本
– 未受影响的分支直接引用旧版本的子节点指针
– 空间复杂度：O(字符串长度 * 字符集大小) 每个版本
核心算法实现
import java.util.*;
/**
* 可持久化Trie（前缀树）
* 支持版本化插入和历史版本查询
*/
public class PersistentTrie {
// 字符集大小：假设为小写字母 a-z
private static final int ALPHABET = 26;
/**
* Trie节点，每个节点记录子节点索引和经过该节点的字符串数量
*/
static class Node {
int[] child; // 子节点指针数组，-1表示空
int count; // 经过该节点的字符串数量
Node() {
this.child = new int[ALPHABET];
Arrays.fill(this.child, -1);
this.count = 0;
}
// 复制构造函数：复制子节点引用和计数
Node(Node other) {
this.child = other.child.clone();
this.count = other.count;
}
}
private final List<Node> nodes; // 节点池，所有版本共享
private final List<Integer> roots; // 每个版本的根节点索引
public PersistentTrie() {
nodes = new ArrayList<>();
roots = new ArrayList<>();
// 版本0：空树
nodes.add(new Node());
roots.add(0);
}
/**
* 在第 (version-1) 版本基础上插入字符串，创建新版本
* @param version 基于的版本号（从1开始）
* @param str 待插入字符串
* @return 新版本号
*/
public int insert(int version, String str) {
int oldRoot = roots.get(version - 1);
int newRoot = cloneNode(oldRoot);
int curOld = oldRoot;
int curNew = newRoot;
// 沿路径复制节点
for (char ch : str.toCharArray()) {
int idx = ch - 'a';
nodes.get(curNew).count++;
int oldChild = nodes.get(curOld).child[idx];
int newChild;
if (oldChild == -1) {
// 旧版本没有该子节点，创建新节点
newChild = createNode();
} else {
// 复制旧子节点
newChild = cloneNode(oldChild);
}
nodes.get(curNew).child[idx] = newChild;
curOld = oldChild == -1 ? 0 : oldChild; // 旧路径继续
curNew = newChild;
}
nodes.get(curNew).count++; // 最后一个节点计数+1
roots.add(newRoot);
return roots.size(); // 返回新版本号
}
/**
* 查询指定版本中是否存在前缀
*/
public boolean startsWith(int version, String prefix) {
int nodeIdx = findNode(version, prefix);
return nodeIdx != -1;
}
/**
* 查询指定版本中以prefix为前缀的字符串数量
*/
public int countPrefix(int version, String prefix) {
int nodeIdx = findNode(version, prefix);
return nodeIdx == -1 ? 0 : nodes.get(nodeIdx).count;
}
/**
* 在指定版本中查找字符串对应的节点索引
*/
private int findNode(int version, String str) {
if (version < 1 || version > roots.size()) return -1;
int cur = roots.get(version - 1);
for (char ch : str.toCharArray()) {
int idx = ch - 'a';
if (nodes.get(cur).child[idx] == -1) return -1;
cur = nodes.get(cur).child[idx];
}
return cur;
}
private int createNode() {
nodes.add(new Node());
return nodes.size() - 1;
}
private int cloneNode(int nodeIdx) {
nodes.add(new Node(nodes.get(nodeIdx)));
return nodes.size() - 1;
}
/**
* 获取当前最新版本号
*/
public int getLatestVersion() {
return roots.size();
}
public static void main(String[] args) {
PersistentTrie pt = new PersistentTrie();
// 版本1：插入 "apple"
int v1 = pt.insert(1, "apple");
System.out.println("版本1插入 apple，当前版本：" + v1);
System.out.println("版本1中 'app' 前缀数量：" + pt.countPrefix(1, "app"));
// 版本2：基于版本1插入 "apply"
int v2 = pt.insert(v1, "apply");
System.out.println("版本2插入 apply，当前版本：" + v2);
System.out.println("版本2中 'app' 前缀数量：" + pt.countPrefix(v2, "app"));
System.out.println("版本1中 'app' 前缀数量（历史版本不变）：" + pt.countPrefix(1, "app"));
// 版本3：基于版本2插入 "banana"
int v3 = pt.insert(v2, "banana");
System.out.println("版本3插入 banana，当前版本：" + v3);
System.out.println("版本3中 'a' 前缀数量：" + pt.countPrefix(3, "a"));
System.out.println("版本2中 'b' 前缀是否存在：" + pt.startsWith(2, "b"));
System.out.println("版本3中 'b' 前缀是否存在：" + pt.startsWith(3, "b"));
}
}
复杂度分析
- 插入时间复杂度：
O(L)，其中L为字符串长度。每个字符最多创建一个新节点。 - 查询时间复杂度：
O(L)，沿Trie路径遍历。 - 空间复杂度：每个版本最多新增
O(L)个节点。N次插入后总节点数为O(N * L)。 - 版本切换：
O(1)，只需切换根节点索引。
应用场景
- 版本控制系统：记录文件内容的每个历史版本，支持快速回滚。
- 离线区间查询：处理”第L到R个字符串中以某前缀开头的有多少个”类问题。
- 可持久化数组/线段树的基础：可持久化Trie是理解更复杂可持久化数据结构的入门。
总结
可持久化Trie通过路径复制实现了版本化字符串存储，每次修改只影响从根到叶子的一条路径，其余分支共享旧版本节点。这种结构在保证 O(L) 操作效率的同时，实现了历史状态的完整保留。
