What is the standard binary search tree structure to use in Scala?

avl-tree, binary-search-tree, red-black-tree, scala

Solution

Trees are fundamental to functional programming and scala, and depending on the complexity of your requirement it wouldn't be a bad idea to roll your own BTree with whatever linkage type and traversal methods fit.

As a general model it could look something like this:

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]

Problem

What is the standard balanced binary search tree implementation one should use in Scala 2.10.x? I am looking around and it seems that `AVLTree` was removed and `RedBlack` is deprecated with a message `(Since version 2.10.0) use TreeMap or TreeSet instead`. However, `TreeMap` and `TreeSet` do not provide the functionality I need because I need to be able to traverse the tree and build a more complex data structure based on this. Is there any new class that provides the plain balanced binary tree functionality that is not deprecated?

Original source