15
\$\begingroup\$

I've written a Binary Search Tree Monad in Scala. I would like to hear your thoughts on how to improve it (e.g. making insertion/deletion/search faster and more scalable). Also, is there a better way to implement this kind of data structure the Scala way?

The whole code

Here is the trait:

trait BST[+A] {
  def +[B >: A <% Ordered[B]](elem: B): BST[B]
  def ++[B >: A <% Ordered[B]](bst: BST[B]): BST[B]
  def -[B >: A <% Ordered[B]](elem: B): (Option[B], BST[B])

  def exists(p: A => Boolean): Boolean
  def contains[B >: A <% Ordered[B]](e: B): Boolean
  def filter[B >: A <% Ordered[B]](p: A => Boolean): BST[B] = filterAcc[B](EmptyBST)(p)
  def filterAcc[B >: A <% Ordered[B]](acc: BST[B])(p: A => Boolean): BST[B]

  def flatMap[B <% Ordered[B]](f: A => BST[B]): BST[B]
  def map[B <% Ordered[B]](f: A => B): BST[B]

  def inOrder[B](z: B)(f: (A, B) => B): B
  def preOrder[B](z: B)(f: (A, B) => B): B
  def postOrder[B](z: B)(f: (A, B) => B): B
  def levelOrder[B](z: B)(f: (A, B) => B): B

  def withLeft[B >: A <% Ordered[B]](newLeft: BST[B]): BST[B]
  def withRight[B >: A <% Ordered[B]](newRight: BST[B]): BST[B]
  def orElse[B >: A <% Ordered[B]](tree: BST[B]): BST[B]
  def minChild[B >: A <% Ordered[B]]: BST[B] = minChildAcc[B](this)
  def minChildAcc[B >: A <% Ordered[B]](acc: BST[B]): BST[B]

  def toList = preOrder(List[A]())(_ :: _).reverse
}

And here is the implementation:

case object EmptyBST extends BST[Nothing] {
  def +[B <% Ordered[B]](elem: B) = BST(elem)
  def ++[B <% Ordered[B]](bst: BST[B]) = bst 
  def -[B <% Ordered[B]](elem: B) = (None, EmptyBST)

  def flatMap[B <% Ordered[B]](f: Nothing => BST[B]): BST[B] = EmptyBST    
  def map[B <% Ordered[B]](f: Nothing => B): BST[B] = EmptyBST 

  def exists(p: Nothing => Boolean) = false
  def contains[B <% Ordered[B]](e: B) = false
  def filterAcc[B <% Ordered[B]](acc: BST[B])(p: Nothing => Boolean) = acc

  def inOrder[B](z: B)(f: (Nothing, B) => B) = z
  def preOrder[B](z: B)(f: (Nothing, B) => B) = z
  def postOrder[B](z: B)(f: (Nothing, B) => B) = z
  def levelOrder[B](z: B)(f: (Nothing, B) => B) = z

  def withLeft[B <% Ordered[B]](newLeft: BST[B]) = newLeft
  def withRight[B <% Ordered[B]](newRight: BST[B]) = newRight
  def orElse[B <% Ordered[B]](tree: BST[B]) = tree
  def minChildAcc[B <% Ordered[B]](acc: BST[B]) = acc

  override def toString = "[]"
}

