scala 树集无法删除元素

Question

我正在使用 scala.collection.mutable.TreeSet 并且运行遇到了一个问题，当调用 -= 时它无法删除元素。

我的代码：

val discovered = new TreeSet[Position]()(Ordering by { position => estimation(position) })
//Position is defined as: type Position = (Int, Int)

discovered += start
var x = 0
while(!discovered.isEmpty){
  val current = discovered.head
  println(discovered)
  discovered -= current
  println(discovered)
  x += 1
  println(s"$x $current")

  [...] //Code to process current and discover new positions
}

以下示例显示，(18,46) 未被删除。到那时为止，删除工作完美无缺。我还有其他测试用例，这些测试用例可以完美运行，而其他测试用例在达到大约 100 次迭代之前不会发生此问题。 TreeSet.

的不可变实现得到了相同的结果

部分输出：

TreeSet((22,42), (18,46), (21,44), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47))
TreeSet((18,46), (21,44), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47))
14 (22,42)
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47))
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47))
15 (18,46)
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47), (17,46))
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47), (17,46))
16 (18,46)

Answer 1

问题是你的顺序不稳定，当代码是运行时，两个给定元素之间的关系可能会改变，使得树的内容无效（你没想到的是每次更新哈希映射时树都会重新排序，是吗？）。

我觉得，你应该考虑把你所有的都扔掉，从头开始重新思考你的方法。尝试以函数的方式实现它可能会有所帮助，避免使用 var 和可变结构，除了使您的代码更清晰和清晰之外，它还可以帮助您避免这样的错误。

Answer 2

感谢大家的回答！排序与问题有关，因此对查找错误有很大帮助。

澄清：

我正在实现我的很多代码库的全部功能。对于这个算法，由于几个原因是不可能的。另外：如果有一个 PriorityQueue，它有一个 updateElement() 函数，我会使用它而不是 TreeSet 以获得更好的性能并避免我运行遇到的问题。

我的解决方案：

如前所述：我必须将其实现为可变的，而且主要是命令式的。问题出在那些代码行中

estimation(somePosition) = newScore
if(alreadyDiscovered){ discovered -= somePosition }
discovered += somePosition

从 discovered 中删除 somePosition 是利用排序，这在上面的行中已更改。因此，当 RB 树尝试删除该元素时，它不再找到它。 以下代码适用于所有测试用例

if(alreadyDiscovered){ discovered -= somePosition }
estimation(somePosition) = newScore
discovered += somePosition

如果有比 vanilla scala 中的 TreeSet 更好的数据结构来完成这个任务，我很乐意切换到那个。

scala 树集无法删除元素

scala treeset fails to remove element

scala

red-black-tree

treeset