11/3/2022

CIC – 209:
DATA STRUCTURES
Unit – II
AVL Trees and Heaps

AVL Trees
■ AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is named
AVL in the honour of its inventors.
■ AVL Tree can be defined as height balanced binary search tree in which each node is
associated with a balance factor which is calculated by subtracting the height of its
right sub-tree from that of its left sub-tree.
■ Tree is said to be balanced if balance factor of each node is in between -1 to 1,
otherwise, the tree will be unbalanced and need to be balanced.
■ An AVL tree is a binary search tree in which:
1. the heights of the right subtree and left subtree of the root differ by at most 1
2. the left subtree and the right subtree are themselves AVL trees
3. A node is said to be
■ left-high (/ or 1) - if the left subtree has greater height
■ right-high (\ or -1) - if the right subtree has greater height
■ Equal (- or 0) - if the heights of the LST and RST are the same
2

1
 11/3/2022

Examples of AVL Trees

AVL Rotations
■ The rotation in AVL tree shall be performed only in case if Balance Factor is
other than -1, 0, and 1.
■ There are basically four types of rotations which are as follows:
1. LL rotation: Inserted node is in the left subtree of left subtree of A
2. RR rotation: Inserted node is in the right subtree of right subtree of A
3. LR rotation: Inserted node is in the right subtree of left subtree of A
4. RL rotation: Inserted node is in the left subtree of right subtree of A
■ Where node A is the node whose balance Factor is other than -1, 0, 1.

■ The first two rotations LL and RR are single rotations and the next two
rotations LR and RL are double rotations.
■ For a tree to be unbalanced, minimum height must be at least 2.

2
 11/3/2022

LL Rotation (Right Rotation)

■ When BST becomes unbalanced, due to a node is inserted into the left subtree of
the left subtree of C, then we perform LL rotation, LL rotation is clockwise rotation,
which is applied on the edge below a node having balance factor 2.

■ In above example, node C has balance factor 2 because a node A is inserted in

the left subtree of C left subtree. Therefore, LL rotation is performed.

RR Rotation (Left Rotation)

■ When BST becomes unbalanced, due to a node is inserted into the right subtree of
the right subtree of A, then we perform RR rotation, RR rotation is an anticlockwise
rotation, which is applied on the edge below a node having balance factor -2

■ In above example, node A has balance factor -2 because a node C is inserted in the
right subtree of A right subtree. Therefore, RR rotation is performed.

3
 11/3/2022

LR Rotation (Left + Right Rotations)

■ Double rotations are
bit tougher than
single rotation.
■ LR rotation = RR
rotation + LL rotation,
i.e., first RR rotation is
performed on subtree
and then LL rotation
is performed on full
tree, by full tree we
mean the first node
from the path of
inserted node whose
balance factor is
other than -1, 0, or 1.

RL Rotation (Right + Left Rotations)

■ As already discussed,
that double rotations
are bit tougher than
single rotation.
■ R L rotation = LL
rotation + RR rotation,
i.e., first LL rotation is
performed on subtree
and then RR rotation
is performed on full
tree, by full tree we
mean the first node
from the path of
inserted node whose
balance factor is
other than -1, 0, or 1.

4
 11/3/2022

Insertions and Deletions in AVL Trees

■ While inserting a new node or deleting an existing node, the resulting tree may violate
the (stringent) AVL property. To reinstate the AVL property, the rotations are used.
■ Rotations in a BST
– Left rotation
– Right rotation

Example: T1, T2 and T3 are subtrees of the tree rooted with y (on the left side) or x (on
the right side)
y x
/ \ Right Rotation / \
x T3 -------> T1 y
/\ <------- /\
T1 T2 Left Rotation T2 T3
Keys in both of the above trees follow the following order
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.
9

Steps to follow for Insertion

Let the newly inserted node be w
1. Perform standard BST insert for w.
2. Starting from w, travel up and find the first unbalanced node. Let z be the first
unbalanced node, y be the child of z that comes on the path from w to z and x
be the grandchild of z that comes on the path from w to z.
3. Re-balance the tree by performing appropriate rotations on the subtree rooted
with z. There can be 4 possible cases that needs to be handled as x, y and z
can be arranged in 4 ways. Following are the possible 4 arrangements:
a) y is left child of z and x is left child of y (Left Left Case)
b) y is left child of z and x is right child of y (Left Right Case)
c) y is right child of z and x is right child of y (Right Right Case)
d) y is right child of z and x is left child of y (Right Left Case)

