Created
October 17, 2017 19:27
-
-
Save praveenKajla/b1ae5dd6a705680d47f288a4162c0cff to your computer and use it in GitHub Desktop.
AVLTree in ES6
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
class Node{ | |
constructor(d){ | |
this.key = d; | |
this.height = 1 | |
this.left = null | |
this.right = null | |
} | |
} | |
class AVLTree{ | |
constructor(){ | |
this.root = null | |
} | |
height(node){ | |
if(node==null)return 0; | |
return node.height; | |
} | |
rightRotate(y){ | |
let x = y.left | |
let T2 = x.right | |
//rotation | |
x.right = y | |
y.left = T2 | |
//update height | |
x.height = Math.max(this.height(x.left),this.height(x.right))+1 | |
y.height = Math.max(this.height(y.left),this.height(y.right))+1 | |
return x; | |
} | |
leftRotate(x){ | |
let y = x.right | |
let T2 = y.left | |
//rotation | |
y.left = x | |
x.right = T2 | |
//update height | |
x.height = Math.max(this.height(x.left),this.height(x.right))+1 | |
y.height = Math.max(this.height(y.left),this.height(y.right))+1 | |
return y; | |
} | |
getBalance(N){ | |
if(N==null)return 0; | |
return this.height(N.left) - this.height(N.right); | |
} | |
insert(node,key){ | |
if(node==null) return new Node(key); | |
if(key<node.key){ | |
node.left = this.insert(node.left,key); | |
}else if(key>node.key){ | |
node.right = this.insert(node.right,key); | |
}else return node; | |
node.height = 1 + Math.max(this.height(node.left),this.height(node.right)) | |
let balance = this.getBalance(node) | |
if(balance > 1 && key<node.left.key){ | |
return this.rightRotate(node); | |
} | |
if(balance > 1 && key>node.left.key){ | |
node.left = this.leftRotate(node.left) | |
return this.rightRotate(node); | |
} | |
if(balance < -1 && key>node.right.key){ | |
return this.leftRotate(node); | |
} | |
if(balance < -1 && key<node.right.key){ | |
node.right = this.rightRotate(node.right); | |
return this.leftRotate(node) | |
} | |
return node | |
} | |
} | |
let tree = new AVLTree() | |
tree.root = tree.insert(tree.root, 10); | |
tree.root = tree.insert(tree.root, 20); | |
tree.root = tree.insert(tree.root, 30); | |
tree.root = tree.insert(tree.root, 40); | |
tree.root = tree.insert(tree.root, 50); | |
tree.root = tree.insert(tree.root, 25); | |
console.log(tree) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment