Scala 2.10.x 中应该使用的标准平衡二叉搜索树实现是什么?我环顾四周,似乎AVLTree
被删除和 RedBlack
不推荐使用消息 (Since version 2.10.0) use TreeMap or TreeSet instead
.然而,TreeMap
和 TreeSet
不提供我需要的功能,因为我需要能够遍历树并基于此构建更复杂的数据结构。
是否有任何新类提供未弃用的纯平衡二叉树功能?
最佳答案
树是函数式编程和 Scala 的基础,根据您的需求的复杂性,使用适合的任何链接类型和遍历方法滚动您自己的 BTree 并不是一个坏主意。
作为一般模型,它可能如下所示:
trait BSTree[+A] {
def value: Option[A] = this match {
case n: Node[A] => Some(n.v)
case l: Leaf[A] => Some(l.v)
case Empty => None
}
def left: Option[BSTree[A]] = this match {
case n: Node[A] => Some(n.l)
case l: Leaf[A] => None
case Empty => None
}
def right: Option[BSTree[A]] = this match {
case n: Node[A] => Some(n.r)
case l: Leaf[A] => None
case Empty => None
}
}
case class Node[A](v: A, l: BSTree[A], r: BSTree[A]) extends BSTree[A]
case class Leaf[A](v: A) extends BSTree[A]
case object Empty extends BSTree[Nothing]
关于scala - 在 Scala 中使用的标准二叉搜索树结构是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21994828/