10

5
 11/3/2022

Steps to follow for Insertion (Contd…)

■ Following are the operations to be performed in above mentioned 4 cases.
■ In all of the cases, we only need to re-balance the subtree rooted with z and the
complete tree becomes balanced as the height of subtree
■ (After appropriate rotations) rooted with z becomes same as it was before
insertion.

a) Left Left Case

T1, T2, T3 and T4 are subtrees.
z y
/\ / \
y T4 Right Rotate (z) x z
/\ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/\
T1 T2
11

Steps to follow for Insertion (Contd…)

b) Left Right Case
z z x
/\ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/\ - - - - - - - - -> / \ - - - - - - - -> /\ /\
T1 x y T3 T1 T2 T3 T4
/\ /\
T2 T3 T1 T2

c) Right Right Case

z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> /\ /\
T2 x T1 T2 T3 T4
/\
T3 T4
12

6
 11/3/2022

Steps to follow for Insertion (Contd…)

d) Right Left Case
z z x
/\ /\ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> /\ /\
x T4 T2 y T1 T2 T3 T4
/\ / \
T2 T3 T3 T4

13

Insertions Examples

14

7
 11/3/2022

Insertions Example - 1

15

Insertions Example - 2

16

8
 11/3/2022

Insertions Example - 3

17

Insertions Example - 4

18

9
 11/3/2022

Implementation of Insertion Operation

■ The following implementation uses the recursive BST insert to insert a new node.
■ In the recursive BST insert, after insertion, we get pointers to all ancestors one by one
in a bottom-up manner. So, we don’t need parent pointer to travel up.
■ The recursive code itself travels up and visits all the ancestors of the newly inserted
node.
1. Perform the normal BST insertion.
2. The current node must be one of the ancestors of the newly inserted node.
Update the height of the current node.
3. Get the balance factor (left subtree height – right subtree height) of the current
node.
4. If balance factor is greater than 1, then the current node is unbalanced, and we
are either in Left Left case or left Right case. To check whether it is left left case
or not, compare the newly inserted key with the key in left subtree root.
5. If balance factor is less than -1, then the current node is unbalanced, and we are
either in Right Right case or Right-Left case. To check whether it is Right Right
case or not, compare the newly inserted key with the key in right subtree root.
19

Steps to follow for Deletion

Let w be the node to be deleted
1. Perform standard BST delete for w.
2. Starting from w, travel up and find the first unbalanced node. Let z be the first
unbalanced node, y be the larger height child of z, and x be the larger height
child of y. Note that the definitions of x and y are different from insertion here.
3. Re-balance the tree by performing appropriate rotations on the subtree rooted
with z. There can be 4 possible cases that needs to be handled as x, y and z
can be arranged in 4 ways. Following are the possible 4 arrangements:
a) y is left child of z and x is left child of y (Left Left Case)
b) y is left child of z and x is right child of y (Left Right Case)
c) y is right child of z and x is right child of y (Right Right Case)
d) y is right child of z and x is left child of y (Right Left Case)

20

10
 11/3/2022

Steps to follow for Deletion (Contd…)

■ a) Left Left Case
T1, T2, T3 and T4 are subtrees.
z y
/\ / \
y T4 Right Rotate (z) x z
/\ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/\
T1 T2

■ b) Left Right Case

z z x
/\ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/\ - - - - - - - - -> / \ - - - - - - - -> /\ /\
T1 x y T3 T1 T2 T3 T4
/\ /\
T2 T3 T1 T2
21

Steps to follow for Deletion (Contd…)

■ c) Right Right Case
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> /\ /\
T2 x T1 T2 T3 T4
/\
T3 T4

■ d) Right Left Case

z z x
/\ /\ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/\ - - - - - - - - -> / \ - - - - - - - -> /\ /\
x T4 T2 y T1 T2 T3 T4
/\ / \
T2 T3 T3 T4
■ Unlike insertion, in deletion, after we perform a rotation at z, we may have to perform a rotation at
ancestors of z. Thus, we must continue to trace the path until we reach the root.

