如何使用 Scala Collections TreeMap（或类似的）维护关于树的属性

Question

由于 scala RedBlack 树在 scala 集合中不再可用，我无法弄清楚如何在 scala 树的节点中维护有关树的属性，因为我需要直接访问树而不是标准集合提供的封装接口。

例如，我想要一棵树，它在每个节点上维护一个字段 x，使得函数 f 对每个节点 n 成立，这样

f(null) = 0
f(n) = n.x + f(n.left) + f(n.right)

我可以为此有效地使用 Scala 标准库 TreeMap 还是我必须实现我自己的树（目前正在这样做）？

Answer 1

遗憾的是，我认为您无法使用 TreeMap 执行此操作。您可能只想从 Scala 集合中复制 the red black tree 并添加一个摘要字段。

或者，您可能想要使用允许指定 "measure" 的 tree-based 集合之一。例如。 https://github.com/Sciss/FingerTree

或者，您可以使用这个可怕的 hack 将一些摘要数据添加到节点，例如一个树集。请注意命名空间 scala.collection.immutable，以便您可以从实用程序内部访问 RedBlackTree。

package scala.collection.immutable

trait Summary[E, S] {
  def apply(v: E): S
  def empty: S
  def combine(a: S, b: S): S
  def combine3(a: S, b: S, c: S) = combine(combine(a, b), c)
}

object TreeSetSummarizer {

  private[this] val treeSetAccessor = classOf[scala.collection.immutable.TreeSet[_]].getDeclaredField("tree")
  treeSetAccessor.setAccessible(true)

  private def tree[K](set: TreeSet[K]): AnyRef = treeSetAccessor.get(set) match {
    case t: RedBlackTree.Tree[K, Unit] ⇒ t
    case _ ⇒ "null"
  }

  private type JFunction[T, R] = java.util.function.Function[T, R]

  def apply[K, S](implicit s: Summary[K, S]): (TreeSet[K] ⇒ S) = new TreeSetSummarizer[K, S]
}

class TreeSetSummarizer[K, S](implicit summary: Summary[K, S]) extends (TreeSet[K] ⇒ S) {
  import TreeSetSummarizer._

  // this should be a guava cache using weak keys to prevent memory leaks
  private val memo = new java.util.IdentityHashMap[AnyRef, S]()

  private val f: JFunction[AnyRef, S] = new JFunction[AnyRef, S] {
    def apply(t: AnyRef): S = t match {
      case t: RedBlackTree.Tree[K, Unit] ⇒ summary.combine3(apply0(t.left), summary.apply(t.key), apply0(t.right))
      case _ ⇒ summary.empty
    }
  }

  private def apply0(set: AnyRef): S =
    memo.computeIfAbsent(set, f)

  def apply(set: TreeSet[K]): S =
    apply0(tree(set))
}

下面是您将如何使用它

import scala.collection.immutable._

// create a large TreeSet
val largeSet = TreeSet(0 until 10000: _*)
// define your summary
implicit val s = new Summary[Int, Long] {
  def empty = 0L
  def apply(x: Int) = x
  def combine(a: Long, b: Long) = a + b
}
// define your summarizer. You need to keep the summarizer instance for
// having a performance benefit, since it internally stores summaries for
// tree nodes in an identity hash map
val summary = TreeSetSummarizer.apply[Int, Long]

// summarize something
println(summary(largeSet))

// summarize a modified set. This is fast because the summaries for tree
// nodes are being cached.
val largeSet1 = largeSet - 5000
println(summary(largeSet1))

请注意，考虑到反射和散列开销，这可能最适合用于计算量更大的汇总，而不是简单的求和。

更新：我现在已经编写了一个小型库 persistentsummary 来为现有的 Scala 集合定义持久性摘要。这应该完全符合您的要求。

如何使用 Scala Collections TreeMap（或类似的）维护关于树的 属性

How to maintain a property about trees using a Scala Collections TreeMap (or similar)

tree

scala

如何使用 Scala Collections TreeMap（或类似的）维护关于树的属性