AVL tree is a self-balancing binary search tree, named after its inventors Adelson-Velsky and Landis.
The main purpose of AVL tree is to solve the balancing problem of binary search tree(BST). If you don't know what binary search tree is, please check my previous article first.
We know that, with binary search tree, we can search a value with average time complexity of O(log(n)).
2
1 5
4 6
But what is the balancing problem? Take a look a below.
1
2
3
4
5
6
As you can see, the values are the same, but with different shape and still a valid BST. So if the tree is like this, then search time complexity becomes O(n).
This is the balancing problem. To solve this problem, whenever inserting a new value into a BST, AVL tree use rotation operations to adjust the tree to make it balanced.
Before we get to how rotation works, we need to know how to measure balance first.
AVL tree uses the height to measure balance. A node's height is the distance between current node to the furthest null node from it. In AVL tree, we save the node's height in the node structure.
type AVLNode = {
data: number;
height: number;
left: AVLNode | null;
right: AVLNode | null;
};
So if we want to get the height of the node, we can just access this attribute.
private getHeight(node: AVLNode | null): number {
return node === null ? 0 : node.height;
}
And to calculate this height value, we can get it from its children's height when traversal the tree.
private updateHeight(node: AVLNode) {
node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
}
Now we know the node's height, next is to define balance. We call a node is balances if the difference between its children's height is either 0, 1 or -1.
private getBalance(node: AVLNode | null): number {
return node === null ? 0 : this.getHeight(node.left) - this.getHeight(node.right);
}
OK, now we know how to measure balance, next is to how to handle it when we see an imbalanced node.
AVL tree uses rotation operations to handle imbalance. Specifically, there are 4 cases.
First, right-right rotation.
Take a look a below tree.
3
2 null
1 x
We can see that the node with value 3 is imbalanced. What we will do now is called right-right rotation. As the name says, we move 1/2/3 to the right. And because 3 is already the root node, so we move 3 as the right child. The result after moving is like below.
2
1 3
x null
The next thing should be noted is that node x should be moved as the node 3's left child.
This rotation can be expressed in code like below.
private rotateRight(node: AVLNode): AVLNode {
if (node.left === null) return node;
const left = node.left;
const leftRight = left.right;
left.right = node;
node.left = leftRight;
return left;
}
Second, left-left rotation.
Just the the contrary of right-right rotation, we rotate node to the left, and move the root node as the left child.
1
null 2
x 3
The result after moving is like below.
2
1 3
null x
Still, one thing needs to be noted that the node x should be moved as node 1's right child.
This rotation can be expressed in code like below.
private rotateLeft(node: AVLNode): AVLNode {
if (node.right === null) return node;
const right = node.right;
const rightLeft = right.left;
right.left = node;
node.right = rightLeft;
return right;
}
Third, right-left rotation.
Take a look at the tree below.
1
null 3
2 null
We can see that, node 2 is imbalanced, but the tree's shape is different from the right-right case.
what we will do for this case is do a right rotation for node 3 first.
1
null 2
null 3
Now it becomes left-left case, do the left-left rotation for node 1.
2
1 3
This rotation can be expressed in code like below.
node.right = this.rotateRight(node.right as AVLNode);
this.rotateLeft(node);
Forth, left-right rotation.
Take a look at the tree below.
3
1
null 2
Just like the contrary of the thrid case, we rotate node 1 to the left first.
3
2
1
Now it becomes right-right case.
2
1 3
This rotation can be expressed in code like below.
node.left = this.rotateLeft(node.left as AVLNode);
this.rotateRight(node);
OK, now we only have one thing left, which is how to decide which case we should apply.
The answer is still to use balance. This logic can be seen more clearly in code.
const balance = this.getBalance(node);
if (balance > 1) {
if (this.getBalance(node.left) < 0) {
node.left = this.rotateLeft(node.left as AVLNode);
}
return this.rotateRight(node);
}
if (balance < -1) {
if (this.getBalance(node.right) > 0) {
node.right = this.rotateRight(node.right as AVLNode);
}
return this.rotateLeft(node);
}
OK, that's all. Now let's see all the code.
type AVLNode = {
data: number;
height: number;
left: AVLNode | null;
right: AVLNode | null;
};
class AVLTree {
private root: AVLNode | null = null;
public insert(data: number) {
this.root = this._insert(data, this.root);
}
private _insert(data: number, node: AVLNode | null): AVLNode {
if (node == null) {
return { data, height: 1, left: null, right: null };
}
if (data < node.data) {
node.left = this._insert(data, node.left);
} else if (data > node.data) {
node.right = this._insert(data, node.right);
} else {
return node;
}
// recursively update every node's height from bottom to top
this.updateHeight(node);
return this.applyRotation(node);
}
private updateHeight(node: AVLNode) {
node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
}
private getHeight(node: AVLNode | null): number {
return node === null ? 0 : node.height;
}
private getBalance(node: AVLNode | null): number {
return node === null ? 0 : this.getHeight(node.left) - this.getHeight(node.right);
}
private rotateRight(node: AVLNode): AVLNode {
if (node.left === null) return node;
const left = node.left;
const leftRight = left.right;
left.right = node;
node.left = leftRight;
this.updateHeight(node);
this.updateHeight(left);
return left;
}
private rotateLeft(node: AVLNode): AVLNode {
if (node.right === null) return node;
const right = node.right;
const rightLeft = right.left;
right.left = node;
node.right = rightLeft;
this.updateHeight(node);
this.updateHeight(right);
return right;
}
private applyRotation(node: AVLNode): AVLNode {
const balance = this.getBalance(node);
if (balance > 1) {
if (this.getBalance(node.left) < 0) {
node.left = this.rotateLeft(node.left as AVLNode);
}
return this.rotateRight(node);
}
if (balance < -1) {
if (this.getBalance(node.right) > 0) {
node.right = this.rotateRight(node.right as AVLNode);
}
return this.rotateLeft(node);
}
return node;
}
print() {
const q: (AVLNode | null)[] = [];
q.push(this.root)
while (true) {
const len = q.length;
for (let i = 0; i < len; i++) {
const v = q[i];
if (v !== null) {
q.push(v.left, v.right);
} else {
q.push(null, null);
}
}
const level = q.splice(0, len);
console.log(level.map(v => v === null ? "x" : v.data).join(" "));
if (q.every(v => v === null)) break;
}
}
}
And let's insert values to see the result.
const t = new AVLTree();
t.insert(1);
t.insert(2);
t.insert(3);
t.insert(4);
t.insert(5);
t.insert(6);
t.insert(7);
t.insert(8);
t.insert(9);
t.print()
Results after format by hand is as below. You can see that the self-balancing is working.
4
2 6
1 3 5 8
x x x x x x 7 9