22

11
 11/3/2022

Deletion Scenario - 1
R0 Rotation is to be performed 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 Right
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 right rotation is shown in the following image.

23

Deletion Example - 1
Problem: Delete the node 30 from the AVL tree shown in the following image.

24

12
 11/3/2022

Deletion Example - 1
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.

25

Deletion Scenario - 2
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.

26

13
 11/3/2022

Deletion Example - 2
Problem: Delete Node 55 from the AVL tree shown in the following image.

27

Deletion Example - 2
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 image.

28

14
 11/3/2022

Deletion Scenario - 3
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.

29

Deletion Example - 3
Problem: Delete the node 60 from the AVL tree shown in the following image.

30

15
 11/3/2022

Deletion Example - 3
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.

31

Implementation of Deletion Operation

■ The following implementation uses the recursive BST delete as basis.
■ In the recursive BST delete, after deletion, we get pointers to all ancestors one by one in
bottom-up manner. So, we don’t need parent pointer to travel up.
■ The recursive code itself travels up and visits all the ancestors of the deleted node.
1. Perform the normal BST deletion.
2. The current node must be one of the ancestors of the deleted node. Update the height of
the current node.
3. Get the balance factor (left subtree height – right subtree height) of the current node.
4. If balance factor is greater than 1, then the current node is unbalanced, and we are
either in Left Left case or Left Right case. To check whether it is Left Left case or Left
Right case, get the balance factor of left subtree. If balance factor of the left subtree is
greater than or equal to 0, then it is Left Left case, else Left Right case.
5. If balance factor is less than -1, then the current node is unbalanced, and we are either
in Right Right case or Right Left case. To check whether it is Right Right case or Right
Left case, get the balance factor of right subtree. If the balance factor of the right
subtree is smaller than or equal to 0, then it is Right Right case, else Right Left case.

32

16
 11/3/2022

Applications of AVL Trees

■ AVL trees are applied in the following situations:
– There are few insertion and deletion operations
– Short search time is needed
– Input data is sorted or nearly sorted
■ AVL tree structures can be used in situations which require fast searching. But, the large cost
of rebalancing may limit the usefulness.
■ Consider the following:
1. A classic problem in computer science is how to store information dynamically so as to
allow for quick look up. This searching problem arises often in dictionaries, telephone
directory, symbol tables for compilers and while storing business records etc. The records
are stored in a balanced binary tree, based on the keys (alphabetical or numerical) order.
The balanced nature of the tree limits its height to O (log n), where n is the number of
inserted records.
2. AVL trees are very fast on searches and replacements. But, have a moderately high cost
for addition and deletion. If application does a lot more searches and replacements than
it does addition and deletions, the balanced (AVL) binary tree is a good choice for a data
structure.
3. AVL tree also has applications in file systems.
33

Heap
■ Heap is a data structure, which permits one to insert elements into a set and
also to find the largest element efficiently.
■ Heaps (occasionally called as partially ordered trees) are a very popular data
structure for implementing priority queues.
■ A data structure, which provides these two operations, is called a priority
queue.
■ A heap is either a min-heap or a max-heap.
■ A min-heap supports the insert and deletemin operations while a max-heap
supports the insert and deletemax operations.
■ Heaps could be binary or d-ary.
■ Binary heaps are special forms of binary trees while d-ary heaps are a special
class of general trees.
■ Binary heaps were first introduced by Williams in 1964.

34

17
 11/3/2022

Max and Min Heap Data Structure

■ A max heap is an almost complete binary tree such that the value of each node
is greater than or equal to those in its children.
■ A min heap is an almost complete binary tree such that the value of each node
is less than or equal to those in its children.

35

Representation of Heap Tree

■ Since heap is a complete binary tree, a heap tree can be efficiently represented using
one dimensional array. This provides a very convenient way of figuring out where
children belong to.
– The root of the tree is in location 1.
– The left child of an element stored at location i can be found in location 2*i.
– The right child of an element stored at location i can be found in location 2*i+1.
– The parent of an element stored at location i can be found at location floor(i/2).
■ The elements of the array can be thought of
as lying in a tree structure. A heap tree
represented using a single array looks as
follows:

