AVL Trees

The AVL tree was introduced in the year 1962 by G.M. Adelson-Velsky and E.M. Landis.
AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a
binary search tree but it is a balanced tree. A binary tree is said to be balanced if, the
difference between the heights of left and right subtrees of every node in the tree is either
-1, 0 or +1. In other words, a binary tree is said to be balanced if the height of left and
right children of every node differ by either -1, 0 or +1. In an AVL tree, every node
maintains an extra information known as balance factor.

An AVL tree is defined as follows...

An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of
every node is either -1, 0 or +1.
Balance factor of a node is the difference between the heights of the left and right
subtrees of that node. The balance factor of a node is calculated either height of left subtree
- height of right subtree (OR) height of right subtree - height of left subtree. In the following
explanation, we calculate as follows...
Balance factor = heightOfLeftSubtree – heightOfRightSubtree
Example of AVL Tree

The above tree is a binary search tree and every node is satisfying balance factor
condition. So this tree is said to be an AVL tree.
Every AVL Tree is a binary search tree but every Binary Search Tree need not be
AVL tree.

AVL Tree Rotations

In AVL tree, after performing operations like insertion and deletion we need to check
the balance factor of every node in the tree. If every node satisfies the balance factor
condition then we conclude the operation otherwise we must make it balanced. Whenever
the tree becomes imbalanced due to any operation we use rotation operations to make
the tree balanced.

Rotation operations are used to make the tree balanced.

 Rotation is the process of moving nodes either to left or to right to make the
tree balanced.
There are four rotations and they are classified into two types.

Single Left Rotation (LL Rotation)

In LL Rotation, every node moves one position to left from the current position. To
understand LL Rotation, let us consider the following insertion operation in AVL Tree...

Single Right Rotation (RR Rotation)

In RR Rotation, every node moves one position to right from the current position. To
understand RR Rotation, let us consider the following insertion operation in AVL Tree...
Left Right Rotation (LR Rotation)
The LR Rotation is a sequence of single left rotation followed by a single right rotation. In
LR Rotation, at first, every node moves one position to the left and one position to right
from the current position. To understand LR Rotation, let us consider the following insertion
operation in AVL Tree...

Right Left Rotation (RL Rotation)

The RL Rotation is sequence of single right rotation followed by single left rotation. In RL
Rotation, at first every node moves one position to right and one position to left from the
current position. To understand RL Rotation, let us consider the following insertion
operation in AVL Tree...

Operations on an AVL Tree

The following operations are performed on AVL tree...

1. Creation
2. Search
3. Insertion
4. Deletion
5. Display

Example: Construct an AVL Tree by inserting numbers from 1 to 8.

 1. AVL Tree Insertion:

Insertion operation:
The data is inserted into the AVL Tree by following the Binary Search Tree property of insertion,
i.e. the left subtree must contain elements less than the root value and right subtree must
contain all the greater elements.

However, in AVL Trees, after the insertion of each element, the balance factor of the tree is
checked; if it does not exceed 1, the tree is left as it is. But if the balance factor exceeds 1, a
balancing algorithm is applied to readjust the tree such that balance factor becomes less than
or equal to 1 again.

Algorithm

The following steps are involved in performing the insertion operation of an AVL Tree −

Step 1 − Create a node

Step 2 − Check if the tree is empty

Step 3 − If the tree is empty, the new node created will become the

root node of the AVL Tree.

Step 4 − If the tree is not empty, we perform the Binary Search Tree insertion operation
and check the balancing factor of the node in the tree.

Step 5 − Suppose the balancing factor exceeds ±1, we apply suitable rotations on the said
node and resume the insertion from Step 4.

Example:

Construct anan
Construct AVL tree tree
AVL by inserting the following
by inserting theelements in the
following given order.in the given o
elements
63, 9, 19, 27, 18, 108, 99, 81
 The process of constructing an AVL tree from the given set of elements
is shown in the following figure.
 At each step, we must calculate the balance factor for every node,
if it is found to be more than 2 or less than -2, then we need a rotation to
rebalance the tree.
The type of rotation will be estimated by the location of the inserted element
with respect to the critical node.
 All the elements are inserted in order to maintain the order of binary search tree.
Deletion in AVL Tree
 Deleting a node from an AVL tree is similar to that in a binary search tree.
Deletion may disturb the balance factor of an AVL tree and therefore the tree
needs to be rebalanced in order to maintain the AVLness. For this purpose,
we need to perform rotations. The two types of rotations are L rotation and R
rotation. Here, we will discuss R rotations. L rotations are the mirror images
of them.
 If the node which is to be deleted is present in the left sub-tree of the critical
node, then L rotation needs to be applied else if, the node which is to be
deleted is present in the right sub-tree of the critical node, the R rotation will
be applied.
 Let us consider that, A is the critical node and B is the root node of its left
