cycle · 祖先检查 = no-op

应用前的祖先检查

上一页的三类畸变里最硬的是成环：把一个节点移到它自己的子树里，树就不再是树。挡住它只需一道祖先检查。应用 move(child, newParent) 前，从 newParent 出发沿 parent 链一路上行；如果途中撞到了 child，说明 child 是 newParent 的祖先、newParent 正在 child 的子树里，或者两者本就相同，这步必然成环，于是退化成 no-op。这条 op 仍记进 log，只是不改树。

1 · 上行检查的单步过程

图 1-1 · 从新 parent 沿 parent 链上行的检查过程。预设给了一个安全的 move 与一个成环的 move；当前所在节点以橙圈标出，提案的 move 是一条虚线，撞到 child 时虚线转红并拒绝，一路走到虚拟根未撞到则安全应用。

警示 · 只查祖先就够，是因为单亲森林里「move 会成环」当且仅当新 parent 已经在 child 的子树内——把 child 挂到自己的后代下面，这段路径就首尾相接。沿 parent 链从新 parent 上行能否抵达 child，正好判定这一点。检查的代价是树高的线性量级。拒绝时这条 op 不丢、只是不生效，这点对 undo-do-redo 很关键：同一条 op 在不同的树状态下重放，可能这次成环被拒、那次又安全生效。

祖先检查保证了单次应用不成环，但分布式下 op 会乱序到达，收敛还要靠 undo-do-redo。