不成环的关键:应用前做祖先检查
上一类畸变里最硬的是成环: 把一个节点移到它自己的子树里,树就不再是树。挡住它其实只需一道祖先检查。应用 move(child, newParent) 前,从 newParent 出发沿 parent 链一路上行: 如果上行途中撞到了
child(说明 child 是 newParent 的祖先,newParent 在 child 的子树里),或者两者本就相同——这步必然成环,于是直接退化成 no-op(这条 op 仍记进 log,只是不改树)。
选一个 child 和一个 newParent(下方给了一个安全和一个成环的预设),点「检查并 move」,用「下一步」逐格看从 newParent 上行的过程:当前所在节点用橙圈标出,提案的 move 是一条虚线。撞到 child → 虚线转红、拒绝;一路到 ROOT 没撞到 → 安全、应用。
为什么只查祖先就够? 单亲森林里,「move 会成环」当且仅当新 parent 已经在 child 的子树内——把 child 挂到自己的后代下面,这段路径就首尾相接。沿 parent 链从 newParent 上行能否抵达 child,正好判定这一点。检查是 的,拒绝时这条 op 不丢、只是不生效 (no-op),这点对 undo-do-redo 很关键:同一条 op 在不同的树状态下重放,可能这次成环被拒、那次又安全生效。
祖先检查保证了单次应用不成环,但分布式下 op 会乱序到达——undo-do-redo 让乱序也收敛。