Introduction To AVL Trees

Introduction

Trees are one of the most helpful data structures that are often used to perform operations like search, insertion, and deletion efficiently.

In this article, we will learn about AVL trees from scratch. 

This article is a part of a complete blog series on AVL trees. The contents are divided into three blogs as follows:

• Introduction to AVL Trees
• Insertion in AVL Tree
• Deletion in AVL Tree 

This article will address all the important points and terms related to AVL trees, starting with its definition, why we need them, their advantages and properties. 

Before moving further, the following are the prerequisites you must understand to follow along with this article -

• Binary tree
• Binary Search Tree

What are AVL Trees?

AVL trees are nothing but self-balancing binary search trees. 

What do you mean by a self-balancing tree?

The height of the left and the right subtrees of every node differs by at most 1, which implies the difference between the heights will always be either 1,0 or -1.

So, AVL trees are an optimised version of binary search trees named after its inventors G.M. Abelson-Velvety and E.M. Landis, in 1962. It was an attempt to improve the performance of Binary Search Trees.

Examples - 

The tree in figure (a) is an AVL tree. As you can see, for every node, the height difference between its left subtree and right subtree does not exceed mod(1). 

While in figure (b), if you check the node with value 3, its left subtree has height=2 while the right subtree’s height=0. So, the difference is mod(2-0) = 2. Hence, the AVL property is not satisfied, and it is not an AVL tree.

Balance Factor in AVL trees

AVL trees use the balance factor to get a height-balanced tree.

Let’s look at an example tree that shows the balance factor of each node - 

In the above example, the balance factor of every node is between -1 and +1. So, it is an AVL tree.

Properties of balance factor - 

• If a subtree has a balance factor>0, then the subtree is called left-heavy as the height of the left subtree is greater than the height of its right subtree, so the left subtree has more nodes than the right subtree.

• If a subtree has a balance factor<0, then the subtree is called right-heavy as the height of the left subtree is smaller than the height of its right subtree, so the right subtree has more nodes than the left subtree.

• If the balance factor=0, the subtree is perfectly balanced, with both left and right subtrees having equal heights.

Why AVL trees?

In a binary search tree, we know that the time complexity of all the operations like search, insertion, and deletion is O(h), where h is the height of the binary search tree. The best case is when the height of a BST is O(logn), i.e. when the tree is balanced. But this may not be possible in every case.

Consider this sequence of insertions in a BST - 

1,2,3,4

You will get a BST like this -

So, when the nodes are in increasing or decreasing order, then the height of a BST is O(n). Hence all the operations take place in O(n), which is the worst case.

AVL tree balances itself such that its height always remains O(logn) by preventing it from being skewed and thus ensuring that the upper bound for all the operations, whether an insertion, deletion or search, is O(logn).

The complexity of Different Operations in AVL Tree

Representation of AVL Tree

An AVL Tree is made up of nodes where each node contains - 

• Data
• Pointer to left subtree
• Pointer to right subtree
• Balance factor of the subtree rooted at this node

The structure of each node is defined as:

Height balancing operations - Rotations in AVL Tree

Different operations which we can perform on an AVL tree are:

• Search
• Insertion
• Deletion
• Traversal

Among these operations, the search and traversal operations do not affect the height of the AVL tree. But when we insert a new node in the tree or, say, delete a node, it may change the height of a subtree. This, in turn, can change the balance factor of a node and violate the height-balanced property of AVL trees.

Why do we need rotations in AVL trees?

• Rotations are used to balance the tree whenever an imbalance is caused due to the insertion of new nodes or the deletion of existing nodes. 

• An unbalanced state is a state in which any subtree has a balance factor of greater than 1 or less than -1. Any tree with a difference between the heights of its two subtrees greater than 1 is considered unbalanced. 

Let us see when each of these rotations is used - 

• Left Rotation (LL - Single Rotation) 

Left rotation is performed when the imbalance is created due to the insertion of a new node in the right subtree of a right subtree or when a subtree becomes right heavy.

Consider this example - 

Node 6 has a balance factor of -2 after the insertion of node 10. After a single rotation towards the left, node 8 becomes the root and node 6 becomes its left child. By doing this, the BST property also remains intact, and the tree becomes height-balanced.

• Right Rotation (RR - Single Rotation)

Right rotation is needed when the imbalance is created due to the insertion of a node in the left subtree of a left subtree or when a subtree becomes left heavy.

See this figure:

Node 3 has a balance factor of 2, so it is unbalanced. After a single rotation towards the right, node 2 becomes the root and node 3 becomes its right child. And the new root, i.e., node 2, has a balance factor of 0. Hence,  the tree becomes balanced.

• Left-Right Rotation (LR - Double Rotation) 

It is a double rotation in which a right rotation follows a left rotation. It is needed when a new node is inserted in the left subtree of the right subtree of a node.

Node 1 is inserted as the left child of node 2, which is the right child of node 5. See that the balance factor of node 5 becomes 2 after insertion of node 1. Firstly, we do a left rotation, but the tree is still not balanced. If you see carefully, the tree is left heavy after this step, so we need a right rotation. After which node 1, i.e. the newly inserted node, becomes the root.

• Right-Left Rotation (RL - Double Rotation)

In this, a right rotation is followed by a left rotation. It is needed when a node is inserted in the left subtree of the right subtree of a node. 

Insertion of node 6 creates an imbalance. Firstly, we perform a right rotation which makes node 6 a parent of node 8 and node 8 becomes the right child of node 6. Next, we perform left rotation on the resulting right-heavy tree and finally, the tree becomes balanced.

Advantages of AVL Trees

• The AVL tree is always height-balanced, and its height is always O(log N), where N is the total number of nodes in the tree.
• The time complexities of all the operations are better than BSTs as the AVL tree has the worst-case time complexity of all operations as O(log N), while in BST, it is O(N).
• AVL trees have self-balancing properties.

Application of AVL Trees

AVL trees are used extensively in database applications in which frequent lookups for data are required, i.e. the frequency of search operation is more. At the same time, the deletions and insertions are fewer.

Frequently Asked Questions

1. Are all Binary Search trees AVL?
   No. All AVL trees are binary search trees, but all binary search trees need not be AVL.
    
2. Which is better - A binary search tree or AVL tree?
   AVL tree has an added advantage over binary search trees as it guarantees that the maximum time complexity for all the operations will never exceed O(logN).
    
3. Which is better: AVL tree or Red-Black Tree?
   AVL tree provides faster lookups than Red-Black tree as they are strictly balanced. Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.
    
4. Can a tree be both a BST and AVL tree?
   Yes, in fact, all the AVL trees are BSTs.

Key Takeaways

The important points we learnt in this article are:

• AVL trees are self-balancing binary search trees.
• The fundamental attribute of the AVL tree is the balance factor. 
• The balance factor is the difference between the height of the left and right subtrees of a node.The allowed values of the balance factor are -1, 0, and +1.
• Rotation is required when insertion or deletion creates an imbalance in any of the subtrees.
• The time complexity of insert, delete, and search operation is O(log N).
• AVL trees follow all the properties of Binary Search Trees.

Now that you are well equipped with the basics of AVL trees, you can further read the next two parts of this blog: insertion and deletion in AVL Trees from codestudio blogs.

Check out this problem - Diameter Of Binary Tree

Do practice questions of AVL trees here to strengthen your understanding.