Algorithms and Data

Structures

AVL Trees
Dr. Yasir Faheem
Department of Computer Science
Islamabad campus

Lecture 13 With thanks to Dr. Salman Niazi

2

BINARY TREE

BINARY EXPRESSION HEAP DECISION HUFFMAN

SEARCH TREE TREE TREE
TREE

AVL RED-BLACK
TREE TREE
 Balanced Trees
3

 A binary search tree is balanced if its height is logarithmic in n (the number of items
in the tree).

Source: https://ppt-online.org/27175
 Balanced & Unbalanced Trees
4

 For any binary search tree worst time for insertion , deletion , searching is O(n).
 The difference between linear and logarithmic can be huge.
 For example , suppose n=1,000,000,000,000 (1 Billion). Then log2n is less than 29.9
 Worst cast case searching, insertion and deletion time in a BST can be reduced from O(n)
to O(log2n) by balancing it. We maintain an AVL tree.

Source: https://ppt-online.org/27175
AVL Trees
 An AVL tree is a binary search tree that either is empty or has the following two
properties :
1. The heights of the left and right subtrees differ by at most 1.
2. The left and right subtrees are AVL trees.
 AVL trees are named after two Russian mathematicians , Adel’son-Velskii and
Landis, who invented them.

https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
Balanced & Unbalanced Trees
 In a balanced BST (aka AVL Tree) the balance factor around any node x i.e.
difference of its left sub-tree and right sub-tree should be -1, 0 or 1.

 An AVL tree balances itself via rotation operations

Source: https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
 Types of Rotations
7

 To balance itself, an AVL tree may perform one of the following four rotation operations
➢ Left Rotation
➢ Right Rotation
➢ Double Left-Right Rotation
➢ Double Right-Left Rotation

To be Balanced via: Right Rotation Left-Right Rotation Left Rotation Right-Left Rotation
Source: https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
 Left Rotation
8

 Suppose that x is a reference to a node which is out of balance and y is a reference to x’s right child.
 Basically , a left rotation around x can be accomplished in just two steps:
1. x->right = y->left
2. y->left=x

y
 Left Rotation
9

1. x->right = y->left
2. y->left=x

x
80
90
y
60 90 80 120

85 120 60 85 100

100

Figure: A Left Rotation Around 80

 Left Rotation
10

1. x->right = y->left
2. y->left=x

50
50

30 80
30 90
20 40
60 90 20 40
80 120

85 120
60 85 100

100
Figure : A Left Rotation around 80 but 80 is not the root item
 Right Rotation
11

 Let x be a reference to a tree node , and let y be a reference to the tree node that is the
left child of x.
 Basically, a right rotation around x can be accomplished in just two steps:
1) x->left=y->right
2) y->right=x
 Right Rotation around 90
12

1) x->left=y->right
2) y->right=x

90 70

100 50 90
70

30 80 100
50 80

30
 Double Rotation Operations

 There are two other major types of rotations, which we call double rotations:

i. Left-Right Rotation: Left rotation around the left child of an item, followed by a right
rotation around the item itself.
ii. Right-Left Rotation: Right rotation around the right child of an item , followed by a left
rotation around the item itself.
Step 1of Right-Left Rotation: Right Rotation around y

Figure: Right Rotation around Right child of 6 i.e. around 15

Step 2 of Right-Left Rotation: Left Rotation around x

Figure : Left Rotation around unbalanced node 6

Insertion

 If a new node is inserted as a child of any non-leaf node then there will be no effect
on its balance , as the height of the tree does not increase.

0 0
20 20
-1 0
0 0
23 17 23
17
0 0
0 0 0 0
0
21
25 6 18 25
6 18

Before Addition After Addition

Figure : Addition of a new node (21) to a non-leaf of an AVL tree

Insertion ( Contd )

 If the new node is inserted as a child of leaf node of sub-tree( left or right ) of
shorter height then there will be no effect on the balance of an AVL tree.

1 0
20 20
0 1
0 0
17 23 17 23

0 0 0 0
0
6 18 6 18 21

Before Addition After addition

Figure : Addition of new node to a sub-tree of shorter height

 Insertion
 If the height of the left and right subtree is same then the insertion of a new node on any of the
leaf node does not disturb the balance of an AVL Tree.

0
20 20
0 1
0 0
23 17 23
17
0 0 0 0 0
0 0 -1
25 6 18 25
6 18 21 21
0
Before Addition After Addition 22

Figure : Addition of a new node to one of the subtrees of same height

Insertion
 If the new node is inserted as a child of the leaf node of taller subtree ( left or right ) then the AVL
tree becomes unbalanced and the tree no longer remains an AVL tree.

0 20
20 -2 1
1 29
-1 6
6 29
0 -1 0
-1
0 0 0 32
-1 5 12 25
5 12 32
25 0 1 0
0 0 0 10 15 27
10 15 27
0
Before Addition 13

