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

Question

什么是Scala 2.10.x中应该使用的标准平衡二叉搜索树实现？我正在寻找，看起来 AVLTree 已被删除，而 RedBlack 已被弃用，并显示消息（自版本2.10.0以来）改用TreeMap或TreeSet。但是， TreeMap 和 TreeSet 不提供我需要的功能，因为我需要能够遍历树并基于此构建更复杂的数据结构。

是否有任何新类提供未被弃用的纯平衡二叉树功能？

- jbx

---

你是在寻找可变的还是不可变的数据结构？ - 0__

在这个阶段，任何能够正常工作的东西都可以... 不可变性会很好。 - jbx

为什么你无法遍历？ - Edmondo

Scala TreeMap和TreeSets是使用红黑树实现的，其源代码可在https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/immutable/RedBlackTree.scala中找到。 - user4322779

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]

- Alex Ehrnschwender

Answer 2

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

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

据我所知，我正在使用HashSet，当数据不可变时，它能非常有效地按键进行排序。

- Mikaël Mayer