AVL Trees

S. Durga Devi ,CSE,CBIT

 AVL Trees
Introduction
- as the height of the tree increases, the average searching time is also increased.
- In order to minimize the average search time, the height of the binary search tree
should be balanced.
 Balance factor
bf=height o f the left sub tree- height of the right sub tree

 Definition
A binary search tree is said to be height balanced binary search tree if all its
nodes have a balance factor of 1, 0, or -1 that is for every node in the tree

|bf|=|height of left sub tree- height of right sub tree|<=1

S. Durga Devi
,CSE,CBIT
 AVL Trees
Introduction
- as the height of the tree increases, the average searching time is also increased.
- In order to minimize the average search time, the height of the binary search tree
should be balanced.
 Balance factor
bf=height o f the left sub tree- height of the right sub tree

 Definition
A binary search tree is said to be height balanced binary search tree if all its
nodes have a balance factor of 1, 0, or -1 that is for every node in the tree

|bf|=|height of left sub tree- height of right sub tree|<=1

S. Durga Devi ,CSE,CBIT

 Balanced and unbalanced BST
1 4
2
2 5
3
1 3
4
4 Is this “balanced”?
5
2 6 6

1 3 5 7 7
S. Durga Devi ,CSE,CBIT
 AVL trees….
 The objective of height balanced tree is to perform searching, insertion and deletion
operations efficiently.
 How unbalanced tree is converted into balanced tree?
 Following steps are to be followed
1. insert node into a binary search tree
insert the node into its proper position following the properties of the
binary search tree.
2. compute the balance factors
on the path starting from the root node to the node newly inserted,
compute the balance factor of each node.
3. Decide the pivot node
if the balance factor of any node is switched from 1 to 2 or -1 to-2 the
tree become unbalanced. That node is designated as pivot node.
4. Balance the unbalanced tree
use the AVL mechanism to balance the tree.

S. Durga Devi ,CSE,CBIT

 AVL rotations
• In order to balance the tree, one of the mechanism devised by two Russian
mathematicians, Adelson- Velskii and Lendis.

4 cases of rotations are possible

case 1: Left to Left insertion (LL Rotation)
case 2: Right to Right insertion (RR Rotation)
Case 3: Left-Right insertion (LR Rotation)
Case 4: Right-Left insertion(RL Rotation)

S. Durga Devi ,CSE,CBIT

 Case 1: LEFT-LEFT insertion
• Unbalanced occurred due to the insertion in the left sub tree of the left child
of the pivot node.
• Steps to follow
1. Right sub- tree(AR) of left child(A) of pivot node (P) becomes the left sub
tree of P.
2. P becomes the right child of A.
3. Left sub- tree(AL) of A remains the same.

P A

P
A
AL
PR
AR
AR PR
AL
S. Durga Devi ,CSE,CBIT
 1
LL Rotation example
8 Insert 2 2
1 8
0 2
6 10 0
0 0 0 0 6 10
4 1 0 0
7 9 11 4
7 0 9 11
0
3 5 0
1 3 5
0
0
2

S. Durga Devi ,CSE,CBIT

 LL Rotation example
8

Pivot 6 10
PR
A
4 7 9 11

3 5

2 AL AR

S. Durga Devi ,CSE,CBIT

 LL Rotation example
8 1

0 0
4 10
0 0 0
1 9 11
3 6
0
0
0 5 7
2

S. Durga Devi ,CSE,CBIT

 Case-2 RIGHT- RIGHT insertion
 Unbalance due to insertion in the right sub tree of right child of pivot node.
The following manipulations takes place
1. Left sub tree (BL) of right child(B) of pivot node (P) becomes the right sub- tree of
P.
2. P become the left child of B.
3. Right sub tree (BR) of B remains same.

B
P

P
B
PL
BL BR
PL
BL
BR
After insertion
S. Durga Devi ,CSE,CBIT
 RR insertion example
7 -1 Pivot
-2 Insert - 12
0
5 9 -1 -2
0 B
0
0 11 0 -1
4 6 8

PL 0
0 10 13

12 BR
BL

S. Durga Devi ,CSE,CBIT

 After rotations
-1
7

0 0 B
11
5
1
13
0 0 6 0
4 9
12
8
10 BR
0
0

S. Durga Devi ,CSE,CBIT

 Case-3 Left to Right insertion

• Unbalanced due to insertion in the right sub tree of left child of pivot node.
• Involves two rotations
Rotation-1
- left sub tree (BL) of the right child (B) of the left child of pivot node(P) becomes the right
sub tree of the left child(A).
- Left child (A) of the pivot node (P) becomes the left child of B.
Rotation- 2
- Right sub tree (BR) of right child(B) of the left child (A) of the pivot node (P) becomes
the left sub tree of P.
- P becomes the right child of B

