java - 比较 2 个 b-tree 以查看它们是否包含相同的值

Question

看到 2 个 b-tree 可能具有相同的值，但形状不同，是否有一种算法可以遍历这些值并比较两个树是否具有相同的键？

关键是如果它们包含不同的密钥（尽快），就能够摆脱困境。

除非您同时在两个 b 树中执行查找，否则递归算法可能不起作用，我猜。

我见过遍历 b-tree 的算法，但我不想遍历两者，然后比较密钥，我想要更聪明的东西，如果有差异，我会尽快退出。

基本上该函数返回真/假。

Answer 1

基本技术是在有序遍历中以某种方式拥有一个表示当前点的对象。一旦你有了其中的两个，一个用于树的每个实例，你只需继续为下一个键抽取它们，当两者第一次返回不同的下一个键时，你就完成了。

在 C# 中，您将使用yield return一次生成一个键的遍历，并跟踪它在树中的位置。然后，您可以将其中两个传递给SequenceEquals，它会在遇到第一个差异时立即退出。在 Java 中，您必须自己构建该机制，但这并不难。

Answer 2

假设你的意思是一个b-tree，那么你需要做的就是一次迭代两者。任何一个迭代器之间的任何偏差都将证明它们的内容不同。如果在构建树时不收集更多细节，您不太可能找到比这更好的算法。

如果您不是在谈论被描述为的b 树：

... B 树是一种树数据结构，它保持数据排序并允许在对数时间内进行搜索、顺序访问、插入和删除。

那么你需要先对其进行排序然后遍历它。