An AVL Tree is a self-balancing Binary Search Tree where the difference in heights of left and right subtrees (balance factor) is at most 1 for every node.
class AVLNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
}
class AVLTree {
getHeight(node) {
return node ? node.height : 0;
}
getBalance(node) {
return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
}
rotateRight(y) {
const x = y.left;
const T2 = x.right;
x.right = y;
y.left = T2;
y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
x.height = 1 + Math.max(this.getHeight(x.left), this.getHeight(x.right));
return x;
}
rotateLeft(x) {
const y = x.right;
const T2 = y.left;
y.left = x;
x.right = T2;
x.height = 1 + Math.max(this.getHeight(x.left), this.getHeight(x.right));
y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
return y;
}
insert(node, value) {
if (!node) return new AVLNode(value);
if (value < node.value) node.left = this.insert(node.left, value);
else if (value > node.value) node.right = this.insert(node.right, value);
else return node;
node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
const balance = this.getBalance(node);
// Left Left Case
if (balance > 1 && value < node.left.value) return this.rotateRight(node);
// Right Right Case
if (balance < -1 && value > node.right.value) return this.rotateLeft(node);
// Left Right Case
if (balance > 1 && value > node.left.value) {
node.left = this.rotateLeft(node.left);
return this.rotateRight(node);
}
// Right Left Case
if (balance < -1 && value < node.right.value) {
node.right = this.rotateRight(node.right);
return this.rotateLeft(node);
}
return node;
}
}