Skip to content

Instantly share code, notes, and snippets.

@ryanlecompte
Last active August 29, 2015 13:56
Show Gist options
  • Save ryanlecompte/9319804 to your computer and use it in GitHub Desktop.
Save ryanlecompte/9319804 to your computer and use it in GitHub Desktop.
Immutable binary search trees
sealed trait BST[+K, +V]
object BST {
def apply[K: Ordering, V](k: K, v: V): Node[K, V] = Node(k, v, Empty, Empty)
case object Empty extends BST[Nothing, Nothing]
case class Node[K, V](key: K, value: V, left: BST[K, V], right: BST[K, V])(implicit ord: Ordering[K]) extends BST[K, V] {
def get(item: K): Option[V] = search(item, this)
def +(kv: (K, V)): Node[K, V] = insert(kv._1, kv._2, this)
private def search(item: K, node: BST[K, V]): Option[V] = {
import ord._
node match {
case Empty => None
case Node(k, v, leftNode, rightNode) =>
if (item < k) search(item, leftNode)
else if (item > k) search(item, rightNode)
else Some(v)
}
}
private def insert(item: K, itemValue: V, node: BST[K, V]): Node[K, V] = {
import ord._
node match {
case Empty => Node(item, itemValue, Empty, Empty)
case n @ Node(k, _, leftNode, rightNode) =>
if (item < k) n.copy(left = insert(item, itemValue, leftNode))
else if (item > k) n.copy(right = insert(item, itemValue, rightNode))
else n.copy(value = itemValue)
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment