AVL Tree - Insertion, Deletion and Rotation with Python Code

In this article, we will study what the AVL tree is and why we should use it. We will learn the rotation operations for the AVL tree along with the insertion and deletion operation and its algorithm steps and examples. We will also study the python code for the AVL tree along with the application, advantages, and disadvantages. So, let's get started!

What Is An AVL Tree?

The full form of an AVL is Adelson-Velskii and Landis also known as a height binary tree. A tree is called an AVL tree if each node of the tree possesses one of the following properties:

• A node is called left heavy if the longest path in its left subtree is one longer than the longest path of its right subtree
• A node is called right heavy if the longest path in the right subtree is one longer than the path in its left subtree
• A node is called balanced if the longest path in both the right and left subtree are equal.

AVL tree is a height-balanced tree where the difference between the heights of the right subtree and left subtree of every node is either -1, 0 or 1. The difference between the heights of the subtree is maintained by a factor named as balance factor. Therefore, we can define AVL as it is a balanced binary search tree where the balance factor of every node in the tree is either -1, 0, or +1. Here, the balance factor is calculated by the formula:

Balance Factor = Height Of Left Subtree - Height Of Right Subtree

As AVL is the height-balanced tree, it helps to control the height of the binary search tree and further help the tree to prevent skewing. When the binary tree gets skewed, the running time complexity becomes the worst-case scenario i.e O(n) but in the case of the AVL tree, the time complexity remains O(logn). Therefore, it is always advisable to use an AVL tree rather than a binary search tree.

Remember that every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL Tree.

AVL Rotation

When certain operations like insertion and deletion are performed on the AVL tree, the balance factor of the tree may get affected. If after the insertion or deletion of the element, the balance factor of any node is affected then this problem is overcome by using rotation. Therefore, rotation is used to restore the balance of the search tree. Rotation is the method of moving the nodes of trees either to left or to right to make the tree heighted balance tree.

There are total two categories of rotation which is further divided into two further parts:

1) Single Rotation 

Single rotation switches the roles of the parent and child while maintaining the search order. We rotate the node and its child, the child becomes a parent.

Single LL(Left Left) Rotation

Here, every node of the tree moves towards the left from its current position. Therefore, a parent becomes the right child in LL rotation. Let us see the below examples

Single RR(Right Right) Rotation

Here, every node of the tree moves towards the right from the current position. Therefore, the parent becomes a left child in RR rotation. Let us see the below example

2) Double Rotation

Single rotation does not fix the LR rotation and RL rotation. For this, we require double rotation involving three nodes. Therefore, double rotation is equivalent to the sequence of two single rotations.

LR(Left-Right) Rotation

The LR rotation is the process where we perform a single left rotation followed by a single right rotation. Therefore, first, every node moves towards the left and then the node of this new tree moves one position towards the right. Let us see the below example

RL (Right-Left) Rotation

The RL rotation is the process where we perform a single right rotation followed by a single left rotation. Therefore, first, every node moves towards the right and then the node of this new tree moves one position towards the left. Let us see the below example

Operations In AVL Tree

There are 2 major operations performed on the AVL tree

1. Insertion Operation
2. Deletion Operation

Let us study them one by one in detail

Insertion Operation In AVL Tree

In the AVL tree, the new node is always added as a leaf node. After the insertion of the new node, it is necessary to modify the balance factor of each node in the AVL tree using the rotation operations. The algorithm steps of insertion operation in an AVL tree are:

1. Find the appropriate empty subtree where the new value should be added by comparing the values in the tree
2. Create a new node at the empty subtree
3. The new node is a leaf ad thus will have a balance factor of zero
4. Return to the parent node and adjust the balance factor of each node through the rotation process and continue it until we are back at the root. Remember that the modification of the balance factor must happen in a bottom-up fashion

Example:

The root node is added as shown in the below figure

The node to the root node is added as shown below. Here the tree is balanced 

Then, The right child is added to the parent node. Here, the balance factor of the tree is changed, therefore, the LL rotation is performed and the tree becomes a balanced tree

Later, one more right child is added to the new tree as shown below

Again further, one more right child is added and the balance factor of the tree is changed. Therefore, again LL rotation is performed on the tree and the balance factor of the tree is restored as shown in the below figure

Deletion Operation In AVL

The deletion operation in the AVL tree is the same as the deletion operation in BST. In the AVL tree, the node is always deleted as a leaf node and after the deletion of the node, the balance factor of each node is modified accordingly. Rotation operations are used to modify the balance factor of each node. The algorithm steps of deletion operation in an AVL tree are:

1. Locate the node to be deleted
2. If the node does not have any child, then remove the node
3. If the node has one child node, replace the content of the deletion node with the child node and remove the node
4. If the node has two children nodes, find the inorder successor node ‘k' which has no child node and replace the contents of the deletion node with the ‘k’ followed by removing the node.
5. Update the balance factor of the AVL tree

Example:

Let us consider the below AVL tree with the given balance factor as shown in the figure below

Here, we have to delete the node '25' from the tree. As the node to be deleted does not have any child node, we will simply remove the node from the tree

After removal of the tree, the balance factor of the tree is changed and therefore, the rotation is performed to restore the balance factor of the tree and create the perfectly balanced tree

Python Code For AVL Tree

class treeNode(object):
	def __init__(self, value):
		self.value = value
		self.l = None
		self.r = None
		self.h = 1

class AVLTree(object):

	def insert(self, root, key):
	
		if not root:
			return treeNode(key)
		elif key < root.value:
			root.l = self.insert(root.l, key)
		else:
			root.r = self.insert(root.r, key)

		root.h = 1 + max(self.getHeight(root.l),
						self.getHeight(root.r))

		b = self.getBal(root)

		if b > 1 and key < root.l.value:
			return self.rRotate(root)

		if b < -1 and key > root.r.value:
			return self.lRotate(root)

		if b > 1 and key > root.l.value:
			root.l = self.lRotate(root.l)
			return self.rRotate(root)

		if b < -1 and key < root.r.value:
			root.r = self.rRotate(root.r)
			return self.lRotate(root)

		return root

	def lRotate(self, z):

		y = z.r
		T2 = y.l

		y.l = z
		z.r = T2

		z.h = 1 + max(self.getHeight(z.l),
						self.getHeight(z.r))
		y.h = 1 + max(self.getHeight(y.l),
						self.getHeight(y.r))

		return y

	def rRotate(self, z):

		y = z.l
		T3 = y.r

		y.r = z
		z.l = T3

		z.h = 1 + max(self.getHeight(z.l),
						self.getHeight(z.r))
		y.h = 1 + max(self.getHeight(y.l),
						self.getHeight(y.r))

		return y

	def getHeight(self, root):
		if not root:
			return 0

		return root.h

	def getBal(self, root):
		if not root:
			return 0

		return self.getHeight(root.l) - self.getHeight(root.r)

	def preOrder(self, root):

		if not root:
			return

		print("{0} ".format(root.value), end="")
		self.preOrder(root.l)
		self.preOrder(root.r)

Tree = AVLTree()
root = None

root = Tree.insert(root, 1)
root = Tree.insert(root, 2)
root = Tree.insert(root, 3)
root = Tree.insert(root, 4)
root = Tree.insert(root, 5)
root = Tree.insert(root, 6)

# Preorder Traversal
print("Preorder traversal of the",
	"constructed AVL tree is")
Tree.preOrder(root)
print()

Output

4 2 1 3 5 6

Time Complexity

For insertion operation, the running time complexity of the AVL tree is O(log n) for searching the position of insertion and getting back to the root. Similarly, the running time complexity of deletion operation of the AVL tree is also O(log n) for finding the node to be deleted and perform the operations later to modify the balance factor of the AVL tree. The time complexity of the AVL tree is faster and constant in comparison to the binary search tree. 

Advantages

• AVL tree is a height-balanced tree and therefore, the height of the tree never grows more than N where N is the number of nodes in the tree
• AVL trees have efficient search time complexity
• AVL tree has capabilities of self-balancing
• AVL tree is faster than the red-black tree as the AVL tree is more strictly balanced

Disadvantages

• AVL trees are very difficult to implement
• Constant factors for operations in AVL is very high

Applications of AVL Tree

1. AVL tree is used when there are few operations of insertion and deletion are performed
2. It is used when a short search time is needed
3. AVL tree is used when the data is almost sorted and only a few operations are required to sort it completely.
4. AVL tree is effective to search the data fast and efficiently in large databases
5. It is widely used for sorting sets and dictionary data
6. AVL tree is used in applications where the searching should be effective rather than database application

Conclusion

AVL tree is a self-balancing binary search tree where the balance of the tree is checked by the balance factor and modified whenever required by performing a rotation process. Insertion and Deletion time complexity of AVL tree is O(log n) and the searching time complexity of the AVL tree is O(n) which makes it better than binary search tree and red-black tree. AVL tree is used for faster and efficient searching of data in a large dataset and therefore, it is always recommended to learn and understand the AVL tree in detail.