什么是持久化平衡树？为什么路径复制能保留历史版本？

简化版

持久化平衡树是在更新时不原地修改旧节点，而是复制从根到修改位置的一条路径，并复用未改变的子树。这样每次更新都会产生一个新根，旧根仍指向旧版本，历史版本就被保留下来。

详细版

普通平衡树更新会改指针、颜色、高度等字段，旧状态被覆盖。持久化版本用路径复制：

查找插入或删除位置；
沿途复制访问过的节点；
未访问到的子树直接共享；
在新节点上做旋转和元数据更新；
返回新根作为新版本。

若树高是 O(log n)，一次更新只复制 O(log n) 个节点，加上旋转附近的常数节点，空间和时间仍是 O(log n) 级别。它适合版本查询、撤销、时间旅行数据等场景。

完整版教学

一、持久化是什么意思

持久化数据结构不是把数据写到磁盘，而是指旧版本在更新后仍然可访问。比如版本 1 有集合 {1,3,5}，插入 4 后得到版本 2 {1,3,4,5}，但版本 1 仍然能被查询，且结果不受版本 2 影响。

对平衡树来说，难点是更新会改变从根到叶的指针，还可能旋转。如果直接原地改，旧版本就被破坏。路径复制通过「只复制会变的路径」解决这个问题。

记忆钩子：持久化平衡树不是整棵复制，而是新路重铺，旧路保留，没经过的树林共享。

二、为什么只复制一条路径就够了

BST 插入删除定位只会沿根到目标位置的一条路径走。只有这条路径上的节点，其左/右孩子指针可能因为下层变化而改变。其他子树没有任何结构变化，可以被新旧版本共享。

假设树有 1024 个节点且高度约 10。插入一个值时，整棵复制要复制 1024 个节点；路径复制只复制约 10 个路径节点，再加少量旋转节点。这就是持久化树可用的关键。

三、结构共享如何避免互相污染

共享未改变子树的前提是这些子树不会被原地修改。因此持久化实现通常把节点视为不可变，或者至少保证一旦节点属于旧版本，就不再修改它。新版本需要改变某个字段时，创建新节点保存新字段。

version1 root -> A -> B -> C
version2 root -> A'-> B'-> C'
未经过的子树 S 被 A 和 A' 同时引用

如果你在共享子树 S 上原地改字段，两个版本都会看到变化，持久化语义就崩了。

四、旋转在持久化里怎么处理

旋转会改局部指针，所以参与旋转的节点也必须是新复制出来的节点。不能拿旧版本里的节点直接旋转。通常做法是递归返回新子树根，然后在新节点上执行旋转，旋转结果也由新节点组成。

Node insert(Node root, int key) {
    if (root == null) return new Node(key);
    Node x = root.copy();
    if (key < x.key) x.left = insert(root.left, key);
    else x.right = insert(root.right, key);
    return rebalance(x); // rebalance 只操作新节点
}

真实代码要确保 rebalance 不会修改旧孩子节点。如果需要修改孩子，也要先复制孩子。

五、复杂度和内存增长

若底层平衡树高度 O(log n)，每次更新复制 O(log n) 个节点，查询仍沿某个版本根走 O(log n)。做 m 次更新后，额外节点数约 O(m log n)，而不是 O(mn)。

操作	时间	新增空间
查询某版本	O(log n)	O(1)
插入新版本	O(log n)	O(log n)
删除新版本	O(log n)	O(log n)
保留 m 个版本	视更新数	O(m log n) 级别

如果版本非常多且长期不释放，内存仍会增长，需要引用计数、GC 或版本淘汰策略。

六、适用场景和限制

持久化平衡树适合需要历史查询的场景，例如撤销操作、按时间版本查询排名、函数式集合、竞赛里的主席树思想。它不适合频繁原地批量修改且只关心最新状态的简单业务，因为实现复杂度和内存压力更高。

还要注意并发语义。不可变结构天然利于多读，但如果有全局版本表、内存回收或懒标记，仍要做好同步设计。

七、常见误区与追问

误区：持久化就是每次复制整棵树。 路径复制只复制 O(log n) 路径节点，其他子树共享。
追问：为什么共享子树不会互相影响？ 共享部分必须不可变，更新只发生在新复制节点上。
误区：旋转可以直接改旧节点。 旋转改指针，必须在新节点上完成，否则旧版本被破坏。
追问：空间复杂度是多少？ 单次更新 O(log n) 新节点，多版本总空间和更新次数相关。
误区：持久化一定更快。 它换来历史版本能力，但常数和内存成本更高。

八、加强记忆

持久化平衡树抓住一句：更新只复制变化路径，未变化子树共享。每个版本用一个根指针代表，旧根不动，新根指向复制后的路径。旋转和字段更新都必须发生在新节点上。它用 O(log n) 级别新增空间换来历史版本查询能力，适合撤销、时间线查询和函数式数据结构。

简化版

详细版