DATA

STRUCTURES
UNIT -4
CLASS NOTES

BALANCED TREES

feedback1correctionsivibha@pesu.pes.edu Vibha Masti

 BALANCED TREES

search Tree
Binary
10

"
4 II

c to find element 2
/ ,

4 traversals needed

u worst case : och)

3
Best case :
oclogcn))

t
2

°
The tree above is BST but it is not efficient
a a
very
BST for
searching
added
If elements randomly then
searching BST
°

are a
,

is efficient than
more an
array
°
If elements are added in order
,
BSI are a slower

implementation of linear
arrays /
lists

of BST depends of and

Heightbe on the order insertion
°

can as bad as n -
I for n elements
Balanced BST -
AVL Trees

I
Here the
height of the tree is
always login) (empty
• → -

°
AVL tree : GM Adelson - Velskii , EM Landis (two Russian
mathematicians )

Balance factor of node is

a
always -1 O or -11
•

balance factor cleft subtree) subtree)

=
height height ( right
-

Not an AVL Tree

unbatanced ③

¢
(3 -
O)

10

°
Cet ) - C D)
-

4 ca -
th) 11
(C D
- -

(D)
⑦
I

/ (O -
C- I ))

C D)
3
(C -
D -
-

2
AVL Tree
O

O
1

2
11
O
O
l 10
3

ROTATION OF TREES

°
To convert a BST to an AVL Tree
Left rotation rotation (
single rotation) double rotations
right
°

, ,

Left Rotation

constructing AVL tree

•

an

into subtree
•
Performed when new
key inserted right of
right
child of a node whose balance factor was -

I before
insertion

•
Tree is
heavy on
right side

1) Insert 1

:
2) Insert 2

-
I

3) Insert 3
-
g c- unbalanced

1
rotate left

f -
I

Need to balance left rotation

• -

perform
into subtree of of
•
New
key inserted right right child a
node whose balance factor was -

I before insertion

•
Perform LCH as balance factor of I
changed from -
I to

-2
 4) Perform Left Rotation

LCD
0

o o

1 3

Rotation
Right

constructing AVL tree

•

an

Performed when inserted into left subtree

•
new
key of left
child of a node whose balance factor was + I before
insertion

Tree is
heavy left side
°

on

1) Insert 3

:
Insert
2) 2

3
O

2
3) Insert l

z ←
unbalanced

"
I
2
rotate
right
0

°
Need to balance

inserted into left subtree of left child of

•
New
key a
node whose balance factor was it before insertion

•
Perform 1213) as balance factor of 3
changed from 1 to 2

:
O
O

l 3
Left
Right Rotation

node inserted into of left child of

New
right subtree
°
a

node whose balance factor was + I before insertion

°
Left rotation on the left subtree of r (the one that

becomes unbalanced is r)

followed rotation of r
Then
by right
•

1) Tree before insertion

2) Insert 2

2
r -7
3

-
I
left

J
subtree l
of r

f
v
o

2
3) LCD

r →
3

"
I
2
rotate
right
0

4) RCD

:
O
O

l 3

°
We performed LRB)
 Rotation
Right Left

left of child of
New node inserted into subtree
right
•
a

node whose balance factor was -

I before insertion

Right rotation on the

right subtree of r (the one that

becomes unbalanced is r)

Then followed left rotation of r

by
•

1) Tree before insertion

2) Insert 2

-2

r -3 l

3
of
a
t
3) 1213)
-
2

r → I
rotate left

f -
I

4) Lcl )

:
O
O

l 3

•
we performed RLCD
 INSERTING A NODE INTO AN AVLTREE

Question I

convert list = I, 2,3 , 4, 5,6 to AVL

1) Insert I
0

2) Insert 2
-
l

3) Insert 3

-2

f -
i perform
left
2
rotation
0

3
 O

O o

I 3

4) Insert 4
-

O -

I 3

5) Insert 5
-2

2
nearest to
←
O newly -
inserted
-2
1 3
node : perform
43)

f -

437 4

5
 :
O o

l 4

O O

3 5

6) Insert 6

make -2
child \
new
left , root inserted into
/
Q
of new
root u right subtree

of child
O -
l right
I 4

o -
I 42)
42)
3 5
make
j child 0
right
of 4 's new
6
left child

4
note :
I
we
only
O
performed left
-

2 5 rotation as

elements were
O O O
read in
ascending
6 order
I 3
Question 2

6,5 , 4,3 , 2 I -
make AVL
,

:
I
I

5 RCG )

2
4

52 O

4 6

I I
144 )
3

:
I

O
o

3 G

O O

2 4
 2

i
I o

Rls)
3 6

I 0

2 4
T
O left node of
I
3 's new
right
child

3
note : we
only
I 0
performed right
2 rotation as
s
elements were

read
descending
° O in
o

order
I 4 6
Question 3

5
, 6,8 , 3,2 , 4,7 -
make AVL

2
-

5 45 )

f -
l

I 0

5 8

62 O

5 8

l T
Rts)
3

:
 2

subtree
I o
rightleft
-

3 of
g
child
O l

2 5
4213)
O

437 Eg Rcb)

) v

5 8

32 4
 -
I

O -
2

3 6 ← r

° left subtree
0 I

of
2 4 g right
child

o d RLCG )

RCS ) 46 )
g

66
2 4

78
 O

O
o

3
7

O o o O

2 4 6 8

Question 4

Is the
following tree an AVL ?

"
50

o / t o

30 70

o l l ,
ol l o
20 35 60 80
' '
is is to
40

yes
Question 5

Insert 28 into the above tree

2 left subtree of
left node

( / L o
30 70 12150)

-
l l l - i
o l l o

20 35 60 80
°
/ l
15
lo
25 I
-

40
'
④
O

30
-
l / t
o

20 50
l / L
o
l y
- I o

15 25 35 70

\ o
lo o / l o

28 40 Go 80
Question 6

Insert 7 into the AVL

'
13

/
/ \ -
I
10 15

/ L \ O
Of o

11 16

041 \
06

°
it is an AVL

•
insert 7

V z

I 13
right subtree
z / \ - , of left node
to 15

\ / \ 4240)
j
o
o
O 11 16

4/16-1
'
⑤
.
45 ) 13
z I
lol \
-

15 o
1
61 \ 116
'
l l O
'I

s >
°
/
4
 RC lo)
I

0 13 -
I
/ \
6 15
( / \ o L o
- 16
S 10
o
1 01 to
4 7 11

DELETING A NODE FROM AN AVL TREE

°
Perform standard BST deletion of a node w

from up and find

Starting travel first unbalanced
°
W
,
the
node Cz )

of for
Let be the
larger height child Cor
equal)
•

y z
any

Let child of for equal )

be the
larger height y carry
°
x

Rebalance tree
by performing appropriate rotations
°
the on

subtree rooted at 2

°
Rotation depends on one of four possible cases Wrt the
of y and
alignment x, z

and
1 Left left case
y left of left of Rt)
: z a
y :
-
.

Left left of and a

2 .
-

right case :
y z
right of
y : LRC 2)

Right right case y right of z and a of

3 :
right : U2 )
-

y
.

of and left of
4
Right left case y right : 2 I
y
: RLG)
. -
Question 7

Delete 55 from the AVL Tree

given
I

50

,
I \ ,
40 60
\ / \ o o /
30 45 55 → w to be deleted

←
Delete would from
as
you
a
regular BST
.

•
Travel upwards and find first unbalanced node

2 ← Z

Y ) ④
v 1)
V
L o

040
60,11
x

no
⑧ 45
0 /
10

•
is left of and a left of Rt)
y z
y :
 40
l l
30 50

' ' '

10 45 60

Question 8

Delete 9 from the tree

10

51 120 left ofz

y
/ h of
3 2×8
-
if 12 ,
a
right y
\ \ LRC 8)
⑨
y
ident:
as
,
10

51 420
3
/
Ig 15/125
'
11 is

6
O

10
51 Lab
-
1

! Yo if
°

last
of '
j '
is
Question 9

Delete 4 -
I

ill ,
3 8

/ lo l l ,
/ ,
11
2 4 7

ol il lo
il 6 10 12

°
/
9

-
l
Z
5

y 121 I -
,
left -
left :

3 8 1213)
t 11
x , I "
,

I 2 7
11

°
I o
l ,
/ to
, 10 12
6
01
9
 Z
-2 ←
5
right right
-

Y
° / y ←
-
I
45 )
2 8

115
"
°
l l id
I '
11
y

o
l ,
I to
10 12
6
°
I
9

8
°
/ \ i

5 11
' '
01 y
il lo
2 10 12
of
0,1 lj 6
ol
g
Question 10

Delete 80

100

2¥ 450
l l l y
,
50
,
② 120 180

o l y l l l
30g 110 130 200
K
/
125

1170 ) -

left left case

2
- Z
f
100
y right ofz
Y left of y
o / \ I f a

50 150
° / lo -
I / \ y
RL ( 100)
30 70 120 ← x 180

o l l l \ o

110 130 200

o l
125
 121150)
100

/ L
50 120

1 1 \
30 70 (
lol 150

l l
130 180

I i
200
125

4100)
O

120
I / \ o

100 150

o / Lo l l l -

,
50 110 130 180

0301 to 125
lo lo
200

Question 11

Delete 40 delete ,

¢ 50

' '
O
40 60
i

'
'

30 ¥ sit
←
 Z
50

Y 121 \ RC45)
45 60
" t l
,
l
J 30
55
o 1
10

50

l l
30 60

I ' 1
10 45 55