Last active
December 10, 2015 03:38
-
-
Save dayorbyte/4375564 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment