scala - 在 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]