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

Question

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?

Answer 1

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]

Answer 2

You can try this home-made version of binary search trees:

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

As far as I'm concerned, I am using HashSet which sort the data by key very efficiently when they are immutable.