AVL Tree

In this tutorial, you will learn what an avl tree is. Also, you will find working examples of various operations performed on an avl tree in C++ and Python.

AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.

AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.

---

Balance Factor

Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node.

Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree)

The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.

---

Python:

	# AVL tree implementation in Python
	import sys
	# Create a tree node
	class TreeNode(object):
	def __init__(self, key):
	self.key = key
	self.left = None
	self.right = None
	self.height = 1
	class AVLTree(object):
	# Function to insert a node
	def insert_node(self, root, key):
	# Find the correct location and insert the node
	if not root:
	return TreeNode(key)
	elif key < root.key:
	root.left = self.insert_node(root.left, key)
	else:
	root.right = self.insert_node(root.right, key)
	root.height = 1 + max(self.getHeight(root.left),
	self.getHeight(root.right))
	# Update the balance factor and balance the tree
	balanceFactor = self.getBalance(root)
	if balanceFactor > 1:
	if key < root.left.key:
	return self.rightRotate(root)
	else:
	root.left = self.leftRotate(root.left)
	return self.rightRotate(root)
	if balanceFactor < -1:
	if key > root.right.key:
	return self.leftRotate(root)
	else:
	root.right = self.rightRotate(root.right)
	return self.leftRotate(root)
	return root
	# Function to delete a node
	def delete_node(self, root, key):
	# Find the node to be deleted and remove it
	if not root:
	return root
	elif key < root.key:
	root.left = self.delete_node(root.left, key)
	elif key > root.key:
	root.right = self.delete_node(root.right, key)
	else:
	if root.left is None:
	temp = root.right
	root = None
	return temp
	elif root.right is None:
	temp = root.left
	root = None
	return temp
	temp = self.getMinValueNode(root.right)
	root.key = temp.key
	root.right = self.delete_node(root.right,
	temp.key)
	if root is None:
	return root
	# Update the balance factor of nodes
	root.height = 1 + max(self.getHeight(root.left),
	self.getHeight(root.right))
	balanceFactor = self.getBalance(root)
	# Balance the tree
	if balanceFactor > 1:
	if self.getBalance(root.left) >= 0:
	return self.rightRotate(root)
	else:
	root.left = self.leftRotate(root.left)
	return self.rightRotate(root)
	if balanceFactor < -1:
	if self.getBalance(root.right) <= 0:
	return self.leftRotate(root)
	else:
	root.right = self.rightRotate(root.right)
	return self.leftRotate(root)
	return root
	# Function to perform left rotation
	def leftRotate(self, z):
	y = z.right
	T2 = y.left
	y.left = z
	z.right = T2
	z.height = 1 + max(self.getHeight(z.left),
	self.getHeight(z.right))
	y.height = 1 + max(self.getHeight(y.left),
	self.getHeight(y.right))
	return y
	# Function to perform right rotation
	def rightRotate(self, z):
	y = z.left
	T3 = y.right
	y.right = z
	z.left = T3
	z.height = 1 + max(self.getHeight(z.left),
	self.getHeight(z.right))
	y.height = 1 + max(self.getHeight(y.left),
	self.getHeight(y.right))
	return y
	# Get the height of the node
	def getHeight(self, root):
	if not root:
	return 0
	return root.height
	# Get balance factore of the node
	def getBalance(self, root):
	if not root:
	return 0
	return self.getHeight(root.left) - self.getHeight(root.right)
	def getMinValueNode(self, root):
	if root is None or root.left is None:
	return root
	return self.getMinValueNode(root.left)
	def preOrder(self, root):
	if not root:
	return
	print("{0} ".format(root.key), end="")
	self.preOrder(root.left)
	self.preOrder(root.right)
	# Print the tree
	def printHelper(self, currPtr, indent, last):
	if currPtr != None:
	sys.stdout.write(indent)
	if last:
	sys.stdout.write("R----")
	indent += " "
	else:
	sys.stdout.write("L----")
	indent += "| "
	print(currPtr.key)
	self.printHelper(currPtr.left, indent, False)
	self.printHelper(currPtr.right, indent, True)
	myTree = AVLTree()
	root = None
	nums = [33, 13, 52, 9, 21, 61, 8, 11]
	for num in nums:
	root = myTree.insert_node(root, num)
	myTree.printHelper(root, "", True)
	key = 13
	root = myTree.delete_node(root, key)
	print("After Deletion: ")
	myTree.printHelper(root, "", True)

view raw avl_tree.py hosted with ❤ by GitHub