S. Durga Devi ,CSE,CBIT

 LEFT RIGHT insertion

P B

2
A A P
PR

AL B
AL
BL BR PR

BR
BL

Balanced tree
Unbalanced tree

S. Durga Devi ,CSE,CBIT

 LEFT-RIGHT insertion Example
1 8 -2
8
0 -1 0
0
10 3 10
3

1 0 1 -1 0 0
0 0
2 5 9 11 2 5 9 11

0 0 0 0 -1
0
1 6 1 4 6
4
0
Height Balanced Tree
7

Un balanced due to insertion of 7

S. Durga Devi ,CSE,CBIT

 Pivot node

8 -2
A
-1 0

3 10 PR

1 -1 0 0
2 5 9 11
B
0 0 -1
1 4 6

AL 0

7
BL BR

S. Durga Devi ,CSE,CBIT

 5

3 8

2 4 10
6
0 BL
1
9 11
AL 7

PR
BR

S. Durga Devi ,CSE,CBIT

 Case-4 Right to left insertion
• Unbalanced occurred due to the insertion in the left sub tree of the right child of the pivot node.
• Two rotations takes place
rotation -1
 Right sub tree(BR) of the left child (B) of the right child(A) of the pivot node (P) becomes the left sub tree
of A.
 Right child (A) of the pivot node(P) becomes the right child of B.

P B

A After first rotation

2 A
PL
1
B AR

AR
BL
BR BR
S. Durga Devi ,CSE,CBIT
 Rotation-2
 Left sub-tree(BL)of the right child(B) of the right child(A) of the pivot node(P) becomes the right sub-tree of P.
 P becomes the left child of B

B
P
After two rotations A
A P
PL 2
1
B
AR AR
PL BL
BR
BL
BR

S. Durga Devi ,CSE,CBIT

 Right to left rotation example

7 -1

0 -1
5 9

0
12 1
8
0 0
4 6
0
0 11 13

S. Durga Devi ,CSE,CBIT

 Right to left rotation example
Insert-10
7 -1-2
P

0 -1
5 PL 9 -2
A
0
12 1
8
0 01
4 6
0
0 11 13

AR

10
BR
BL
S. Durga Devi ,CSE,CBIT
 Right to left rotation example
After AVL rotations
-1
7
0

5 0
11

0 0 0
4 6 9 -1
12
0 0
0
8 10
13
PL BL BR

AR

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree

14

11 17

7 53

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree

14

11 17

7 53

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree

14

7 17

4 11 53

13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now insert 12

14

7 17

4 11 53

13

12

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now insert 12

14

7 17

4 11 53

12

13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now the AVL tree is balanced.

14

7 17

4 12 53

11 13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now insert 8

14

7 17

4 12 53

11 13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now insert 8

14

7 17

4 11 53

8 12

13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now the AVL tree is balanced.

14

11 17

7 12 53

4 8 13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now remove 53

14

11 17

7 12 53

4 8 13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Now remove 53, unbalanced

14

11 17

7 12

4 8 13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Balanced! Remove 11

11

7 14

4 8 12 17

13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Remove 11, replace it with the largest in its left branch

7 14

4 12 17

13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Remove 8, unbalanced

4 14

12 17

13

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Remove 8, unbalanced

4 12

14

13 17

S. Durga Devi ,CSE,CBIT

 AVL Tree Example:
• Balanced!!

12

7 14

4 13 17

S. Durga Devi ,CSE,CBIT

 In Class Exercises
• Build an AVL tree with the following values:
15, 20, 24, 10, 13, 7, 30, 36, 25

S. Durga Devi ,CSE,CBIT

 15, 20, 24, 10, 13, 7, 30, 36, 25
20

15
15 24
20
10
24

13

20 20

13 24 15 24

10 15 13

10 S. Durga Devi ,CSE,CBIT

 15, 20, 24, 10, 13, 7, 30, 36, 25

20
13

13 24 10 20

10 15 7 15 24

7 30

13 36

10 20

7 15 30

24 36

S. Durga Devi ,CSE,CBIT

 15, 20, 24, 10, 13, 7, 30, 36, 25

13 13

10 20 10 20

7 15 30 7 15 24

24 36 30

25 13 25 36

10 24

7 20 30

15 25 36

S. Durga Devi ,CSE,CBIT

 Remove 24 and 20 from the AVL tree.

13 13

10 24 10 20

7 20 30 7 15 30

15 25 36 25 36

13 13

10 30 10 15

7 15 36 7 30

25 S. Durga Devi ,CSE,CBIT

25 36