AVL Trees

Height Balanced Trees

Tree is one of the most important data structure that is used for efficiently
performing operations like insertion, deletion and searching of values.
However, while working with a large volume of data, construction of a
well-balanced
balanced tree for sorting all d
data is
s not feasible. Thus only useful data
is stored as a tree, and the actual volume of data being used continually
changes through the insertion of new data and deletion of existing data.
You will find in some cases where the NULL link to a binary tree to special
links is called as threads and hence it is possible to perform traversals,
insertions, deletions without using either stack or recursion. In this
chapter, you will learn about the Height balance tree which is also known
as the AVL tree.

What is AVL Tree:

AVL tree is a binary search tree in which the difference of heights of left
and right subtrees of any node is less than or equal to one. The technique
of balancing the height of binary trees was developed by Adelson, Velsky,
Velsk
and Landis and henc
hencee given the short form as AVL tree or Balanced
Binary Tree.

What if the input to binary search tree comes in a sorted (ascending or

descending) manner? It will then look like this –

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 1

 It is observed that BST's worst
worst-case
case performance is closest to linear
search algorithms, that is Ο(n). In real
real-time
time data, we cannot predict data
pattern and their frequencies. So, a need arises to balance out the
existing BST.
Named after their inventor Adelson, Velsky and Landis, AVL trees are
height balancing binary searc
searchh tree. AVL tree checks the height of the left
and the right sub-trees
trees and assures that the difference is not more than
1.
This difference is called the Balance Factor.

Consider the following trees. Here we see that the first tree is balanced
and the next two trees are not balanced −

In the second tree, the left subtree of C has height 2 and the right subtree
has height 0, so the difference is 2. In the third tree, the right subtree
of A has height 2 and the left is missing, so it is 0, and the difference
diffe is 2
again. AVL tree permits difference (balance factor) to be only 1.
BalanceFactor = height(left
height(left-subtree) − height(right-subtree)

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 2

 If the difference in the height of left and right sub-trees is more than 1,
the tree is balanced using some rotation techniques.

AVL Rotations
To balance itself, an AVL tree may perform the following four kinds of
rotations −

 Left rotation
 Right rotation
 Left-Right rotation
 Right-Left rotation

The first two rotations are single rotations and the next two rotations are
double rotations. To have an unbalanced tree, we at least need a tree of
height 2. With this simple tree, let's understand them one by one.

Left Rotation
If a tree becomes unbalanced, when a node is inserted into the right
subtree of the right subtree, then we perform a single left rotation −

In our example, node A has become unbalanced as a node is inserted in

the right subtree of A's right subtree. We perform the left rotation by
making A the left-subtree of B.

Right Rotation
AVL tree may become unbalanced, if a node is inserted in the left subtree
of the left subtree. The tree then needs a right rotation.

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 3

 As depicted, the unbalanced node becomes the right child of its left child
by performing a right rotation.

Left-Right Rotation
Double rotations are slightly complex version of already explained
versions of rotations. To understand them better, we should take note of
each action performed while rotation. Let's first check how to perform
Left-Right rotation. A left-right rotation is a combination of left rotation
followed by right rotation.

State Action

A node has been inserted into the right subtree of the left
subtree. This makes C an unbalanced node. These scenarios
cause AVL tree to perform left-right rotation.

We first perform the left rotation on the left subtree of C.

This makes A, the left subtree of B.

Node C is still unbalanced, however now, it is because of

the left-subtree of the left-subtree.

We shall now right-rotate the tree, making B the new root

node of this subtree. C now becomes the right subtree of its
own left subtree.

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 4

 The tree is now balanced.

Right-Left Rotation

The second type of double rotation is Right-Left Rotation. It is a

combination of right rotation followed by left rotation.
State Action

A node has been inserted into the left subtree of the right
subtree. This makes A, an unbalanced node with balance
factor 2.

First, we perform the right rotation along C node,

making C the right subtree of its own left subtree B.
Now, B becomes the right subtree of A.

Node A is still unbalanced because of the right subtree of

its right subtree and requires a left rotation.

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 5

 A left rotation is performed by making B the new root node
of the subtree. A becomes the left subtree of its right
subtree B.

The tree is now balanced.

An AVL tree can be defined as follows:

Let T be a non-empty binary tree with TL and TR as its left and right subtrees.
The tree is height balanced if:

 TL and TR are height balanced

 hL - hR <= 1, where hL - hR are the heights of TL and TR

The Balance factor of a node in a binary tree can have value 1, -1, 0, depending
on whether the height of its left subtree is greater, less than or equal to the
height of the right subtree.

Advantages of AVL tree

Since AVL trees are height balance trees, operations like insertion and deletion
have low time complexity. Let us consider an example:

If you have the following tree having keys 1, 2, 3, 4, 5, 6, 7 and then the binary
search tree will be like the second figure:

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 6

To insert a node with a key Q in the binary tree, the algorithm requires seven
comparisons, but if you insert the same key in AVL tree, from the above 1st
figure, you can see that the algorithm will require three comparisons.

Representation of AVL Trees

Struct AVLNode
{
int data;
struct AVLNode *left, *right;
int balfactor;
};

Algorithm
lgorithm for Insertion
Step 1: First, insert a new element into the tree using BST's (Binary Search
Tree) insertion logic.
Step 2: After inserting the elements you have to check the Balance Factor of
each node.
Step 3: When the Balance Factor of every node will be found like 0 or 1 or -1
then the algorithm will proceed for the next operation.
Step 4: When the balance factor of any node comes other than the above
three values then the tree is said to be imbalanced. Then perform
the suitable Rotation to make it balanced and then the algorithm
will proceed for the next operation.

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 7