sub-tree. If node X, present in the right sub-tree of A, is to be deleted, then
there can be three different situations:
 R0 rotation (Node B has balance factor 0 )
 If the node B has 0 balance factor, and the balance factor of node A disturbed
upon deleting the node X, then the tree will be rebalanced by rotating tree
using R0 rotation.
The critical node A is moved to its right and the node B becomes the root of the tree
with T1 as its left sub-tree. The sub-trees T2 and T3 becomes the left and right sub-
tree of the node A. the process involved in R0 rotation is shown in the following
image.
 The critical node A is moved to its right and the node B becomes the root of
the tree with T1 as its left sub-tree. The sub-trees T2 and T3 becomes the left
and right sub-tree of the node A. the process involved in R0 rotation is shown
in the following image.
Example:
Delete the node 30 from the AVL tree shown in the following image.

Solution
In this case, the node B has balance factor 0, therefore the tree will be rotated by
using R0 rotation as shown in the following image. The node B(10) becomes the
root, while the node A is moved to its right. The right child of node B will now
become the left child of node A.
R1 Rotation (Node B has balance factor 1)
 R1 Rotation is to be performed if the balance factor of Node B is 1. In R1
rotation, the critical node A is moved to its right having sub-trees T2 and T3
as its left and right child respectively. T1 is to be placed as the left sub-tree
of the node B.
 The process involved in R1 rotation is shown in the following image.

Example
Delete Node 55 from the AVL tree shown in the following image.

Solution :
Deleting 55 from the AVL Tree disturbs the balance factor of the node 50 i.e. node
A which becomes the critical node. This is the condition of R1 rotation in which,
the node A will be moved to its right (shown in the image below). The right of B is
now become the left of A (i.e. 45).
 The process involved in the solution is shown in the following figure.
R-1 Rotation (Node B has balance factor -1)
 R-1 rotation is to be performed if the node B has balance factor -1. This case
is treated in the same way as LR rotation. In this case, the node C, which is
the right child of node B, becomes the root node of the tree with B and A as
its left and right children respectively.
 The sub-trees T1, T2 becomes the left and right sub-trees of B whereas, T3,
T4 become the left and right sub-trees of A.

The process involved in R-1 rotation is shown in the following image.

Example
 Delete the node 60 from the AVL tree shown in the following image.

Solution:
 In this case, node B has balance factor -1. Deleting the node 60, disturbs
the balance factor of the node 50 therefore, it needs to be R-1 rotated. The
node C i.e. 45 becomes the root of the tree with the node B(40) and A(50)
as its left and right child.
2. Search Operation in AVL Tree

In an AVL tree, the search operation is performed with O(log n) time complexity. The
search operation in the AVL tree is similar to the search operation in a Binary search tree.
We use the following steps to search an element in AVL tree...

• Step 1 - Read the search element from the user.

• Step 2 - Compare the search element with the value of root node in the tree.
• Step 3 - If both are matched, then display "Given node is found!!!" and terminate
the function
• Step 4 - If both are not matched, then check whether search element is smaller or
larger than that node value.
• Step 5 - If search element is smaller, then continue the search process in left
subtree.
• Step 6 - If search element is larger, then continue the search process in right
subtree.
• Step 7 - Repeat the same until we find the exact element or until the search element
is compared with the leaf node.
• Step 8 - If we reach to the node having the value equal to the search value, then
display "Element is found" and terminate the function.
• Step 9 - If we reach to the leaf node and if it is also not matched with the search
element, then display "Element is not found" and terminate the function.

Complexity

Algorithm Average case Worst case

Space o(n) o(n)

Search o(log n) o(log n)

Insert o(log n) o(log n)

Delete o(log n) o(log n)

Applications of AVL Trees
o Most in-memory sets and dictionaries are stored using AVL trees.
o Database applications, where insertions and deletions are less common but frequent
data lookups are necessary, also frequently employ AVL trees.
o In addition to database applications, it is employed in other applications that call for
better searching.
o A balanced binary search tree called an AVL tree uses rotation to keep things
balanced.
o It may be used in games with plotlines as well.
o It is mostly utilized in business sectors where it is necessary to keep records on the
employees that work there and their shift changes.

Advantages of AVL Trees

o The AVL tree's height never exceeds log N, where N is the total number of nodes in
the tree, since the height is always balanced.
o When compared to straightforward Binary Search trees, it provides a superior search
time complexity.
o AVL trees are capable of self-balancing.

Disadvantages of AVL Trees

o The aforementioned examples show that AVL trees can be challenging to implement.
o Additionally, for particular operations, AVL trees have significant constant factors.
o Red-black trees, as opposed to AVL trees, are used in the majority of STL
implementations of the ordered associative containers (sets, multisets, maps, and
multimaps). Red-black trees, unlike AVL trees, only need one restructure for an
insertion or removal.