在Scala中使用的标准二进制搜索树结构是什么？

Question

什么是Scala 2.10.x中应该使用的标准平衡二叉搜索树实现？我环顾四周,它似乎已AVLTree被删除,并RedBlack已被弃用(Since version 2.10.0) use TreeMap or TreeSet instead.但是,TreeMap并TreeSet没有提供我需要的功能,因为我需要能够遍历树并基于此构建更复杂的数据结构.

是否有任何新类提供了不被弃用的普通平衡二叉树功能？

Answer 1

树是函数式编程和 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]

Answer 2

您可以尝试这个自制版本的二叉搜索树：

https://github.com/melvic-ybanez/scala-bst

就我而言，我使用 HashSet，当数据不可变时，它可以非常有效地按键对数据进行排序。