AVL Tree in Data Structures

AVL Trees is one of the fundamental concepts of Data Structures used in Computer Science to store and retrieve data efficiently. An AVL tree in Data Structures is a self-balancing Binary Search Tree that guarantees all primitive operations, i.e., searching, insertion, and deletion, will take place quickly even if the dataset grows in size. Understanding AVL trees and how they work is important for students and developers since they are the underlying structure for managing memory efficiently, database indexing, and real-time systems. This article will cover AVL trees in detail, including concepts, rotations, operations, implementation, comparisons, applications, time complexities, and common interview questions.

What is an AVL Tree in Data Structure?

An AVL tree in data structure is a self-balancing binary search tree. A binary search tree is a binary tree (has at most two children) that follows an ordering pattern, left < node < right. A self-balancing tree is, on the other hand, one whose balance factor (the height difference between right and left subtrees) is at most one. 

Therefore, an AVL Tree is a binary search tree (BST) in which the height difference (balance factor) between the left and right subtrees of every node is at most 1. 

It was invented by G.M. Adelson-Velsky and E.M. Landis in 1962, and that’s why it is named AVL.

Key Concepts of AVL Tree

There are three main concepts that you should be aware of to properly understand AVL trees in data structures:

Unlock Python: Supercharge Your Coding Skills

Practice coding with hands-on projects and examples to quickly level up your Python skills.

Explore Program

1. Balance Factor

As discussed earlier, the balance factor is the difference between the right subtree and the left subtree of a node. For all the nodes in an AVL tree, this factor should be at most one. Mathematically, 

Balance Factor (BF) = Height(Left Subtree) − Height(Right Subtree), and

-1 <= BF <= 1

Now, the AVL tree is self-balancing, which means that when the tree becomes unbalanced, it automatically rebalances itself by rotation mechanisms. 

Note: The negative in the balance factor value signifies the direction (left or right). It does not affect the value.

2. Height of the Tree

To calculate the balance factor, we must know the height of each node. The height is calculated by the number of edges on the longest path from that node down to a leaf node. The mathematical formula to calculate the same is

Height(node) = 1 + max(Height(node.left),Height(node.right))

For example,

Here,

• Height of node 10 = 0
• Height of node 20 = 1 + max(Height(10), Height(None)) = 1 + max(0, -1) = 1
• Height of node 40 = 0
• Height of node 30 = 1 + max(Height(20), Height(40)) = 1 + max(1, 0) = 2

3. AVL Tree Properties

There are certain properties a tree must maintain all the time to be called an AVL tree in data structures. While writing code implementation, remember to keep these properties in check:

1.  Height-Balanced Structure: The difference between the heights of the left and right subtrees of any node never exceeds 1, ensuring minimal height and preventing skewed structures.
2. Automatic Rebalancing: After every insertion or deletion, the tree checks for imbalance and restores balance using rotations (LL, RR, LR, RL).
3. Optimal Time Complexity: All fundamental operations like search, insert, and delete have a guaranteed time complexity of O(log n) because the tree height grows logarithmically with the number of nodes.
4. Height Constraint: The maximum height of an AVL tree with n nodes is O(log n), keeping the tree shallow and efficient for large datasets.
5. Consistent Inorder Traversal: Regardless of how the tree rebalances, the inorder traversal of an AVL tree always yields elements in sorted order.
6. Multiple Valid Structures: For the same set of input keys, different AVL tree shapes may exist, but all maintain the same balanced property and in-order sequence.

Rotations in AVL Tree in Data Structures

Rotations are an important concept in AVL trees due to their self-balancing nature. When an insertion or deletion causes an AVL tree to become unbalanced (balance factor > 1 or <-1), we perform rotations to restore balance. Rotations rearrange the tree nodes while maintaining the BST property. There are four main types of rotations available. Let us look at them one by one:

1. LL Rotation (Left-Left Rotation)

When a new node is added in the left subtree of the left child, which makes the AVL tree unbalanced, we apply LL rotation. It is basically a single right rotation. Let us understand with an example:

Let us calculate the balance factor of node 30, 

BF(30) = Height(Left) – Height(Right) = 2 – 0 = +2, which is more than 1. Therefore, we must balance the tree again. 

Using LL rotation, we will perform a single rotation to the right. 

Now, the balance factor is 0 for all the nodes, meaning that the balance of the AVL tree is restored.

2. RR Rotation (Right-Right Rotation)

RR rotation is used when the tree becomes unbalanced because a new node was added in the right subtree of its right child. In such a case, we will perform a single left rotation on the node. For example, here the node 10 is unbalanced since the BF is -2 ( which is more than 1, -ve is just the direction). 

By rotating Node 10 to the left once, we get:

Now, every node has a balance factor of zero.

3. LR Rotation (Left-Right Rotation)

LR rotation is used when the tree becomes unbalanced due to a new node in the right subtree of its left child. This is a double rotation, which means first you rotate the left child towards the left and then rotate the unbalanced node towards the right. Let us understand this better with the help of an example.

In the example above, the unbalanced node is Node 30, and the left child is Node 10.

• We will rotate Node 10 towards the left. 

• And then rotate Node 30 towards the right.

Now, the tree has again become balanced, and it is now an AVL tree in data structure.

4. RL Rotation (Right-Left Rotation)

This is the final kind of rotation, which occurs when the AVL tree gets unbalanced due to a new node in the left subtree of its right child. Let us take a simple example.

As the name suggests, we will rotate the right child to the right and the unbalanced node towards the left. For example, 

Here, Node 10 is unbalanced. To balance itself, first Node 30 will be rotated towards the right, and then Node 10 will be rotated to the left. 

Operations on AVL Tree

Let us now understand a few basic operations that are performed on the AVL tree. These operations are insertion, deletion, and searching. All of these operations we will understand using the rebalancing of the nodes as well.

1. Insertion with Rebalancing

When inserting a node in an AVL tree in data structures, you must follow the rules of a binary search tree. These rules are:

• If the value is smaller than the node, go to the left subtree.
• If the value of the new node is greater than the node, then go to the right subtree.

Once you insert the nodes, you must rebalance the tree. Calculate the balance factor and apply the required rotation from the four (LL, LR, RR, RL)

For example, in the tree given below, we have to add 25.

Since 25 > 20, it will go in the right subtree of Node 20. This insertion operation will make the Node 30 unbalanced with a BF of +2. Once you apply the LR rotation, the tree will become balanced. 

2. Deletion with Rebalancing

The deletion operation also has a lot of chances of unbalancing the AVL tree since we will be removing a node. 

When we delete from an AVL tree follows standard BST deletion rules:

• First, you remove the target node and then,
• Check if the node has two children and replace it with its inorder predecessor or successor.
• Once deleted, check the balance factors from the deleted node up to the root. If the tree becomes unbalanced, apply appropriate rotation(s) to restore AVL balance.

For Example, from the tree given below, let us remove Node 10.

When Node 10 is removed, Node 20 does not become unbalanced. If it had made the tree unbalanced, then rotations were needed. 

3. Searching

The searching operation in the AVL tree is similar to that of the BST tree. You simply start at the root and keep comparing the target value with the current node.

• If the node is equal to the current node, then you have found the node.
• If the node is smaller, then you have to go to the left subtree.
• If the node is larger, then go to the right subtree.

This height-balanced property of the AVL tree is the reason why an AVL tree always has O(log n) time complexity for search operations.

For example, searching for 25 in the tree:

First, you will start at the root, which is 20, and compare it with 25. Since 25 > 20, you will go right. Next, you will encounter 30. Since 30 < 25, you will have to go left. The first node you encounter is 25. Therefore, you have found your node.

AVL Tree Implementation

In the earlier sections, we have explored all the theory related to the AVL tree. Let us now implement an AVL tree in data structures using Python, C++, and Java. To implement an AVL tree, we first need to define the node structure that will hold all the values and nodes. Then, we will implement insertion, deletion, and rotations. Below is a simple explanation with code examples in Python, Java, and C++.

Node Structure

Each node of the AVL tree will hold the following elements:

• key → the value of the node
• left → reference to the left child
• right → reference to the right child
• height → the height of the node (used to calculate balance factor)

Let us implement them in Python, Java, and C++:

AVL Tree in Data Structures in Python

Output:

Explanation: Here, in the AVL tree class, we defined a function to get the height of the tree, calculate the balance factor of the tree. Then, we have four rotation techniques: LL, LR, RL, and RR. And then, finally, we define the insert, delete, and search operations for the AVL tree in data structures. Then, using this class, we make an instance tree and try the inorder traversal. Since our example did not completely follow all the properties of the AVL tree (25 was not its correct position), it was fixed first before traversal.

AVL Tree in Data Structures in Java

Output:

Explanation: In this Java example of an AVL tree, we inserted the nodes in random order. It was then rearranged so that it followed the AVL tree properties, as you can see in the output.

