AVLTree

class node(val data : Int ){
    var hieght:Int=0
    var left:node?=null
    var right:node?=null
}
class tree(){
    fun getHeight(root:node?):Int{
        if (root==null)return 0;
        return root.hieght
    }
    fun setHeight(root:node):Int{
        return Math.max(getHeight(root.left),getHeight(root.right))+1
    }
    fun rotateLeft(root: node):node{
        var t:node=root.right!!
        root.right=root.right?.left
        t.left=root;
        t.hieght=setHeight(t)
        root.hieght=setHeight(root)
        return t
    }
    fun rotateRight(root: node):node{
        var t:node=root.left!!
        root.left=root.left?.right
        t.right=root;
        t.hieght=setHeight(t)
        root.hieght=setHeight(root)
        return t
    }

    fun insert(root:node?,data: Int):node{
        //normal insert
        var r:node?=root
        if (r==null){
            r=node(data)
        }else if(data>r.data){
            r.right=insert(r.right,data)
        }else {
            r.left=insert(r.left,data)
        }
        //balancing the tree
        var d=getHeight(r?.left)-getHeight(r?.right)
        if(d>1){//then its not balnaced
            if(getHeight(r?.left?.left)>=getHeight(r?.left?.right))r=rotateRight(r!!)
            else{
                rotateLeft(r!!)
                rotateRight(r!!)
            }
        }else if(d<-1){//then it's not balanced
            if(getHeight(r?.right?.right)>=getHeight(r?.right?.left))r=rotateLeft(r!!)
            else{
                r=rotateRight(r!!)
                r=rotateLeft(r!!)
            }
        }
        //updating the hight
        r.hieght=setHeight(r)
        return r
    }
    fun search(root:node?, data:Int):Boolean{
        if (root==null)return false
        if(root.data==data)return true
        else if(data>root.data)return search(root.right,data)
        else return search(root.left,data)
    }

}

fun main(args: Array<String>) {
    var avl=tree()
    var tree:node=node(9)
    tree=avl.insert(tree,8)
    tree=avl.insert(tree,7)
    tree=avl.insert(tree,6)
    tree=avl.insert(tree,5)
    tree=avl.insert(tree,4)
    tree=avl.insert(tree,3)


    println(avl.search(tree,5))
    println(avl.getHeight(tree))


}