gistfile1.scala

import scala.util.Random
import scala.math.max

class AVLTree[T <% Ordered[T]] (root: Option[AVLNode[T]] = None) {
    
    def insert(t: T): AVLTree[T] = {
        root match {
            case None => new AVLTree(Some(AVLNode(value=t)))
            case Some(x) => new AVLTree(Some(x.insert(value=t)))
        }
    }
    def print_tree() {
        root.get.print_tree()
    }
}

case class AVLNode[T <% Ordered[T]] (
    val value:T,
    val left:Option[AVLNode[T]] = None, 
    val right:Option[AVLNode[T]] = None
    ) {
    val height: Int = this match {
        case AVLNode(v, Some(l), Some(r)) => max(l.height, r.height) + 1
        case AVLNode(v, None, Some(r)) => r.height + 1
        case AVLNode(v, Some(l), None) => l.height + 1
        case _ => 0
    }
    def balance(): Int = this match {
        case AVLNode(v, Some(l), Some(r)) => l.height - r.height
        case AVLNode(v, None, Some(r)) => -r.height
        case AVLNode(v, Some(l), None) => l.height
        case _ => 0
    }
    def insert(value:T): AVLNode[T] = {
        println("BEGIN INSERT: " + value)
        if (value == this.value) {
            return this
        }
        require(value != this.value);
        // Get the new tree
        val tree = this match {
            // Value Less
            case AVLNode(_, None, _) if value < this.value => {
                AVLNode(value=this.value,
                           right=this.right,
                           left=Some(AVLNode(value)))

            }
            case AVLNode(_, Some(x), _) if value < this.value => {
                AVLNode(value=this.value,
                           right=this.right,
                           left=Some(x.insert(value)))

            }
            // Value More
            case AVLNode(_, _, Some(x)) if value > this.value => {
                AVLNode(value=this.value,
                        left=this.left,
                        right=Some(x.insert(value)))
            }
            case AVLNode(_, _, None) if value > this.value => {
                AVLNode(value=this.value,
                        left=this.left, 
                        right=Some(AVLNode(value)))
            }
            // Value Equal
            case _ => this
        }

        if (balance > 2 || balance < -2) {
            tree.print_tree()
            throw new Exception("Malformed tree")
        }
        // Rebalance
        val ret = tree match {
            // Right Side Too Heavy
            case AVLNode(v, a, Some(right @ AVLNode(rv, b, rr))) 
                if (tree.balance == -2 && right.balance == -1) => {
                    AVLNode(rv, Some(AVLNode(v, a, b)), rr)
                }
            case AVLNode(v, a, Some(right @ AVLNode(rv, Some(AVLNode(rlv, b, c)), d))) 
                if (tree.balance == -1 && right.balance == 1) => {
                    AVLNode(rlv, 
                                Some(AVLNode(v, a, b)),
                                Some(AVLNode(rv, c, d)))
                }
            // Left Side Too Heavy
            case AVLNode(v, Some(left @ AVLNode(lv, c, ll)), d) 
                if (tree.balance == 2 && left.balance == 1) => {
                    AVLNode(lv, ll, Some(AVLNode(v, c, d)))
                }
            case AVLNode(v, Some(left @ AVLNode(lv, a, Some(AVLNode(lrv, b, c)))), d) 
                if (tree.balance == 2 && left.balance == -1) => {
                    AVLNode(lrv, 
                                Some(AVLNode(lv, a, b)),
                                Some(AVLNode(v, c, d)))
                }
            case _ => tree

        }
        return ret
    }
    def print_tree(level:Int=0) {
        print("\t"*level)
        println(this.value)
        left match {
            case None => print("\t"*(level+1)); println(".")
            case Some(x) => x.print_tree(level=level+1)
        }
        right match {
            case None => print("\t"*(level+1)); println(".")
            case Some(x) => x.print_tree(level=level+1)
        }

    }
}


object HelloWorld {
    def main(args: Array[String]) {
      val q = new AVLTree[Int]()
      val random = new Random()
      var w = q.insert(5)
      w = w.insert(99).insert(15).insert(88).insert(11).insert(17).insert(55)
      for ( a <- 1 to 70) {
        w = w.insert(random.nextInt(10000))
      }
      println("-" * 40)
      w.print_tree()
    }
}
HelloWorld.main(args)