C++:

	// AVL tree implementation in C++
	#include <iostream>
	using namespace std;
	class Node {
	public:
	int key;
	Node *left;
	Node *right;
	int height;
	};
	int max(int a, int b);
	// Calculate height
	int height(Node *N) {
	if (N == NULL)
	return 0;
	return N->height;
	}
	int max(int a, int b) {
	return (a > b) ? a : b;
	}
	// New node creation
	Node *newNode(int key) {
	Node *node = new Node();
	node->key = key;
	node->left = NULL;
	node->right = NULL;
	node->height = 1;
	return (node);
	}
	// Rotate right
	Node *rightRotate(Node *y) {
	Node *x = y->left;
	Node *T2 = x->right;
	x->right = y;
	y->left = T2;
	y->height = max(height(y->left),
	height(y->right)) +
	1;
	x->height = max(height(x->left),
	height(x->right)) +
	1;
	return x;
	}
	// Rotate left
	Node *leftRotate(Node *x) {
	Node *y = x->right;
	Node *T2 = y->left;
	y->left = x;
	x->right = T2;
	x->height = max(height(x->left),
	height(x->right)) +
	1;
	y->height = max(height(y->left),
	height(y->right)) +
	1;
	return y;
	}
	// Get the balance factor of each node
	int getBalanceFactor(Node *N) {
	if (N == NULL)
	return 0;
	return height(N->left) -
	height(N->right);
	}
	// Insert a node
	Node *insertNode(Node *node, int key) {
	// Find the correct postion and insert the node
	if (node == NULL)
	return (newNode(key));
	if (key < node->key)
	node->left = insertNode(node->left, key);
	else if (key > node->key)
	node->right = insertNode(node->right, key);
	else
	return node;
	// Update the balance factor of each node and
	// balance the tree
	node->height = 1 + max(height(node->left),
	height(node->right));
	int balanceFactor = getBalanceFactor(node);
	if (balanceFactor > 1) {
	if (key < node->left->key) {
	return rightRotate(node);
	} else if (key > node->left->key) {
	node->left = leftRotate(node->left);
	return rightRotate(node);
	}
	}
	if (balanceFactor < -1) {
	if (key > node->right->key) {
	return leftRotate(node);
	} else if (key < node->right->key) {
	node->right = rightRotate(node->right);
	return leftRotate(node);
	}
	}
	return node;
	}
	// Node with minimum value
	Node *nodeWithMimumValue(Node *node) {
	Node *current = node;
	while (current->left != NULL)
	current = current->left;
	return current;
	}
	// Delete a node
	Node *deleteNode(Node *root, int key) {
	// Find the node and delete it
	if (root == NULL)
	return root;
	if (key < root->key)
	root->left = deleteNode(root->left, key);
	else if (key > root->key)
	root->right = deleteNode(root->right, key);
	else {
	if ((root->left == NULL) ||
	(root->right == NULL)) {
	Node *temp = root->left ? root->left : root->right;
	if (temp == NULL) {
	temp = root;
	root = NULL;
	} else
	*root = *temp;
	free(temp);
	} else {
	Node *temp = nodeWithMimumValue(root->right);
	root->key = temp->key;
	root->right = deleteNode(root->right,
	temp->key);
	}
	}
	if (root == NULL)
	return root;
	// Update the balance factor of each node and
	// balance the tree
	root->height = 1 + max(height(root->left),
	height(root->right));
	int balanceFactor = getBalanceFactor(root);
	if (balanceFactor > 1) {
	if (getBalanceFactor(root->left) >= 0) {
	return rightRotate(root);
	} else {
	root->left = leftRotate(root->left);
	return rightRotate(root);
	}
	}
	if (balanceFactor < -1) {
	if (getBalanceFactor(root->right) <= 0) {
	return leftRotate(root);
	} else {
	root->right = rightRotate(root->right);
	return leftRotate(root);
	}
	}
	return root;
	}
	// Print the tree
	void printTree(Node *root, string indent, bool last) {
	if (root != nullptr) {
	cout << indent;
	if (last) {
	cout << "R----";
	indent += " ";
	} else {
	cout << "L----";
	indent += "| ";
	}
	cout << root->key << endl;
	printTree(root->left, indent, false);
	printTree(root->right, indent, true);
	}
	}
	int main() {
	Node *root = NULL;
	root = insertNode(root, 33);
	root = insertNode(root, 13);
	root = insertNode(root, 53);
	root = insertNode(root, 9);
	root = insertNode(root, 21);
	root = insertNode(root, 61);
	root = insertNode(root, 8);
	root = insertNode(root, 11);
	printTree(root, "", true);
	root = deleteNode(root, 13);
	cout << "After deleting " << endl;
	printTree(root, "", true);
	}

view raw avl_tree.cpp hosted with ❤ by GitHub

---

Complexities of Different Operations on an AVL Tree

---

AVL Tree Applications

• For indexing large records in databases
• For searching in large databases