After Addition
Insertion
 To rebalance and make it an AVL tree the nodes need to be properly adjusted.
 So after insertion of a new node the tree is traversed starting from the new node to the node
whose balance factor is disturbed.
 The nodes are adjusted in such a way that the resultant tree becomes a balanced tree.

Question
How to determine which of the four rotation operations is required to
rebalance the tree?
How to Determine Which Rotation Operations are
required?

h or

Case a: Left Rotation Around x Case b: Right-Left Rotation:

1) Right Rotation around y. 2)
left rotation around x
How to Determine Which Rotation Operations are
required?

Left-Right Rotation:
Right Rotation Case: 1) Left Rotation around y.
Right Rotate x 2) 2) Right Rotation around x
Left Rotation after Insertion
 The node containing the data 6 violates the condition of an AVL tree.
 In this case, x is the unbalanced node 6 and y is its right child 12.
 The resulting Unbalanced tree resembles case a. Hence a single left rotation is required
around x i.e. node 6

1
20
-2 1
6 29

0 -1 -1 0
5 12 25 32
0 1 0
10 15 27
0
13
After Addition Case a: Apply Single Left Rotation Around x
Left Rotation after Insertion
1 0

Single Left Rotation Steps: 1) x.right=y.left & 2) y.left=x

20 20
-2 1 0 1
6 29 12 29

0 -1 -1 0 0 1 -1 0
5 12 25 32 6 15 25 32
0 1 0 0 0 0
10 15 27 5 10 0 27
13
0
13

Before Rotation After Rotation

Right-Left Rotation after Insertion
 Now suppose instead of 13 we insert a node with value 11. This new node would get
inserted as the right child of the node containing a value 10.

0 1
20
20 -2 1
1
-1 6 29
6 29
0 1 -1 0
0 0 -1 0
5 12 25 32
5 12 25 32
-1 0 0
0 0 0 10
10 15 27
15 27
0
Before Addition 11
After Addition
 Right-Left Rotation after Inserting a Value
 After inserting 11, tree becomes unbalanced at node 6
 So, x is the unbalanced node 6 and y is its right child 12.
 This tree resembles the below given case b. Hence, a double rotation is required; a right
rotation around y followed by a left rotation around x. The final tree will be AVL tree.
0 1
20
20 -2 1
1
-1 6 29
6 29
0 1 -1 0
0 0 -1 0
5 12 25 32
5 12 25 32
-1 0 0
0 0 0 10
10 15 27
15 27
0
Before Addition 11
After Addition Right-Left Rotation: 1) Right Rotation
around y. 2) left rotation around x
Step 1 of Right-Left Rotation: Right Rotate y

 To rebalance the tree we are required to make initially a right-rotation of the tree
along the node containing a value 12.
 The tree is then rotated to left along the node 6.
1 1
20 20
-2 1 1
-2
6 29 6 29

0 1 0 0 0
-1 -2 -1
5 12 32 5 32
25 10 25
-1 0 0 0 0
10 15 27 12 27
0 0 0
11 11 15

First, apply right rotation around node 12 (right child of x) After First Rotation
 Step 2 of Right-Left Rotation: Left Rotate x

 After first right rotation around y, the resulting tree now resembles case a.
 As a second step of right-left rotation, now apply left rotation around unbalanced
node x i.e. 6.
1 0
1 20 20
20 1 1
1 -2 0
-2 6 29 10 29
6 29
0 -2 -1 0 1 0 -1 0
0 -2 -1 0 32 6 32
32 5 10 25 12 25
5 10 25
0 0 0 0 0 0
0 0 12 27 5 11 15 27
12 27
0 0
0 0 11 15 After Second Rotation, the final
11 15
After First Rotation tree will become AVL tree i.e.
After First Rotation balanced tree
How to Determine Which Rotation Operations are
required?

Left-Right Rotation:
Right Rotation Case: 1) Left Rotation around y.
Right Rotate x 2) 2) Right Rotation around x
AVL Trees

 AVL Trees
 Minimum height of an AVL tree is log2n.
 Maximum height of an AVL tree with n nodes is 1.44 log2n.
 Worst case search, insert, modify time is O(log2n)

AVL Tree Source: https://adtinfo.org/libavl.html/Answers-for-Chapter-5.html

Unbalanced Binary Search Tree
 Conclusion
 List ADT
 Sorted Array-list:
◼ Insertion and deletion are of order O(n), Binary Search algorithm is of order O(log2n)
◼ Memory wastage and memory overflow issues.
 Dynamic linked list:
◼ Efficiently utilizes memory as compared to array.
◼ Only linear search possible which is of order O(n), insertion and deletion are of order O(n)
 Binary Search Trees
◼ Insertion, deletion, searching are of order O(n)
 AVL Trees
 Worst case search, insert, modify time is O(log2n)
 Efficient utilization of memory as it is dynamically allocated & deallocated