动态树

动态树问题, 即要求我们维护一个由若干棵子结点无序的有根树组成的森林。

要求这个数据结构支持对树的分割、合并，对某个点到它的根的路径的某些操作，以及对某个点的子树进行的某些操作。

在这里我们考虑一个简化的动态树问题，它只包含对树的形态的操作和对某个点到根的路径的操作：

维护一个数据结构，支持以下操作:

• MAKE TREE() — 新建一棵只有一个结点的树。

• CUT(v) — 删除 v 与它的父亲结点 parent(v) 的边，相当于将点 v 的子树分离了出来。

• JOIN(v,w) — 让 v 成为 w 的新的儿子。其中 v 是一棵树的根结点，并且 v 和 w 是不同的两棵树中的结点。

• FIND ROOT(v) — 返回 v 所在的树的根结点。搞清了这个问题，我们也容易扩充这个数据结构，维护每个点到它所属的树的根结点的路径的一些信息，例如权和、边权的最大值、路径长度等。

Link-Cut Trees

Link-Cut Trees 是由 Sleator 和 Tarjan 发明的解决这类动态树问题的一种数据结构。

这个数据结构可以在均摊 O(logn) 的时间内实现上述动态树问题的每个操作。

如果没有用对树的形态的改变的话，我们可以用树链剖分，把树剖分成许多条链并维护上面的权值信息。

然而对于树的形态的改变，树链的剖分方案也要改变，我们借助 Splay 的思想来动态维护许多树链（称为 Link-Cut Trees）。

Link-Cut Trees 的定义

称一个点被访问过，如果刚刚执行了对这个点的 ACCESS 操作。如果结点 v 的子树中，最后被访问的结点在子树 w 中，这里 w 是 v 的儿子, 那么就称 w 是 v 的 Preferred Child。如果最后被访问过的结点就是 v 本身，那么它没有 Preferred Child。每个点到它的 Preferred Child 的边称作 Preferred Edge。由 Preferred Edge 连接成的不可再延伸的路径称为 Preferred Path。这样，整棵树就被划分成了若干条 Preferred Path。对每条 Preferred Path，用这条路上的点的深度作为关键字，用一棵平衡树来维护它(在这棵平衡树中，每个点的左子树中的点，都在 Preferred Path 中这个点的上方；右子树中的点，都在 Preferred Path 中这个点的下方)。需要注意的是，这种平衡树必须支持分离与 合并。这里，我们选择 Splay Tree 作为这个平衡树的数据结构。我们把这棵平衡树称为一棵 Auxiliary Tree。知道了树 T 分解成的这若干条 Preferred Path，我们只需要再知道这些路径之间的连接关系，就可以表示出这棵树 T。用 Path Parent 来记录每棵 Auxiliary Tree 对应的 Preferred Path 中的最高点的父亲结点，如果这个 Preferred Path 的最高点就是根结点，那么令这棵 Auxiliary Tree 的 Path Parent 为 null。Link-Cut Trees 就是将要维护的森林中的每棵树 T 表示为若干个 Auxiliary Tree。并通过 Path Parent 将这些 Auxiliary Tree 连接起来的数据结构。

实际上，对于定义要从两方面去理解：

首先是逻辑结构，存在着一棵或多棵树，这是在逻辑上存在的，我们要做的就是对这个森林进行操作与维护；

其次是物理结构，我们并没有直接储存这些树，而是把树剖分成了多条链，每条链作为一棵 Splay。Splay 中的最小结点就是链的头结点。

回顾一下定义：

ACCESS(访问)：又叫 Expose，对结点的访问操作。

Preferred Child(最佳孩子)：最近一次访问过的儿子。最近一次被访问过的结点没有 Preferred Child。

Preferred Edge(最佳边)：每个结点到 Preferred Child 的边。

Preferred Path(最佳路径)：连续的 Preferred Edge 组成的边。

Auxiliary Tree(辅助树)：在 Splay 上维护一条链，对于 Splay 上的每个结点，它的左子树上的点都在链的上方，右子树的点都在链的下方。

Path Parent(路径的父亲)：记录链上最高结点的父亲，也就是 Splay 最左边结点的父亲，用于表示链与链之间的关系。

Link-Cut Trees 的操作

Access

ACCESS 操作是 Link-Cut Trees 的所有操作的基础。假设调用了过程 ACCESS(v)，那么从点 v 到根结点的路径就成为一条新的 Preferred Path。如果路径上经过的某个结点 u 并不是它的父亲 parent(u) 的 Preferred Child，那么由于 parent(u) 的 Preferred Child 会变为 u，原本包含 parent(u) 的 Preferred Path 将不再包含结点 parent(u) 及其之上的部分。

也就是说，过程 ACCESS 会改变逻辑上的树上的链剖分，它将结点 v 到根结点的路径作为一条新的链。而这条链会把旧的链切割开。

在物理上的 Splay 的表现就是，Splay 中的一些树被断开与重组。