case class NonEmptyBST[A <% Ordered[A]](elem: A, left: BST[A], right: BST[A]) extends BST[A] {
  def +[B >: A <% Ordered[B]](newElem: B) = 
    if (newElem < elem) withLeft(left + newElem)
    else if (newElem > elem) withRight(right + newElem)
    else this

  def ++[B >: A <% Ordered[B]](bst: BST[B]) = bst.preOrder[BST[B]](this)((e, acc) => acc + e)

  def -[B >: A <% Ordered[B]](e: B) = 
    if (e < elem) (left - e) match { 
      case (opt, l) => (opt, withLeft(l)) 
    } else if (e > elem) (right - e) match { 
      case (opt, r) => (opt, withRight(r)) 
    } else (Some(elem), (left, right) match {
      case (EmptyBST, EmptyBST) => EmptyBST
      case (l, EmptyBST) => l
      case (EmptyBST, r) => r
      case (l, r) => right.minChild match {
        case EmptyBST => r.withLeft(l)
        case NonEmptyBST(min, _, _) => NonEmptyBST(min, l, (r - min)._2) 
      }
    })

  def exists(p: A => Boolean) = p(elem) || left.exists(p) || right.exists(p)
  def contains[B >: A <% Ordered[B]](e: B) = exists(_ == e)
  def filterAcc[B >: A <% Ordered[B]](acc: BST[B])(p: A => Boolean) = 
    right.filterAcc(left.filterAcc(if (p(elem)) acc + elem else acc)(p))(p)

  def flatMap[B <% Ordered[B]](f: A => BST[B]) = preOrder(f(elem))((e, acc) => acc ++ f(e))
  def map[B <% Ordered[B]](f: A => B) = preOrder[BST[B]](BST(f(elem)))((e, acc) => acc + f(e))

  def inOrder[B](z: B)(f: (A, B) => B) = right.inOrder(f(elem, left.inOrder(z)(f)))(f)
  def preOrder[B](z: B)(f: (A, B) => B) = right.preOrder(left.preOrder(f(elem, z))(f))(f)    
  def postOrder[B](z: B)(f: (A, B) => B) = f(elem, right.postOrder(left.postOrder(z)(f))(f))

  def levelOrder[B](z: B)(f: (A, B) => B) = {
    def recurse(acc: B, queue: Queue[BST[A]]): B = queue match {
      case Queue() => acc
      case h +: t => h match {
        case EmptyBST => recurse(acc, t)
        case NonEmptyBST(e, l, r) => recurse(f(e, acc), t.enqueue(l).enqueue(r))
      }
    }  

    recurse(z, Queue(this))
  }

  def withLeft[B >: A <% Ordered[B]](newLeft: BST[B]) = NonEmptyBST(elem, newLeft, right)
  def withRight[B >: A <% Ordered[B]](newRight: BST[B]) = NonEmptyBST(elem, left, newRight)
  def minChildAcc[B >: A <% Ordered[B]](acc: BST[B]) = left.minChildAcc(this)
  def orElse[B >: A <% Ordered[B]](tree: BST[B]) = this

  override def toString = elem + "[l=" + left + ", r=" + right + "]"
}

object BST {
  def apply[A <% Ordered[A]](): BST[A] = EmptyBST

  def apply[A <% Ordered[A]](elem: A, elems: A*): BST[A] = { 
    def recurse(elems: List[A],bst: BST[A]): BST[A] = 
      if (elems.isEmpty) bst
      else recurse(elems.tail, bst + elems.head)

    recurse(elems.toList, NonEmptyBST(elem, EmptyBST, EmptyBST))
  }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I remember seeing some academic paper about an efficient algorithm to implement an immutable binary tree. I know it was referenced in some way by Martin Odersky. Sorry, but it's really all that I remember. \$\endgroup\$
    – toto2
    Jun 14, 2014 at 17:14
  • \$\begingroup\$ It does not sound right that you are using possibly different Ordered implementations on each operation. (Also, nowadays -I understand this is quite old question- Ordering and context bounds are preferred.) \$\endgroup\$ Oct 24, 2017 at 5:33

1 Answer 1

1
\$\begingroup\$

I have not treated Scala, but Haskell. I like some competitive programming and I thought about Tree Problems deeply. I'm sorry for the Japanese site, a tree problem and my solution are:

Deque - Aizu Online Judge

My solution in Haskell

In Scala, the vector type scala.collection.immutable.Vector is similar to my above tree structure. Maybe, you can get faster implementation than the simple BST.

Each depth d needs 2^(d-1) nodes, I think the following relationship:

1st depth = 1
2nd depth = [2, 3]
3rd depth = [4, 5, 6, 7]

In general,

left = (parent << 1);
right = (parent << 1) + 1;
parent = child >> 1;
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Sorry for the delay, SE didn't notify me of your response. Thank you for the change your post should now meet the requirements to not be deleted. \$\endgroup\$
    – Peilonrayz
    May 30, 2021 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.