AVL Tree
Overview
In its base, AVL tree is a Binary Search Tree but on top of that - it's a self-balancing tree which makes up for an efficient insertion, deletion and search.
The balance is achieved by a property called 'Balance Factor' which is actually pretty simple. It's a number given for each node based on the height (edges from node to a leaf node) difference between its left and right subtrees. For AVL tree to be considered 'balanced' and maintaining its AVL property, the balance factor for each node should be -1, 0 or 1. Less or more than that means that we have a node for which the height difference is too big and the tree gets too heavy on one side.
So, how an AVL tree balances itself if the balance factor gets 'out of hand'? By rotation! It's very difficult to grasp theoretically but I think the animation makes it easy to see and think of. We just re-arrange the AVL tree nodes to once again balance it and also make sure it's still a valid Binary Search Tree. That being said, we have 4 types of rotation and we make a decision which one to use based on where the tree is out of balance.
-
Left Rotation - When the left side of a tree is too heavy, and the left side of its left child is heavier than its right side.
-
Right Rotaion - The opposite - when the right side of a tree is too heavy, and the right side of its right child is heavier than its left side.
These were single rotation - only one rotation movement needed. The other 2 types of rotation are double / chained rotations:
-
Left-Right - When the left side of a tree is too heavy, and the right side of its left child is heavier than its left side, we do a left-right rotation. We simply do left rotation first and then right rotation
-
Right-Left - Exactly the opposite - when the right side of a tree is too heavy, and the left side of its right child is heavier than its right side, we do a right-left rotation.
These balancing operations allow the AVL tree to achieve O(log n) time complexity of insert, delete and search operations. The animation on top of this page builds the tree via insertion. Here's another one that shows how deletion works:
As you can see - we replace the node to be deleted with the in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree) and then rebalance the tree.
In some cases, we don't even have to rebalance the tree. For instance, when deleting a leaf node or deleting a node with only single child.
In conclusion - AVL tree is mostly preferred for frequent inserts and deletes because they lead to frequent rebalancing which on the other hand, keeps searching in the tree always efficient and quick.
As a downside, obviously, the rebalancing rotations add a lot of complexity so decision on when to use AVL tree should be done carefully, taking into consideration other self-balancing trees like the famous one we will see in next section - Red-Black Tree.
Code
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def get_height(self, node):
return node.height if node else 0
def get_balance_factor(self, node):
return self.get_height(node.left) - self.get_height(node.right)
def update_height(self, node):
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
def rotate_right(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
self.update_height(y)
self.update_height(x)
return x
def rotate_left(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
self.update_height(x)
self.update_height(y)
return y
def balance(self, node):
if not node:
return None
self.update_height(node)
balance_factor = self.get_balance_factor(node)
if balance_factor > 1:
if self.get_balance_factor(node.left) < 0:
node.left = self.rotate_left(node.left)
return self.rotate_right(node)
if balance_factor < -1:
if self.get_balance_factor(node.right) > 0:
node.right = self.rotate_right(node.right)
return self.rotate_left(node)
return node
def insert(self, value):
self.root = self.insert_node(self.root, value)
def insert_node(self, node, value):
if not node:
return Node(value)
if value < node.value:
node.left = self.insert_node(node.left, value)
elif value > node.value:
node.right = self.insert_node(node.right, value)
else:
return node
return self.balance(node)
def in_order_traversal(self, node):
if node:
self.in_order_traversal(node.left)
print(node.value, end=" ")
self.in_order_traversal(node.right)
# Example usage:
avl_tree = AVLTree()
avl_tree.insert(22)
avl_tree.insert(25)
avl_tree.insert(33)
avl_tree.insert(7)
avl_tree.insert(1)
avl_tree.insert(16)
avl_tree.insert(27)
avl_tree.in_order_traversal(avl_tree.root) # Output: 1 7 16 22 25 27 33
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
}
class AVLTree {
constructor() {
this.root = null;
}
// Get the height of a node (handles null nodes as well)
getHeight(node) {
return node ? node.height : 0;
}
// Calculate the balance factor of a node
getBalanceFactor(node) {
return this.getHeight(node.left) - this.getHeight(node.right);
}
// Update the height of a node based on its children's heights
updateHeight(node) {
node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
}
// Right rotation
rotateRight(y) {
const x = y.left;
const T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
this.updateHeight(y);
this.updateHeight(x);
return x;
}
// Left rotation
rotateLeft(x) {
const y = x.right;
const T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
this.updateHeight(x);
this.updateHeight(y);
return y;
}
// Rebalance the tree starting from a given node
balance(node) {
if (!node) return null;
// Update height of this node
this.updateHeight(node);
// Check the balance factor and perform rotations if needed
const balanceFactor = this.getBalanceFactor(node);
if (balanceFactor > 1) {
if (this.getBalanceFactor(node.left) < 0) {
node.left = this.rotateLeft(node.left);
}
return this.rotateRight(node);
}
if (balanceFactor < -1) {
if (this.getBalanceFactor(node.right) > 0) {
node.right = this.rotateRight(node.right);
}
return this.rotateLeft(node);
}
return node;
}
// Insert a value into the AVL tree
insert(value) {
this.root = this.insertNode(this.root, value);
}
insertNode(node, value) {
if (!node) {
return new Node(value);
}
if (value < node.value) {
node.left = this.insertNode(node.left, value);
} else if (value > node.value) {
node.right = this.insertNode(node.right, value);
} else {
// Duplicate values are not allowed in this implementation
return node;
}
return this.balance(node);
}
// In-order traversal to get sorted values
inOrderTraversal(node, callback) {
if (node) {
this.inOrderTraversal(node.left, callback);
callback(node.value);
this.inOrderTraversal(node.right, callback);
}
}
// Public method to get sorted values of the tree
getSortedValues() {
const sortedValues = [];
this.inOrderTraversal(this.root, (value) => sortedValues.push(value));
return sortedValues;
}
}
const avlTree = new AVLTree();
avlTree.insert(22);
avlTree.insert(25);
avlTree.insert(33);
avlTree.insert(7);
avlTree.insert(1);
avlTree.insert(16);
avlTree.insert(27);
console.log(avlTree.getSortedValues());
class Node {
int value;
Node left;
Node right;
int height;
Node(int value) {
this.value = value;
this.height = 1;
}
}
public class AVLTree {
Node root;
int getHeight(Node node) {
return node != null ? node.height : 0;
}
int getBalanceFactor(Node node) {
return getHeight(node.left) - getHeight(node.right);
}
void updateHeight(Node node) {
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
Node rotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
updateHeight(y);
updateHeight(x);
return x;
}
Node rotateLeft(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
updateHeight(x);
updateHeight(y);
return y;
}
Node balance(Node node) {
if (node == null) return null;
updateHeight(node);
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1) {
if (getBalanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
}
return rotateRight(node);
}
if (balanceFactor < -1) {
if (getBalanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
}
return rotateLeft(node);
}
return node;
}
Node insert(Node node, int value) {
if (node == null) return new Node(value);
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
} else {
return node;
}
return balance(node);
}
void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.value + " ");
inOrderTraversal(node.right);
}
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
avlTree.root = avlTree.insert(avlTree.root, 22);
avlTree.root = avlTree.insert(avlTree.root, 25);
avlTree.root = avlTree.insert(avlTree.root, 33);
avlTree.root = avlTree.insert(avlTree.root, 7);
avlTree.root = avlTree.insert(avlTree.root, 1);
avlTree.root = avlTree.insert(avlTree.root, 16);
avlTree.root = avlTree.insert(avlTree.root, 27);
avlTree.inOrderTraversal(avlTree.root); // Output: 1 7 16 22 25 27 33
}
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node* left;
struct Node* right;
int height;
};
int max(int a, int b) {
return (a > b) ? a : b;
}
int getHeight(struct Node* node) {
return (node) ? node->height : 0;
}
int getBalanceFactor(struct Node* node) {
return getHeight(node->left) - getHeight(node->right);
}
struct Node* newNode(int value) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->value = value;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
struct Node* rotateRight(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
struct Node* rotateLeft(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
struct Node* balance(struct Node* node) {
if (!node) return NULL;
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1) {
if (getBalanceFactor(node->left) < 0) {
node->left = rotateLeft(node->left);
}
return rotateRight(node);
}
if (balanceFactor < -1) {
if (getBalanceFactor(node->right) > 0) {
node->right = rotateRight(node->right);
}
return rotateLeft(node);
}
return node;
}
struct Node* insert(struct Node* node, int value) {
if (!node) return newNode(value);
if (value < node->value) {
node->left = insert(node->left, value);
}
else if (value > node->value) {
node->right = insert(node->right, value);
}
else {
return node;
}
return balance(node);
}
void inOrderTraversal(struct Node* node) {
if (node) {
inOrderTraversal(node->left);
printf("%d ", node->value);
inOrderTraversal(node->right);
}
}
int main() {
struct Node* root = NULL;
root = insert(root, 22);
root = insert(root, 25);
root = insert(root, 33);
root = insert(root, 7);
root = insert(root, 1);
root = insert(root, 16);
root = insert(root, 27);
inOrderTraversal(root); // Output: 1 7 16 22 25 27 33
return 0;
}
class Node {
public $value;
public $left;
public $right;
public $height;
public function __construct($value) {
$this->value = $value;
$this->height = 1;
}
}
class AVLTree {
private $root;
private function getHeight($node) {
return $node ? $node->height : 0;
}
private function getBalanceFactor($node) {
return $this->getHeight($node->left) - $this->getHeight($node->right);
}
private function updateHeight($node) {
$node->height = max($this->getHeight($node->left), $this->getHeight($node->right)) + 1;
}
private function rotateRight($y) {
$x = $y->left;
$T2 = $x->right;
$x->right = $y;
$y->left = $T2;
$this->updateHeight($y);
$this->updateHeight($x);
return $x;
}
private function rotateLeft($x) {
$y = $x->right;
$T2 = $y->left;
$y->left = $x;
$x->right = $T2;
$this->updateHeight($x);
$this->updateHeight($y);
return $y;
}
private function balance($node) {
if (!$node) return null;
$this->updateHeight($node);
$balanceFactor = $this->getBalanceFactor($node);
if ($balanceFactor > 1) {
if ($this->getBalanceFactor($node->left) < 0) {
$node->left = $this->rotateLeft($node->left);
}
return $this->rotateRight($node);
}
if ($balanceFactor < -1) {
if ($this->getBalanceFactor($node->right) > 0) {
$node->right = $this->rotateRight($node->right);
}
return $this->rotateLeft($node);
}
return $node;
}
public function insert($value) {
$this->root = $this->insertNode($this->root, $value);
}
private function insertNode($node, $value) {
if (!$node) {
return new Node($value);
}
if ($value < $node->value) {
$node->left = $this->insertNode($node->left, $value);
} elseif ($value > $node->value) {
$node->right = $this->insertNode($node->right, $value);
} else {
return $node;
}
return $this->balance($node);
}
private function inOrderTraversal($node) {
if ($node) {
$this->inOrderTraversal($node->left);
echo $node->value . " ";
$this->inOrderTraversal($node->right);
}
}
public function printInOrder() {
$this->inOrderTraversal($this->root);
}
}
// Example usage:
$avlTree = new AVLTree();
$avlTree->insert(22);
$avlTree->insert(25);
$avlTree->insert(33);
$avlTree->insert(7);
$avlTree->insert(1);
$avlTree->insert(16);
$avlTree->insert(27);
$avlTree->printInOrder(); // Output: 1 7 16 22 25 27 33