java - 二叉搜索树中的重复项

Question

处理二叉搜索树中的重复项的优雅方法是什么？我们假设每个键都有几个不同的关联值。我需要做的是按顺序迭代所有值。因此，如果我有 2 个带有键 1 的值 A 和 B，以及一个带有键 2 的值 C，那么当调用类似的方法时，我希望得到对:(1,A)、(1,B)、(2,C) TreeIterator.next();

我能想到:

• 每个节点都有一个键和一个值数组，具有相同键的值位于该数组中
• 每个节点都有一个已访问标志

还有其他建议吗？作为一般准则，我希望 Tree 实现尽可能抽象。

Answer 1

听起来基本上您确实想要每个键的值列表，是的。那么添加到 map 的过程就是:

• key 存在吗？
  • 如果是这样，请为现有列表添加值(value)。
  • 如果没有，请在树中的适当位置(照常)创建一个新节点，并从包含一个值的列表开始

迭代 map 时，您的一般模式是:

• 生成左节点的所有值(较小的键)
• 生成该节点的所有值 - (key, value1), (key, value2) 等
• 生成右侧节点的所有值(较大的键)

当然，如果您不需要自己实现这个用于学习目的，您可以使用现成的多重映射，例如 Guava的TreeMultimap 。如果您为了自学而实现它，我会首先实现一个“正常”的二分搜索映射，然后从那里继续。