带状态约束的树操作执行顺序确定方法技术问询

问题背景与需求 #

• 数据模型：树结构，每个节点包含name字段，兄弟节点的name不可重复
• 核心目标：对比操作前后的两份树状态副本，生成能清晰体现结构变化的操作日志序列
• 支持的离散操作：
  • 删除节点（包含其子节点）
  • 迁移节点至树中其他位置（包含其子节点）
  • 修改节点name
• 日志必须满足的约束：
  1. 被迁移的节点必须在其任何祖先节点被删除前完成移动
  2. 每一步操作完成后，所有兄弟节点的name保持唯一
• 额外说明：节点具备仅代码可识别的内部ID（日志中不可出现），用户提交最终结构前可能存在临时约束冲突，需处理此类情况并允许合并移动与重命名操作

示例说明 #

操作前树结构

North Shop (1)
- Zone 1 (2)
  - Shelf A (5)
    - Level 1 (7)
      - Left (11)
    - Level 2 (8)
  - Shelf B (6)
    - Level 1 (9)
    - Level 2 (10)
- Zone 2 (3)
  - Shelf A (12)
- Zone 3 (4)
  - Shelf A (13)

操作后树结构

North Shop (1)
- Zone 1 (3)
  - Shelf A (5)
    - Level 1 (7)
      - Left (11)
    - Level 2 (8)
- Zone 3 (4)
  - Shelf A (13)
  - Shelf B (12)
  - Shelf C (14)

可接受的日志序列

方式一（分步操作）

• North Shop/Zone 2/Shelf A was renamed to Shelf B
• North Shop/Zone 2/Shelf B was moved to North Shop/Zone 3
• North Shop/Zone 1/Shelf A was moved to North Shop/Zone 2
• North Shop/Zone 1 was removed
• North Shop/Zone 2 was renamed to Zone 1
• North Shop/Zone 3/Shelf C was added

方式二（合并操作）

• North Shop/Zone 2/Shelf A became North Shop/Zone 3/Shelf B
• North Shop/Zone 1/Shelf A became North Shop/Zone 2/Shelf A
• North Shop/Zone 1 was removed
• North Shop/Zone 2 became North Shop/Zone 1
• North Shop/Zone 3/Shelf C was added

建模思路与算法选择 #

1. 基于内部ID的节点映射 #

首先利用节点内部ID建立操作前后的唯一映射，这是解决name变更、路径变化的核心基础：

• 分别遍历两棵树，构建ID → 节点完整信息（当前路径、子节点列表、name等）的映射表
• 划分节点类型：
  • 存在于前后状态的节点：标记为变更节点（需检查name、父节点是否变化）
  • 仅存在于前状态的节点：标记为待删除节点
  • 仅存在于后状态的节点：标记为待新增节点

2. 约束建模与拓扑排序规划操作顺序 #

针对日志的两个核心约束，用拓扑排序来构建合法的操作依赖关系：

• 依赖关系定义：
  • 若节点X是节点Y的祖先，且X需被删除，则Y的迁移操作必须排在X的删除操作之前（避免删除X后无法定位Y）
  • 若节点Z的目标位置已存在同名兄弟节点，则需先处理冲突（比如先重命名Z，或先移走冲突节点）
• 冲突处理逻辑：
  • 对于兄弟节点的name冲突，优先处理需要变更的节点（比如将待迁移节点先重命名再移动，或直接合并为“移动并重命名”的操作）
  • 处理循环name冲突（如两个兄弟节点交换name）时，优先用合并操作简化日志，若必须分步则用临时name过渡

3. 操作生成与合并优化 #

• 基础操作生成规则：
  • 新增节点：[父节点完整路径]/[新name] was added
  • 删除节点：[原完整路径] was removed（需确保该节点的所有子节点已完成迁移或无需保留）
  • 重命名：[原完整路径] was renamed to [新name]
  • 迁移：[原完整路径] was moved to [目标父节点路径]
• 操作合并策略：
  • 当一个节点同时发生迁移和重命名时，合并为[原完整路径] became [目标完整路径]（如示例方式二），减少日志条目
  • 批量处理同层级的冲突操作，避免不必要的分步操作

4. 操作序列验证 #

生成初始操作序列后，需模拟每一步操作后的树状态，验证以下规则：

• 每一步操作完成后，所有兄弟节点的name保持唯一
• 被删除节点的所有子节点已完成迁移或被删除
• 迁移操作的目标父路径在当前状态下存在，且无name冲突

内容的提问来源于stack exchange，提问作者Tim Schommer