AVL Tree library in Scala. See also: http://d.hatena.ne.jp/hideshi_o/20120917/1347902052

avltree.scala

sealed abstract class AVLTree[A <% Ordered[A]] {
	def +(v:A):AVLTree[A]
	def -(v:A):AVLTree[A]
	def reconstruct:AVLTree[A]
	def depth:Int
	def contains(v:A):Boolean
	def size:Int
	def isEmpty:Boolean
	def nonEmpty:Boolean
	def toList:List[A]
}

case class Node[A <% Ordered[A]](left:AVLTree[A], value:A, right:AVLTree[A]) extends AVLTree[A] {
	def +(v:A):AVLTree[A] = {
		val result =
		if(v < value) {
			left match {
				case Node(_,_,_) => Node(left + v, value, right)
				case Leaf() => Node(Node(Leaf[A](), v, Leaf[A]()), value, right)
			}
		} else if(value < v) {
			right match {
				case Node(_,_,_) => Node(left, value, right + v)
				case Leaf() => Node(left, value, Node(Leaf[A](), v, Leaf[A]()))
			}
		} else this
		result.reconstruct
	}
	def -(v:A):AVLTree[A] = {
		val result =
			if(v < value) Node(left - v, value, right)
			else if(value < v) Node(left, value, right - v)
			else insertTree(left, right)
		result.reconstruct
	}
	private def insertTree(left:AVLTree[A], right:AVLTree[A]):AVLTree[A] = { 
		(left, right) match {
			case (node, Node(l,v,r)) => Node(insertTree(node, l), v, r)
			case (node, Leaf()) => node
			case (Leaf(), node) => node
		}
	}
	def reconstruct:AVLTree[A] = {
		val (ldMax, rdMax) = (left.depth, right.depth)
		(left, right) match {
			case (Node(ll, lv, lr), (Node(rl, rv, rr))) =>
				val (lld, lrd, rld, rrd) = (ll.depth, lr.depth, rl.depth, rr.depth)
				if(lld > lrd && ldMax > rdMax && Math.abs(ldMax - rdMax) > 1) {
					Node(ll, lv, Node(lr, value, right))
				} else if(lld < lrd && ldMax > rdMax && Math.abs(ldMax - rdMax) > 1) {
					val (Node(lrl, lrv, lrr)) = lr
					Node(Node(ll, lv, lrl), lrv, Node(lrr, value, right))
				} else if(rld < rrd && ldMax < rdMax && Math.abs(ldMax - rdMax) > 1) {
					Node(Node(left, value, rl), rv, rr)
				} else if(rld > rrd && ldMax < rdMax && Math.abs(ldMax - rdMax) > 1) {
					val (Node(rll, rlv, rlr)) = rl
					Node(Node(left, value, rll), rlv, Node(rlr, rv, rr))
				} else this
			case (Node(ll, lv, lr), Leaf()) =>
				val (lld, lrd) = (ll.depth, lr.depth)
				if(lld > lrd && Math.abs(ldMax - rdMax) > 1) {
					Node(ll, lv, Node(lr, value, right))
				} else if(lld < lrd && Math.abs(ldMax - rdMax) > 1) {
					val (Node(lrl, lrv, lrr)) = lr
					Node(Node(ll, lv, lrl), lrv, Node(lrr, value, right))
				} else this
			case (Leaf(), Node(rl, rv, rr)) =>
				val (rld, rrd) = (rl.depth, rr.depth)
				if(rld < rrd && Math.abs(ldMax - rdMax) > 1) {
					Node(Node(left, value, rl), rv, rr)
				} else if(rld > rrd && Math.abs(ldMax - rdMax) > 1) {
					val (Node(rll, rlv, rlr)) = rl
					Node(Node(left, value, rll), rlv, Node(rlr, rv, rr))
				} else this
			case (Leaf(), Leaf()) => this
		}
	}
	def depth:Int = {
		Math.max(1 + left.depth, 1 + right.depth)
	}
	def contains(v:A):Boolean = {
		if(v == value) true
		else {
			(left, right) match {
				case (Node(_,_,_), Node(_,_,_)) =>
					(left contains v) || (right contains v)
				case (Node(_,_,_), Leaf()) =>
					(left contains v)
				case (Leaf(), Node(_,_,_)) =>
					(right contains v)
				case (Leaf(), Leaf()) => false
			}
		}
	}
	def size:Int = {
		(left, right) match {
			case (Node(_,_,_), Node(_,_,_)) =>
				1 + (left size) + (right size)
			case (Node(_,_,_), Leaf()) =>
				1 + (left size)
			case (Leaf(), Node(_,_,_)) =>
				1 + (right size)
			case (Leaf(), Leaf()) => 1
		}
	}
	def isEmpty:Boolean = false
	def nonEmpty:Boolean = !isEmpty
	def toList:List[A] = {
		(left toList) ::: List(value) ::: (right toList)
	}
}

case class Leaf[A <% Ordered[A]] extends AVLTree[A] {
	def +(v:A):AVLTree[A] = Node(Leaf[A](), v, Leaf[A]())
	def -(v:A):AVLTree[A] = this
	def reconstruct:AVLTree[A] = this
	def depth:Int = 0
	def contains(v:A):Boolean = false
	def size:Int = 0
	def isEmpty:Boolean = true
	def nonEmpty:Boolean = !isEmpty
	def toList:List[A] = Nil
}
/*
val tree = (2 to 4).reverse.foldLeft(Leaf[Int]():AVLTree[Int]){(acc, i) => acc + i}
val tree2 = (2 to 5).reverse.foldLeft(Leaf[Int]():AVLTree[Int]){(acc, i) => acc + i}
val tree3 = Leaf[Int]() + 10 + 5 + 15 + 3 + 7
val tree4 = (1 to 129).reverse.foldLeft(Leaf[Int]():AVLTree[Int]){(acc, i) => acc + i}
val tree5 = (1 to 256).reverse.foldLeft(Leaf[Int]():AVLTree[Int]){(acc, i) => acc + i}
println("**+")
println(Leaf[Int]() + 1)
println(tree + 1)
println(tree2 + 1)
println(tree4)
println(tree5)

println("**depth")
println(Leaf[Int]().depth)
println(tree.depth)
println(tree2.depth)
println(tree3.depth)
println(tree4.depth)
println(tree5.depth)

println("**+")
println(tree3)
println(tree3 + 1)
println(tree3 + 4)
println(tree3 + 6)
println(tree3 + 8)
println(tree3 + 1 + 0 + (-1))

println("**contains")
println(tree3 contains 5)
println(tree3 contains 15)
println(tree3 contains 0)

println("**size")
println(Leaf[Int]() size)
println(tree size)
println(tree2 size)
println(tree3 size)
println(tree4 size)
println(tree5 size)

println("**isEmpty")
println(Leaf[Int]() isEmpty)
println(tree isEmpty)

println("**nonEmpty")
println(Leaf[Int]() nonEmpty)
println(tree nonEmpty)

println("**toList")
println(Leaf[Int]() toList)
println(tree toList)
println(tree2 toList)
println(tree3 toList)
println(tree4 toList)
println(tree5 toList)

println("**-")
println(Leaf[Int]() - 1)
println(tree3 - 10)
println(tree3 + 1 - 10 - 7 - 15)
*/