Ex 1) Construct AVL Tree for the following numbers
14, 8, 12, 46, 23, 5, 77, 88, 20

Insert (14)

Insert (8)

Insert (12)

Insert (46)

Insert (23)

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 8

Insert (5)

Insert (77)

Insert (88)

Insert (20)

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 9

Ex 2) Construct AVL Tree for the following numbers
1, 2, 3, 4, 8, 7, 6, 5, 11, 10, 12

Insert (1)

Insert (2)

Insert (3)

Insert (4)

Insert (8)

Insert (7)

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 10

Insert (6)

Insert (5)

Insert (11)

Insert (10)

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 11

Insert (12)

EX 3) Construct a binary search tree for data 8, 10, 3, 2, 1, 5, 4 ,6

Insert an element 7 into binary search tree using AVL rotation.

Insert 7

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 12

Algorithm for Deletion

We will try to understand this algorithm using an example but before

that let's go over the major steps of this algorithm. Note that this
algorithm is a bottom-upup algorithm and hence height restoration of
the tree proceeds from leaves to root.

This algorithm is basically a modification of the usual BST deletion

algorithm.

The
he steps of this algorithm are :

1. Use general BST deletion algorithm to delete given key from the
AVL tree.

2. After deletion, update the height of the current node of the AVL
tree.

3. Now check the 'balance' at the current node by getting the

difference of height of left sub
sub-tree
tree and height of right sub-tree.
sub

3a. If 'balance' > 1 then that means the height of the left sub-tree sub is
greater than the height of the right sub sub-tree.
tree. This indicates left-left
left or left-right
right case. To confirm if this is left left-left
left or left-right
left
case, we check the balance of left sub sub-tree of current
rent node. If it
greater than 0 then that confirms left left-left
left case, if it less than 0
then that confirms leftleft-right
right case. If it is equal to 0, then this we
can either consider this as a left left-left
left case or as a left-right
left case.
In this implementation, we cons consider this as left-left left case for
efficiency. For left--left
left case, we do a right rotation at the current
node. For the left--right
right case, we do a left rotation at left child of
current node followed by a right rotation at the current node
itself.