AVL Tree in Data Structures in C++

Output:

Explanation: This example is the implementation of an AVL tree in data structures in the C++ programming language. 

AVL Tree vs Other Trees

In order to understand the efficiency and use cases of AVL Trees, they must be compared to other tree data structures that are popular tree data structures. The two most commonly done comparisons are AVL vs Binary Search Tree (BST) and AVL vs Red-Black Tree.

1. AVL Tree vs Binary Search Tree (BST)

A Binary Search Tree (BST) is a tree that models the hierarchical way of organizing and storing data that maintains the order and permits fast addition, deletion, and searching of data. However, if data is inserted into a BST in sorted order, the BST may become unbalanced, which may degrade the performance.

An AVL Tree is a self-balancing version of a BST, to make sure that for any left or right subtrees, the height difference between left and right subtrees never exceeds 1.

2. AVL Tree vs Red-Black Tree

Both AVL Trees and Red-Black Trees are self-balancing binary search trees, but they differ in how strictly they maintain balance and in their performance trade-offs

BST works best for situations where the application is simple and the dataset is short. An AVL tree works best for scenarios where you must perform search operations with guaranteed performance. Finally, a red-black tree is best when you must perform frequent insertions and deletions. 

Application of AVL Tree in Data Structures

AVL Trees can be used in several cases where the need to search, insert, or delete data quickly is paramount. AVL Trees also guarantee the search or update will remain efficient even if a lot of data is involved due to their self-balancing properties.

Some common real-world applications of AVL Trees include:

• Databases Indexing: AVL Trees are useful for databases to find data quickly. For example, if you are searching a database to find a student record by their student ID or name, the balanced tree will allow you to retrieve it much more efficiently than an unbalanced tree.
• Memory Management: The operating system and compilers use AVL Trees to track free memory. When a program needs to allocate memory, the OS can quickly find and allocate a suitable size using an AVL Tree.
• File Systems: Certain file systems use AVL Trees to organize files or data blocks. Accessing or updating files is more efficient since it can reduce overhead to search for or update a location, especially on systems with a great many files.
• Network Routing Tables: Routers use AVL Trees to track routing tables or paths to send data across a network. Due to the self-balancing properties of AVL Trees, when routes need to be updated to find the most efficient route, routers can do this much more quickly with an AVL Tree.
• Gaming and Simulation: AVL Trees help manage objects or entities in games and simulations. They allow quick access and updates, ensuring smooth gameplay or simulation performance.
• Compiler Design: Compilers use AVL Trees to store and manage symbol tables that contain variable names, functions, and class information, enabling quick lookups during code compilation.

Time Complexity of AVL Tree

One of the main advantages of using an AVL Tree is that it stays balanced after every insertion and deletion. Because of this, all major operations, such as searching, inserting, and deleting, take O(log n) time, where n is the number of nodes in the tree.

Here’s a quick breakdown of the time complexities for different operations:

Common Interview Questions on AVL Tree

AVL Trees are a popular topic in data structure and algorithm interviews. Interviewers often focus on understanding your knowledge of balanced trees, rotations, time complexity, and real-world applications. Being familiar with these questions can help you prepare effectively for technical interviews.

Here are the top 10 commonly asked AVL Tree interview questions:

• What is an AVL Tree?
• Who invented the AVL Tree?
• What is the balance factor in an AVL Tree?
• What are the different types of rotations in an AVL Tree?
• What is the time complexity of search, insertion, and deletion in an AVL Tree?
• How is an AVL Tree different from a regular Binary Search Tree (BST)?
• How is an AVL Tree different from a Red-Black Tree?
• Can duplicate keys be inserted in an AVL Tree?
• What is the maximum height of an AVL Tree with n nodes?
• When do rotations occur in an AVL Tree, and why are they necessary?

Master DSA Today - Accelerate Your Future

Enroll Now and Transform Your Future

Explore Program

Conclusion

An AVL tree is a reliable and efficient way to manage sorted data while maintaining balance automatically after every operation. Their self-balancing nature ensures that search, insertion, and deletion operations always perform in O(log n) time, which makes them ideal for applications that require consistent performance. From databases and file systems to compilers and gaming simulations, AVL trees are widely used in real-world scenarios. By understanding the key concepts, rotation mechanisms, and implementation techniques covered in this blog, you can confidently apply AVL trees in programming projects and prepare effectively for technical interviews.

AVL Tree in Data Structures – FAQs