java - 确保树状结构中的失败原子性

Question

情况

我必须处理相当大的(>10000 个条目)树结构。不是二叉树，而是具有自然层次结构的数据(例如，根的子级是大陆，大陆的子级是国家，国家的子级是城市)。

合并是通过递归地配对具有相同名称的条目并计算其子项的并集来完成的。

Europe
  Germany
     Düsseldorf
     Hamburg
(merged with)
Europe
  Belgium
     Mechelen
  Germany
     Stuttgart
(should give)
Europe
  Belgium
     Mechelen
  Germany
     Düsseldorf
     Hamburg
     Stuttgart

条目总是排序的，因此您永远不会遇到相同条目在不同树中以不同顺序出现的情况。

问题

在合并两棵这样的树时，确保失败原子性的好方法是什么？具体来说，如果树在同一级别包含相同的叶条目，则整个合并操作应该失败。

Europe
  Belgium
     Gent
     Mechelen
(merged with)
Europe
  Belgium
     Mechelen
(should fail, because Mechelen appears in both trees under Europe/Belgium)

“好”是什么意思？

1. 运行时间并不重要，代码复杂性和内存是主要限制因素。
2. 具体来说，由于结构的大小，我希望尽可能避免写时复制。
3. 解决方案不必是线程安全的，外部同步可确保在合并运行时不会访问任何树。
4. 我碰巧在使用 Java，但任何命令式伪代码都可以。

Answer 1

我认为David Eisenstat已经给出了一个可行的方案。

正如 Durandal 提到的，您可以在开始合并操作之前检查重复节点。

如果您已经有办法计算两棵树的交集，另一种可能的方法很容易，就是计算它并在它为空时继续合并，否则抛出异常。您似乎希望交叉路口是空的或非常小，因此这不会占用太多空间。您还可以将代码调整为在找到相交元素时立即停止。

(我认为您因空间要求而排除的最自然的选择是:创建一个新树，它是原始树的副本。对新树执行合并操作，成功后继续使用新树. 这种方法类似于 Java 的 String 等不可变对象(immutable对象)的操作方式。)