36

18
 11/3/2022

Operations on Heap Tree

■ The major operations required to be performed on a heap tree:
1. Insertion,
2. Deletion and
3. Merging.

37

Insertion into a Heap Tree

■ This operation is used to insert a node into an existing heap tree satisfying the
properties of heap tree.
■ Using repeated insertions of data, starting from an empty heap tree, one can
build up a heap tree.
■ Let us consider the heap (max) tree. The principle of insertion is that,
– First we have to adjoin the data in the complete binary tree.
– Next, we have to compare it with the data in its parent; if the value is
greater than that at parent then interchange the values. This will continue
between two nodes on path from the newly inserted node to the root node
till we get a parent whose value is greater than its child or we reached the
root.

38

19
 11/3/2022

Insertion into a Max Heap Tree - Algorithm

Max_heap_insert (a, n)
{
//inserts the value in a[n] into the heap which is stored at a[1] to a[n-1]
int i, n;
i = n;
item = a[n];
while ( (i > 1) and (a[ ⎣ i/2 ⎦ ] < item ) do
{
a[i] = a[ ⎣ i/2 ⎦ ] ; // move the parent down
i=⎣ i/2 ⎦ ;
}
a[i] = item ;
return true ;
}
39

Example
■ Form a heap using the above algorithm for the data: 40, 80, 35, 90, 45, 50, 70.

40

20
 11/3/2022

Example

41

Deletion of a node from Heap Tree

■ Any node can be deleted from a heap tree.
■ But from the application point of view, deleting the root node has some special
importance.
■ The principle of deletion is as follows:
– Read the root node into a temporary storage say, ITEM.
– Replace the root node by the last node in the heap tree. Then re-heap the
tree as stated below:
■ Let newly modified root node be the current node. Compare its value
with the value of its two child. Let X be the child whose value is the
largest. Interchange the value of X with the value of the current node.
■ Make X as the current node.
■ Continue re-heap, if the current node is not an empty node.

42

21
 11/3/2022

Deletion from Max Heap Tree - Algorithm

delmax (a, n, x) // delete the maximum from the heap a[n] and store it in x
{
if (n = 0) then
{
write (“heap is empty”);
return false;
}
x = a[1];
a[1] = a[n];
adjust (a, 1, n-1);
return true;
}

43

Deletion from Max Heap Tree – Algorithm

(Contd…)
adjust (a, i, n)
// The complete binary trees with roots a(2*i) and a(2*i + 1) are combined with a(i) to form a single
heap, 1 < i < n. No node has an address greater than n or less than 1. //
{
j = 2 *i ;
item = a[i] ;
while (j < n) do
{
if ((j < n) and (a (j) < a (j + 1)) then j = j + 1;
// compare left and right child and let j be the larger child
if (item > a (j)) then break;
// a position for item is found
else a[ ⎣ j / 2 ⎦ ] = a[j] // move the larger child up a level
j = 2 * j;
}
a [ ⎣ j / 2 ⎦ ] = item;
}

44

22
 11/3/2022

Example
■ Here the root node is 99. The last node is 26, it is in the level 3. So, 99 is replaced by
26 and this node with data 26 is removed from the tree. Next 26 at root node is
compared with its two child 45 and 63. As 63 is greater, they are interchanged. Now,
26 is compared with its children, namely, 57 and 42, as 57 is greater, so they are
interchanged. Now, 26 appears as the leave node, hence re-heap is completed.

45

Merging Two Heap Tree

■ Consider, two heap trees H1 and H2.
■ Merging the tree H2 with H1 means to include all the node from H2 to H1.
■ H2 may be min heap or max heap and the resultant tree will be min heap if H1
is min heap else it will be max heap.
■ Merging operation consists of two steps: Continue steps 1 and 2 while H2 is
not empty:
1. Delete the root node, say x, from H2. Re-heap H2.
2. Insert the node x into H1 satisfying the property of H1.

46

23
 11/3/2022

Example

47

Application of Heap Tree

■ They are two main applications of heap trees known are:
– Sorting (Heap sort) and
– Priority queue implementation.

48

24