3b. If 'balance' < -11 then that means the height of the right sub-tree
sub
is greater than the height of the left sub sub-tree.
tree. This indicates
right-right
right or right
right-left
left case. In this case, if balance of right sub-
sub
tree of current node is less than 0 then this confirms right-right
right
case, if it is greater than 0 then this confirms right
right-left
left case. If it

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 13

 is equal to 0, then we can either consider this as a right-right
right
case or a right-left
left case. In this implementation, we will consider
this as a right-right
right case. In right
right-right case, we do a left
rotation at the current node. In rightright-left
left case, we do a right
rotation at the right child of current node followed by left
rotation at the current node itself.

Example walk-through: Let's delete key sequence [6,5,4] from the below AVL tree
and see how the height balance is maintained throughout.

Delete keys 6,5 and 4:

At this point, there is a height imbalance at node 3 with the left

left-left
left case. We do a
right rotation at node 3.

As you can confirm this tree satisfies height balance property for AVL tree.

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 14

 QUESTIONS FROM PREVIOUS UNIVERSITY EXAMINATIONS

1) What is an AVL tree?

Height Balanced Tree

Tree. AVL tree is a binary search tree in which the
difference of heights of left and right subtrees of any node is less than or
equal to one. The technique of balancing the height of binary trees was
developed by Adelson, Velsky, and Landis and hence given the short form
as AVL tree or Balanced Binary Tree.

2) Explain the right of left rotation of an AVL tree?

3) Explain the left of right rotation of an AVL tree?

4) What is the maximum number of nodes in an AVL tree given a height h.

5) What is an AVL search tree? How do we define the height of it? Explain
about the balance factor associated with a node of an AVL tree.

6) Construct AVL tree for the following numbers 14, 8, 12, 46, 23, 5, 77, 88, 20

7)) Insert the following sequence of elements into an AVL tree, starting with an
empty tree 10, 20, 15, 25, 30, 16, 18, 19

Insert(10) insert(20)

Insert(15)

Insert(25)

Insert(30)

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 15

Insert(16)

Insert(18)

Insert(19)

15) Deletee 30 in the AVL tree you got?

Delete(30)

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 16

8) Construct AVL tree for the following numbers 1, 2, 3, 4, 8, 7, 6, 5, 11, 10, 12

9) Define balanced binary search tree. Construct binary search tree for the data
8, 10, 3, 2, 1, 5, 4, 6, Insert an element 7 into binary search tree using AVL
rotation.

10) Write a routine for inserting an element into an AVL tree.

11)) Create an AVL tree using the following elements as a sequence set. Show
the balance factor in the resulting tree 13, 22, 6, 9, 32, 55, 79, 65, 70

12)) Insert 42, 43, 46 and 49 in the above constructed AVL tree and show a
balanced AVL tree

13)) Write the AVL tree deletion algorithm

algorithm?

14)) Write the AVL tree insertion algorithm?

15) Compare the worst case height of a red-black tree with n nodes and the
worst case height of an AVL tree with same number of nodes

16)) In an initially empty AVL tree insert the following Keys: DEC, JAN, APR,
MAR, JUL, AUG, OCT, FEB, NOV. Draw AVL tree after every insertion and
apply rotations where ever nece
necessary

17)) With suitable examples, explain different rotations associated with AVL tree
insertion.

18)) Derive an expression for maximum height of an AVL tree with n nodes.

If there are n nodes in AVL tree, minimum height of AVL tree is

floor(log2n).
If there are n nodes in AVL tree, maximum height can’t exceed 1.44*log 2n.

The worst case possible height of AVL tree with n nodes is 1.44*log n.
This can be verified using AVL tree having 7 nodes and maximum height.

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 17

 using 7 nodes, we can achieve maximum he
height
ight as 3. Following is the AVL
tree with 7 nodes and height 3.

MPESGI :: I B Tech CSE :: II Semester :: Data Structures :: AVL Trees :: Page 18