SUBJECT CODE : 210252

As per Revised Syllabus of

Savitribai Phule Pune University

Choice Based Credit System (CBCS)
S.E. (Computer) Semester - IV

Data Structures and Algorithms

Anuradha A. Puntambekar
M.E. (Computer)
Formerly Assistant Professor in
P.E.S. Modern College of Engineering,
Pune

Minal P. Nerkar
M.E. (Computer Science)
Assistant Professor in
AISSMS Institute of Information Technology,
Pune

® ®
TECHNICAL
PUBLICATIONS
SINCE 1993 An Up-Thrust for Knowledge

(i)
Data Structures and Algorithms

Subject Code : 210252

S.E. (Computer Engineering) Semester - IV

ã Copyright with A. A. Puntambekar

All publishing rights (printed and ebook version) reserved with Technical Publications. No part of this book
should be reproduced in any form, Electronic, Mechanical, Photocopy or any information storage and
retrieval system without prior permission in writing, from Technical Publications, Pune.

Published by :
® ®
Amit Residency, Office No.1, 412, Shaniwar Peth,
TECHNICAL Pune - 411030, M.S. INDIA, Ph.: +91-020-24495496/97
PUBLICATIONS
SINCE 1993 An Up-Thrust for Knowledge Email : [email protected] Website : www.technicalpublications.org

Printer :
Yogiraj Printers & Binders
Sr.No. 10/1A,
Ghule Industrial Estate, Nanded Village Road,
Tal. - Haveli, Dist. - Pune - 411041.

ISBN 978-93-90450-35-0

SPPU 19
9 789390 450350

9789390450350 [1] (ii)

(iv)
(v)
 Position Key Record
4967000 0 4967000
1
2 8421002
Position 3

395
4957397 396 4618396
397 4957397
398
Position 399 1286399
in Hash 400
Table 401
402
403
404
405
406
407
408

990 0000990
991 0000991
992 1200992
993 0047993
994
995 9846995
996 4618996
997 4967997
998
999 0001999
 Step 1: Insert 33 0 25 Step 3: Insert 25
33 mod 5 = 3 1
Hash function 2 25 mod 5 = 0

Step 2: Insert 54 3 33 Bucket

54 mod 4 = 4 4 54
Hash Table

If we want to
insert 55 then
0 25
55 mod 5 = 0
1 th
But at 0 location
2 25 is already placed
3 33 and now 55 is
demanding the
4 54 same location.
Hence we say
''collision occurs''
 25% 5 = 0 0 25
1 31
31% 5 = 1
2 42
42% 5 = 2 3 63
63% 5 = 3 4 49

49% 5 = 4

33% 5 = 3

Slot1 Slot2
0 A A1 Bucket
1
2 C C2
3 D D1
4
Hash Table

n
T

n

(sb)
 Hash functions

Folding
Mid
Division Multiplication Extraction and
square
method method method universal
method
method

Hash Table
Hash Function
h(key) = record%table size 0

4 = 54%10 1

2 72

2 = 72%10 3

4 54

9 = 89%10 5

7 = 37%10 7 37

9 89
 h(k) = m { kA } 

Fractional part

 
h(k) = m 107  0.61803398987

66.12

0.12 Fractional part

h(k) = 50  0.12
=6
h(k) = 6

4 9 7 8 24

478 at 478 location in the hash

table of size 1000
the key can be stored.
 2
 (3111)

9 6 7 8 3 2 1

345678123
Key

345 678 123 345 678 123

Digit
reversed Digit
345 543 reversed
 678  678
 123  321
1 146  Index = 146 1 542  Index = 542
Discarded Discard

(a) Fold shift (b) Fold boundary

 0, 1, .... , m  1
x, y  U  x  y 
|H|
| h  H : h x  h y  |
m

1
m

nm

x 0 , x 1 , .... x r 

a  a 0 , a 1 , a 2 , .... a r 

r
h a  x  a i x i mod m
i0

a ha m r 1
  r 
h a (K)   a i K i  mod size
 
 i0 

  
 Collision handling
techniques

Open hashing Closed hashing

(chaining) (open addressing)

Chaining

Linear probing Quadratic Double

probing hashing
 0 39
Cluster
19%10 = 9 1 29

18%10 = 8 2 8

39%10 = 9 3

29%10 = 9 4

8%10 = 8 5

8 18

9 19
 0 90
1 11
2 22
3
4
5 55
6
7 37
8 17
9 49

0 90
1 11
2 22
22 3
32  4
5 55
6 87
7 37
8 17
9 49
H1( 37)
H1( 90)
H 1( 45)
H1( 22)
H1( 49)

0 90
1 17
2 22
3
4
5 45
6
7 37
8
9 49
 0
Transferring 1
the contents 2

9
Old table

22
New table
Collision solved by
linear probing
h 2 (X)
( Key  i 2 )

Index Keys Index Keys

0 0
1 4371 1 4371
2 2
3 3 1323
4 4
5 5
6 6
7 7
8 8
9 9

4371 mod 10 = 1 1323 mod 10 = 3

Index Keys 6173 mod 10 = 3

As collision occurs
0 we will apply
1 4371 quadratic probing.
2
2  H(key) = (H(key) + i ) % m
3 1323 Consider i = 0 2
4 6173  H (6173) = (3 + 0 ) % 10
5 = 3 collision
Hence consider i = 1 2
6
H (6173) = (3 +1 ) % 10
7 = (3 + 1) % 10
8 H (6173) = 4
9 As index 4 is an empty
slot, we will place
6173 at index 4.
 Index Keys
0
1 4371
2 4199 mod 10 = 9
3 1323
As this slot is empty
4 6173 we will place 4199 at index 9
5
6
7
8
9 4199

4344 mod 10 = 4
Index Keys But index 4 shows an
0 occupied slot. Hence
collision occurs. Therefore
1 4371
we will place 4344 using
2 quadratic probing.
2
3 1323  H(key) = (H(key) + i ) % m
4 6173 H(key) = 4, i = 0, 1, 2, ...
5 4344 m = 10 2
6  H (key) = (4 +0 ) % 10 = 4 collision
2
7 H (key) = (4 +1 ) % 10 = 5
8 The index 5 is an empty
9 4199 slot. Hence we will place
4344 at index 5.

Index Key 9679 mod 10 = 9 collision occurs.

0 9679 Hence we will place the element
1 4371 using quadratic probing.
2
2  H(key) = (H(key) + i ) % m
3 1323 H(key) = 9, i will be 0 or 1 or 2 ...
4 6173 m = 10 2
5 4344 H (key) = (9 +0 ) % 7 i=0
= 9 collision
6 2
7  H (key) = (9 + 1 ) % 10 = 0
8  Place 9679 at index 0
9 4199
Index Key 1989 mod 10 = 9 collision occurs.
0 9679 Hence we will place the element
1 4371 using quadratic probing.
2
2  H(key) = (H(key) + i ) % m.
3 1323 H(key) = 9, hence
2
4 6173  H (key) = (9 +0 ) % 10 i=0
5 4344 = 9 collision
6 2
 H (key) = (9 +1 ) % 10 i=1
7 = 0 collision
8 1989 2
 H (key) = (9 +2 ) % 10 i=2
9 4199 = 3 collison
2
 H (key) = (9 +3 ) % 10 i=3
=8
Insert 1989 at index 8
 h 2( X)
h2( 6173)



 Total number of comparisons 39
Number of keys 12


n Number of keys 12

b Total number of buckets 10

Total number of comparisons 39

Total number of buckets 10

Un
1 1 
  1 
2  (1 –  ) 

1 1 
  1  
2 (1 – 1.2) 
1 1 
 1 
2  ( – 0.2) 


1  1 

 1
2 (1 –  ) 2 
 
 1 1 
 1 
2  0. 04 





0 20

2 22

3 13

4 24

5 15

6 16

7 14 Place 14 here
because 14 % 10 = 4.
8 The index 4 contain
the element 24.
9 19 This is a proper record at its place.
Hence to place 14 we have to move down
10 in search of an empty slot.

11
 0 20

2 22

3 13

4 24

5 15

6 16

7 17 17 % 10 = 7. This position was occupied

by 14. But 14 is not the proper record
8 14 at this place. Hence replace 14 by 17.
Then place 14 at next empty slot.
9 19

10

11

0 20

2 22

3 13

4 24

5 15

6 16 26 % 10 = 6. But 16 is a proper record at this place.

7 17

8 14

9 19

10 26 Hence at next empty location 26 is placed.

11
 0 20

2 22

3 13

4 24 84 % 10 = 4. But 24 is occupying its own location

5 15

6 16

7 17

8 14

9 19

10 26

11 84 Then by moving linearly down we can place

84 at the empty location found.

0 20

1 96 As 96 % 10 = 6. But index 6 holds a record 16 which

is correct for that location. By moving down linearly
2 22 we get no empty slot. Hence we
roll back and get the empty slot at index 1.
3 13 Hence 96 will be replaced at index 1.

4 24

5 15

6 16

7 17

8 14

9 19

10 26

11 84
 0 20

2 22

3 13

4 24

5 15

6 16
Collision occurs at
7 14 index 4. Hence
probing 14 at
8 17
the next empty slot.
9 19
At index 7, the 14 is already placed.
10 26 Hence at next empty slot 17 is placed.

11
26 % 10 = 6. The collision occurs.
Hence 26 is placed at next empty slot.

0 20

1 96 96 % 10 = 6. But at location 6, the element 16 is

placed. Hence we go linearly down in search
2 22 of an empty slot. But since table gets full,
we may not get an empty slot. Therefore
3 13 roll back to search an empty slot.
At index 1, we can then place 96.
4 24

5 15

6 16

7 14

8 17

9 19

10 26

11 84 84 % 10 = 4. But index 4 contains key element

24. Hence by linear probing, at empty slot 11,
the element 84 is placed.



 


 Directory
0 1

(1) (1) Levels

001 111 Data to

010 be placed
in bucket

(0)

001
100
 0 1

(1) (1)

100 001
101
1


00 01 10 11

(1) (2) (2)

100 001 111

101

00 01 10 11

(1) (2)

100 001 111

1000 101
 00 01 10 11

(1) (2) (2) (2)

100 001 1010 111

1000 101

00 01 10 11

(1) (2) (2)

100 001 111

1000 101

00 01 10 11

(1) (1)
Note that the level was increased
100 001 when we insert 7. Now on deletion
of 7, the level should get decremented.
1000 101
 00 01 10 11

(1) (1)

001
100 101

1 2 3 4 5 6 NIL
head tail
node node
head tail
10 20 30 40 50 60 70 NULL

NULL
10 20 30 40 50 60 70

head tail

NULL
10 20 30 40 50 60 70
Skip List
 Key Value Array of pointer

Element *next



 
header tail
3
2
NULL
1
0 10 20 30 40 50 60 70





 NULL

10 20 30 40 50 60 70

Before insertion of 55

NULL

10 20 30 40 50 55 60 70

After insertion of 55
header tail

NULL

10 20 30 40 50 60

Before: The node 40 is to be deleted

header tail

NULL

10 20 30 50 60

After: The node 40 is deleted


 O(n 2 )

O(2n )
 (3  1  4) %7

 ( 3  3  4) % 7

 ( 3  8  4) %7
0 th


 (3  10  4) %7

2 nd
 T1 Root node

T2 T3 T4

T5 T6 T7 T8 T9

T10 T11 T12

10

30
20

60
40 70
50

90
80
 20 70
or
60 90
40
50

20
20 70
or or
40 60 90
40
50

10

30 Leaves are
20 marked in this
tree

60
40 70
50

90
80

Node with
Degree of this node 70 degree 1
20 is 3
90
60
40 Node
50 with degree 0
 10

This is the 30
node with
maximum degree 20
i.e. 3.Hence
degree of tree
is 3 60
40 70
50

90
80

Node at level 0
10

30 Nodes at level 1
(20,30)
20

60 Nodes at level 2
40 70
50 (40,50,60,70)

90 Nodes at level 3
80 (80,90)
 10

30
20

60 Internal nodes
40 70
50

90 External nodes
80

20 The nodes 40, 50 and

60 are siblings of
each other.
60
40
50
 Root node
10

Node with
two child
nodes 20 30

40 Node with one

70
child
50
60 80
Node with no
90 child or leaf
node

10

90 20
30
40
50

70
 10 10

20 20

30 30

40 40

50 50

Left skewed tree Right skewed tree

n n

nl nr

L = 0 then When L = 1, then

maximum nodes maximum nodes
are 1. are two i.e. nl and nr.

 
    
 Level 0

Height = 1

Level 1 Height = 2

Level 2

m

i0

 (2 h(TL ) 1  1)  ( 2 h(TR ) 1  1)  1
 (2 h(TL ) 1  2 h(TR ) 1 )  1

(2(2 max(h(TL ) 1, h(TR )+1 ) )  1

i = 0
n  e = 0+1
e = 1
i.e. Only one external node is present.

n1

n2 n3


 1

2 3

4 5 6 7

8 9 10 11 12 13 14 15
 Array Root = A = index 0.
A 0 A
1 B Left child of A i.e n = 0.
2 C  B will be at location.
B C 3 D Similarly right child of
4 E A is C
5 F nd
 C will be at 2 x 0 + 2 = 2 location
6 G th
D E F G I is at 8 location
7 H
8 I 2n + 2 = 8
2n = 6
H I n=3
rd
That means parent of I is at 3
location and i.e. D

10 0 10
1 20
20 2
3 30
30 4
5
40 6
7 40
 Left Right
child Data child

10 10

20 30

40 50 20 NULL 30 NULL

NULL 40 NULL NULL 50 NULL

 A

B C

D E

Array
0 A
A
1 B
2 C
B C 3
4
D E 5 D
6 E
 A

C D

E F

10

8
15 18
9

7 16
11 13 14 19 20

10

9 15

7 18
11

19
13

20
14

16
 A

B C D

H J K
E G
F

E C

F H D

G J

A Root

B C D

E F G H

I J K
 A

E C

D
F

G H

B C D
J
B F G H I

K L

E D

F H

C K I

G L J
 10

8 12

7 9 11 13

10

8 12

7 9 11 13

10

8 12

7 9 11 13
 50

17 72

12 23 54 76

9 14 19 67

Q, B, K, C, F, A P, E, D, H, R
 Preorder : B , Q, A, C, K, F, Preorder : P , D, E, R, H,

Inorder : Q, B , K, C, F, A Inorder : P , E, D, H, R,

G G

B P

Q K, C, F, A E, D, H,R

Preorder : A , C, K, F Preorder : D , E, R, H
Inorder : K, C, F, A Inorder : E , D , H, R

G G

B P B P

Q A Q A D
E, D, H, R

K, C, F K, C, F E H, R

Preorder : C , K, F, Preorder : R , H,
Inorder : K, C , F, Inorder : H, R

G G

B P B P

Q A D Q A D

C E H, R C E R

K F K F
H

Final binary tree

 10 Root / current

8 11

7 9

10
 

current 8 11
10

7 9 Stack

 
10

8 11
8
10
current Stack
7 9

10

 

8 11 7
8
10
7 9 Stack

current = NULL
 


10

8 11 7
8 current = NULL
10
7 9
Stack Output

NULL current




10

8 11 7 8
current = NULL
10
7 9
current Stack Output
 




10

8 11 7 8 9

10 current = NULL
7 9

NULL current Stack Output

10

8 11 7 8 9 10 11

current = NULL
NULL
7 9
current Output Stack
  10 current  10

 8 current 11  10 8
7
8 8
10 10 10
 7 current 9  10 8 7
  

Output Stack
 10 8 7 9
9
10
Stack Output

10 8 7 9 11
11
Stack Output
 10

The DFS sequence

8 12 is 10, 8, 12, 11, 13

11 13
 10

4 12

3 8 11

6 9

5 7

10
 4
12

12

3
8
12

8
12

12

6
9
12

9
12

5
7
9
12

7
9
12
 9
12

12
 10
Level 0
visit 10,
visit 8, 12
8 12
Level 1 visit 11, 13
 The BFS
11 13 sequence will be
Level 2 10, 8, 12, 11, 13
 10

4 12

3 8 11

6 9

5 7

10
Queue

4 12
Queue

12 3 8


 3 8 11

11 6 9

9 5 7


 root/New New data = 10;
New left = NULL;
NULL 10 NULL
New right = NULL;
root = New;

root New
NULL 10 NULL NULL 8 NULL

root
10 NULL root left = New;

New
NULL 8 NULL

root New
NULL 10 NULL NULL 12 NULL

root
10 root right = New;

New New
NULL 8 NULL NULL 12 NULL

root/temp
10 While(temp left ! = NULL)
temp = temp left

NULL 8 NULL NULL 12 NULL

 root
10 temp left = New;

temp
8 NULL NULL 12 NULL

New
NULL 7 NULL
 E 2
G 2
B 3
4
H 3
C 4
E:2 G:2
F 4
A 10
D 15

B 3
H 3
C 4
F 4 4 6
EG 4
A 10 E:2 G:2 B:3 H:3
D 15
C 4
F 4
EG 4
4 6 8
BH 6
A 10
E:2 G:2 B:3 H:3 C:4 F:4
D 15

EG 4 10
BH 6
CF 8 4 6
A 10
D 15 E:2 G:2 B:3 H:3

18
CF 8
A 10 8 A : 10
EGBH 10
D 15 C:4 F:4

25

10 D : 15
EGBH 10
D 15
4 6
CFA 18

E:2 G:2 B:3 H:3

 43

18
25
8 A : 10
10 D : 15
CFA 18
EGBHD 25 C:4 F:4
4 6

E:2 G:2 B:3 H:3

43 Data Weight Code

0 1 A 10 01
18 25 B 3 1010
0 1 0 1
C 4 000
8 A :10 10 D : 15
0 1 D 15 11
0 1
4 6 E 2 1000
C:4 F:4
0 1 0 1
F 4 001
E:2 G:2 B:3 H:3 G 2 1001
H 3 1011

c
c




H:2 A:3

10

C:5 5

H:2 A:3
 15

I:7 E:8

25

10 15

C:5 5 I:7 E:8

H:2 A:3

This is Huffman's tree

25
0 1

10 15
0 1 1
0
C:5 5 I:7 E:8
0 1

H:2 A:3
 10

7 15

5 9 12 18
Attaching left node to the
current node.

If the root node has already

some left child, then move on
to left subtree
 10

6 20

8 15 22

9 21 24

10

6 20

8 15 22

9 21 24

Node is attached
23
10 10 10 10 10

08 08 15 08 15 08 15

12 12

13

10 10 10

08 15 08 15 08 15

07 12 07 09 12 07 09 12 17

13 13 13

10
10
08 15
08 15
07 09 12 17
07 09 12 17
13 20
13 20
18

10 10

08 15 08 15

07 09 12 17 07 09 12 17

04 13 20 04 13 20

18 05 18
 10

8 20

6 7 15 22

10

8 20

7 15 22

10

8 20

6 15 22

18

16
 10

5 12

7
4

6 9

10

5 12

8
4

6 9

temp is node which is to be deleted.

Parent is a node which keeps track of
parent node. temp and temp_succ is for
keeping track of successor of temp node.
Copying the successor
node's data to temp node.
Thus contents of temp
node gets deleted.
 10

5 12

8
4

6 9

 Marking the parent node

 If current node is greater than key
 Search for the left subtree
 


 


10

8 12

7 9 11 13
13

7
8 8
10 10 10

Stack Stack Stack

 8
10

Stack

8 8

NULL 7 NULL NULL 9 NULL NULL 9 NULL NULL 8 NULL

10

stack

11
12 12
10 10

Stack Stack

12 12

10 NULL 11 NULL NULL 13 NULL NULL 13 NULL NULL 11 NULL

stack
 10 10

NULL 8 NULL NULL 12 NULL NULL 12 NULL NULL 8 NULL

Stack

10 50

20 60 20 80

30 40 50 10 30 60 100

70 90
70 80 90 100

Tree Binary search tree

 –999 Head node

10 Child
Thread
8 15

7 9 12 18
 lth Left Data Right rth
Dummy
0 NULL –999 NULL 0
node

New
0 NULL 10 NULL 0 or
root

dummy
1 –999 NULL 0

root
1 10 0

 



 dummy
1 –999 NULL 0

1 10 0 root

New
0 8 0

1 –999 NULL 0

1 10 0

1 8 0

0 6 0
 1 –999 NULL 0

Root
1 10 0

New
1 8 0 1 12 0

New  right = root  right

0 6 0 New  left = root
root  rth = 1
root  right = New

1 –999 NULL 0

1 10 1

1 8 1 1 12 1

0 6 0 0 9 0 0 11 0 0 14 0
 12 th

1 –999 NULL 0

1 10 1

1 8 1 1 12 1

0 6 0 0 9 0 0 11 0 0 13 0

–999 NULL 0

1 10 1

1 8 1 1 13 0

0 6 0 0 9 0 0 11 0

2 h– 1 2 h– 1 – 1
2 h 1 – 1 2 h 1
 10
0 10 root
1 8 root's left
8 11 2 11 root's right
3 7 8's left
4 9 8's right
7 9

Consider following tree The inorder traversal order is

left, parent, root
4 1, 2, 3, 4, 5

2 IV 5
III

I II
1 3

2 3

4 5
 10

8 12

7 5 9 11 13 14 20

10

Here 8 and 11 are

leaf nodes.
8 11

NULL NULL NULL NULL

2 level – 1
 TM

TECHNICAL PUBLICATIONS - An up thrust for knowledge

 V1
E1 E3
E2
V4
V2
V3 G = { V1, V2, V3, V4, V5, V6 },
E6 { E1, E2, E3, E4, E5, E6, E7 }
E4 E5

V6
V5
E7
 V1
E1 E2

V2 V3

E3 E4
V4

V1
E1

V2 V3

V4

V1

V2 V4

V3

n ( n – 1)
2

n ( n – 1) 4 ( 3)

2 2
 V1 e1 V2
n ( n – 1) e5
2 e4 e2
e6

V4 e3 V3

V1

k ( k – 1)
2

n ( n – 1) n ( n – 1)  2n
2 2

n 2 – n  2n n2 n
2 2
n ( n  1)
2

( k – 1) k k ( k – 1)
2 2

n ( n – 1) n ( n  1)
2 2

n ( n – 1)
2
 V1 V1

V2 V3 V2

Graph G Graph G'

Vi Vj Vi Vj

V1

V1 - V2 V2 - V1 V 3 - V1 V4 - V 3 - V1

V1 - V 3 V2 - V1 - V 3 V 3 - V1 - V2 V4 - V2 V2 V3

V1 - V4 V2 - V4 V 3 - V4 V4 - V 3

V4
 0
10 20

30
1 4

40 50 60

2 3
70

2
1

5
4

2
1

5
4
 6

1 2

4 5 7 8

4 3
9

V1

V4 V2

V3

V1
 1 2 3 4 5

V1 1 0 1 1 0 0

2 1 0 0 1 0
V3
V2 3 1 0 0 1 1

4 0 1 1 0 1
V5
V4 5 0 0 1 1 0

V1 1 2 3 4 5
10 20
1 0 10 0 0 20
30 V5
V2 2 10 0 60 50 30

3 0 60 0 70 0
50
60 40
4 0 50 70 0 40

5 20 30 0 40 0
V3 V4
70

Weighted graph Adjacency matrix

b e

d
c
 head node

a b e NULL

b a c NULL

c b d NULL

d c e NULL

e a d NULL

Head [5]

0 a b e Null

1 b a c Null
2 c b d Null
 3 d c e Null
4 e a d Null
 1 2 3

Nodes
VERTEX
1 N1 1 2 N2 N3 edge (1,2)
2 edge (1,4)
N2 1 4 0 N4
3
N3 2 3 N4 N5 edge (2,3)
4
N4 2 4 0 N5 edge (2,4)

N5 3 4 0 0 edge (3,4)
 Vertex 1 : N1  N2 
Vertex 2 : N2  N3  N4 
 Adjacency Multilists
Vertex 3 : N3  N5 
Vertex 4 : N2  N4  N5 

0 2 NULL

1 0 NULL

1 2

2 3 NULL

3
3 0 1 NULL
NULL

E1 1 4
E3 E5

0 3

E4 E6
E2 2 5
0 2 X

1 0 X

2 3 X
3 1 4 5 X

4 X
5 X
 4 th

0 1 NULL

1 3 NULL

2 0 NULL

3 2 NULL

4 3 NULL

5 3 NULL
 Vi Vj


 head [MAX] where MAX = 10

0 0 1 2 NULL
0
1 1 0 3 NULL

2 2 0 3 NULL
1 2
3 3 1 2 NULL

4 0 NULL

5 0 NULL
3
6 0 NULL

7 0 NULL

8 0 NULL

9










B C D

E F
A B C D NULL

B A C E NULL

C A B D E F NULL

D A C F E NULL

E B C D F NULL

F D C E NULL
NULL
 1

2 3

visit Queue
0 0 1 2 3 4 Inserted vertex 1 in queue
1 1 –1 1 and marked the index 1 of
2 visited array by 1.
3 Front Rear
4

0 1 2 3 4 Delete '1' and print it

1 so '1' gets printed.

Front
rear
 visit
0 0 1 2 3 4
1 1 1 2 3 Increment front by 1 delete '2' from
2 1 Queue and print it so '2' gets printed.
3 1 Front Rear
4

visit
0 0 1 2 3 4
1 1 1 2 3 4
2 1
3 1 Front Rear
4 1

0 1 2 3 4
1 2 3 4 So ‘3’gets printed

Front Rear

visit
0 0 1 2 3 4
1 1 1 2 3 4 So ‘4’ gets printed since front = rear
2 1 stop the procedure.
3 1 Front
4 1 rear
O V  E 

3
 1

2 3

Visited
0 0
1 1
2 0
3 0
4 0

Visited Stack
0 0 2
1 1
2 1
3 0
4 0

Visited Stack
0 0 4
1 1
2 1
3 0
4 1

Visited Stack
0 3 Top
After exiting the loop 3 will be
1 1 popped print ‘3’
2 1
3 1
4 1


 


 0

1 2


 




 











 




 1

2 3 4

b c

a g d

e f
a b e g NULL

b a c g NULL

c b d g NULL

d c f g NULL

e a f g NULL

f e d g NULL

g a b c d e f NULL
NULL
b

f
 e

b c

a g d

e f
a b e g NULL

b a c g NULL

c b d g NULL

d c f g NULL

e a f g NULL

f e d g NULL

g a b c d e f NULL
NULL

a
a

a b e g

a b e g c

a b e g c f
a b e g c f d

a b e g c f d

a b e g c f d

a b e g c f d
1 2 3

8
7
9

6 5 4

2 3 BFS order : 1, 2, 3, 4

Graph





s  select (D) // section of solution from D

Check if the if (Feasible (solution, s)) then
selected solution solution  Union (solution, s);
is feasible or
not.
Make a feasible
} choices and select
return solution optimum solution.
 1 1 1

2 4 2 4 2 4

3 3 3

Graph G Spanning trees

 2
V1 V2

4 1 3 10

2 7
V3 V4 V5

8 4
5 6
V6 1 V7
 V1
1 Path length = 1

V4

V1 2 V2
1 Path length = 3

V4

V1 2 V2
1 Path length = 5

V3 2 V4

V1 2 V2

1 Path length = 9

V3 2 V4
4

V7

V1 2 V2

1 Path length = 10

V3 2 V4
4

V6 1 V7

V1 2 V2

1 Path length = 16

2 V5
V3 V4
4 6

V6 1 V7



b 5 c
10 2
7
9 a 5 d 5
6 6 4

f 10 e
Step 1 : Step 2 : Step 3 :
5 c
c c b

2 2 2

d d d

4 4

e e
weight = 2 weight = 6 weight = 11

Step 4 Step 5

5 c 5 c
b b

2 2
a

d d
6 6 6
4 4
f f
e e
weight = 16 weight = 23 - is minimum
spanning tree
 5 c
b

2
a

d
6 6
4
f
e
Minimum spanning tree with weight 23

60
1 3
20
61
41 30 5

90
40
2 4
70

3
20

3
20

30 5

4
 60
1 3
20

30 5

60
1 3
20

41 30 5

2 4

b 20 c 30 d

30 29
7
42 65
a e
99 13
85
40 38

h g f
17 5
 c d
b

a e

h g 5 f

c d
b

a e

h g 5 f

c d
b

a e
13

h g 5 f

20 c d
b

a e
13

h g 5 f
 20 c d
b

30
7

a e
13

h g 5 f

20 c d
b

30
7

a e
13

h 17 g 5 f

20 c d
b

30 29
7

a e
13

h 17 g 5 f








 



tree [ ] [ ] is an array in
which the spanning tree
edges are stored.


Computing total cost

 of all the minimum
distances.


For each node of
i, the minimum distance
edges are collected in
array tree [ ] [ ] .
The spanning tree
is printed here.
 3
1 2
1 5 3

6
6 3 5
5
4 6
4 2 6

3
1 1 2
1 1

3 3

3
1 2
3 1 3
1 2
1 3
3 5

3 5 4

3
1 2
1 3

3 5

4 2 6
 3
B D
4 8
1 7
A C E
8 3
 3
B D
4 8
 1 7
 A C E
8 3

3
B D
 4 8
1 7
A C E
8 3

3
B D
4 8
1 7
A C E
8 3




Start from each source node







 Finding minimum
distance from
selected source
node.That is :
source-j represents
 min. dist. edge







v1 is next selected destination
vertex with shortest distance.
All such vertices are
accumulated in array
path[ ]
 2
B C
10

A 1 4 7 9
8
3
E D
2


 




 a b

d c

Vi Vj Vi Vj
i th j th

a b c d
a b As no edge from
a 0 1 0 0 b to d, value
is 0.
b 0 0 1 0
c 0 0 0 1 Edge from
d c c to d
d 1 0 0 0

Digraph Adjacency matrix

 Path
b-c-d

d-a-b-c-d

Graph Transitive closure

R(0) , ... , R(k  1) , ... , R(k) , ... R(n)

R(0) R(0)

R(0) R(0)

R(1)
R(1) R(0)
 R(k)
R(k) R(k  1)
R(n) R(n)
R(n)

R(0)

a b c d
Here we have
a b a 0 1 1 0 considered only
direct edges from
(0) b 0 0 1 0 each source
R = vertex. If the
c 0 0 0 1
direct is edge
d c d 1 0 0 0 is present make
1 in matrix.
The boxes at row
(1)
and column are for getting R
a b c d
Here intermediate
a b a 0 1 1 0 vertex is 'a' and
using 'a' as
(1) b 0 0 1 0 intermediate vertex
R = we have to find
c 0 0 0 1 destination vertices
d c d 1 1 0 0 with path length of
2. For instance from d
to b a path exists
with a as intermediate
vertex.

a b c d
a b
a 0 1 1 0
(2)
R = b 0 0 1 1

c c 0 0 0 1
d
d 1 1 1 1
 R(1)

a b c d
a b
a 0 1 1 1
(3)
R = b 0 0 1 1

c c 0 0 0 1
d
d 1 1 1 1

a b c d
a b
a 1 1 1 1
(4)
R = b 1 1 1 1

c c 1 1 1 1
d
d 1 1 1 1

R(k) R(k  1)
(k)
rij  i th j th R(k)
(k)
vi vj rij

vi 
vi vj
 k th vi
vj
(k  1)
rij  1

k th vk

vi vk
(k  1)
ri k  1

vk vj
(k  1)
rkj  1

R(k) Rk 1

(k) (k  1) (k  1) (k  1)
rij = rij or rik and rkj

(k)
R(k) rij

R(k)

1 2 3 4
1 2
1 0 1 1 0
(0)
R = 2 0 0 1 1
3 0 0 0 1
4 3
4 1 0 0 0

R(1)

1 (k 1) (k 1) (k 1)

r11 rij rik rkj
0
r11 0
r11 0
r11

1
r11

1 (k 1) (k 1) (k 1)

r12 rij rik rkj
0
r12 0
r11 0
r12
 1
r12

R(0) R(1)
1 k 1 k 1 k 1
r42 rij rik rkj

1 2 3 4
1 0 1 1 0
(0)
R = 2 0 0 1 1
3 0 0 0 1
4 1 0 0 0

0
r42 0
r41 0
r12

 1
r42

R(1)

1 2 3 4
1 0 1 1 0

2 0 0 1 0
3 0 0 0 1
4 1 1 0 0

R(1) , R(2) , R(3) R(4)



 R(k 1) 


(n 3 )
R(k)

(n 3 )
0 1 0 0
0 0 1 0
 
0 0 0 1
 
0 0 0 0

0 1 0 0
0 0 1 0
 
0 0 0 1
 
0 0 0 0

rijk rij(k  1) (k  1)
rik (k  1)
rkj

1
r11 0
r11 0
r11 0
r11
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj

1
r12 0 or r 0 and r 0
r12 11 12

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r13 0 or r 0 and r 0
r13 11 13

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r14 0 or r 0 and r 0
r14 11 14

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r21 0 or r 0 and r 0
r21 21 11

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r22 0 or r 0 and r 0
r22 21 12
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj

1
r23 0 or r 0 and r 0
r23 21 13

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r24 0 or r 0 and r 0
r24 21 14

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r 31 0 or r 0 and r 0
r 31 31 11

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r 32 0 or r 0 and r 0
r 32 31 12

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r 33 0 or r 0 and r 0
r 33 31 13
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj

1
r 34 0 or r 0 and r 0
r 34 31 14

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r41 0 or r 0 and r 0
r41 41 11

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r42 0 or r 0 and r 0
r42 41 12

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r43 0 or r 0 and r 0
r43 41 13

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

1
r44 0 or r 0 and r 0
r44 41 14
rijk rij(k  1) (k  1)
rik (k  1)
rkj

2
r11 1 or r 1 and r 1
r11 12 21

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r12 1 or r 1 and r 1
r12 12 22

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r13 1 or r 1 and r 1
r13 12 23
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj

2
r14 1 or r 1 and r 1
r14 12 24

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r21 1 or r 1 and r 1
r21 22 21

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r22 1 or r 1 and r 1
r22 22 22

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r23 1 or r 1 and r 1
r23 22 23

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r24 1 or r 1 and r 1
r24 22 24
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj

2
r 31 1 or r 1 and r 1
r 31 32 21

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r 32 1 or r 1 and r 1
r 32 32 22

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r 33 1 or r 1 and r 1
r 33 32 23

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r 34 1 or r 1 and r 1
r 34 32 24
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj

2
r41 1 or r 1 and r 1
r41 42 21

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r42 1 or r 1 and r 1
r42 42 22

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r43 1 or r 1 and r 1
r43 42 23

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

2
r44 1 or r 1 and r 1
r44 42 24
rijk rij(k  1) (k  1)
rik (k  1)
rkj
3
r11 2 or r 2 and r 2
r11 13 31

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r12 2 or r 2 and r 2
r12 13 32

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r13 2 or r 2 and r 2
r13 13 33

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r14 2 or r 2 and r 2
r14 13 34

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

3
r21 2 or r 2 and r 2
r21 23 31
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj
3
r22 2 or r 2 and r 2
r22 23 32

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r23 2 or r 2 and r 2
r23 23 33

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r24 2 or r 2 and r 2
r24 23 34

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
2
r 31 2 or r 2 and r 2
r 31 33 31

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r 32 2 or r 2 and r 2
r 32 33 32
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj
3
r 33 2 or r 2 and r 2
r 33 33 33

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r 34 2 or r 2 and r 2
r 34 33 34

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
3
r41 2 or r 2 and r 2
r41 43 31

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

3
r42 2 or r 2 and r 2
r42 43 32

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

3
r43 2 or r 2 and r 2
r43 43 33
rijk rij(k  1) or rik
(k  1) (k  1)
and rkj

3
r44 2 or r 2 and r 2
r44 43 34

rijk rij(k  1) (k  1)
rik (k  1)
rkj
4
r11 3 or r 3 and r 3
r11 14 41

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
4
r12 3 or r 3 and r 3
r12 14 42

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
4
r13 3 or r 3 and r 3
r13 14 43
rijk rij(k  1) or rik
(k  1) and r (k  1)
kj
4
r14 3 or r 3 and r 3
r14 14 44

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
4
r21 3 or r 3 and r 3
r21 24 41

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

4
r22 3 or r 3 and r 3
r22 24 42

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

4
r23 3 or r 3 and r 3
r23 24 43

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

4
r24 3 or r 3 and r 3
r24 24 44
rijk rij(k  1) or rik
(k  1) (k  1)
and rkj

4
r 31 3 or r 3 and r 3
r 31 34 41

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

4
r 32 3 or r 3 and r 3
r 32 34 42

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

4
r 33 3 or r 3 and r 3
r 33 34 43

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
4
r 34 3 or r 3 and r 3
r 34 34 44

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj

4
r41 3 or r 3 and r 3
r41 44 41
 rijk rij(k  1) or rik
(k  1) and r (k  1)
kj
4
r42 3 or r 3 and r 3
r42 44 42

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
4
r43 3 or r 3 and r 3
r43 44 43

rijk rij(k  1) or rik

(k  1) and r (k  1)
kj
4
r44 3 or r 3 and r 3
r44 44 44

n2 n3

n3
 
  n2

 n2  n2  n2
n3

a b c d e

a 0 10   

10
a b b  0 20 40 
70
40
e 50 20
c   0 30 
60 d c
30
d 50   0 60

e 70    0


 D (0) , D(1) , ... D(k  1) , ... D(n)

D (k) " d ij "

vi vj
D (0)
D (0) vi vj i th j th
D (1)

D (n)

D (n)

5
1 3

8 2
1

D (0)
5
1 3 1 2 3
1 0 8 5
8 2
1
(0) 2 2 0 
D =
3  1 0
2

D (0)
vi vj i th j th 
vi vj

5
1 3 1 2 3
1 0 8 5
8 2 (1)
1 D = 2 2 0 7

3  1 0
2
 D (1)

  2 nd 3 rd

5
1 3 1 2 3
1 0 8 5
8 2 (2)
1 D = 2 2 0 7

3 3 1 0
2

D (2)

D (1)  3 rd 1 st

3 rd 1 st

5
1 3 1 2 3
1 0 6 5
8 2 (3)
1 D = 2 2 0 7

3 3 1 0
2

D (2) D (3) D (3)

D (3)
D (k) D (3)

D k [i, j] vi vj
{ v 1 , v 2 , v 3 ... v k}
D (0)
 vi vj {v 1 , v 2 , ... v k}
vk
D k [i, j] D (k 1) [i, j]

vi vj
{ v 1 , v 2 , ... v k} vk
D k [i, j] D (k  1) [i, k] + D (k  1) [k, j]

Shortest path using

intermediate vertices
{ v1,v 2, ... vk}

vk

(k –1)
dkj
(k – 1)
dik
vi vj

Shortest path using

vertices {v1, v2, ... vk–1}

D (k) [i, j] D (k  1) [i, j]

D (k) [i, j] D (k  1) [i, k] + D (k  1) [k, j]

D (k) [i, j] min D(k  1) [i, j] , D(k  1) [i, k]  D(k  1) [k, j]
 

 Computing D
(k)

using two cases

 1 with k 2 without k
Note that this as intermediate vertex
is the basic
operation in 
this algorithm

n n n
   1
k 1 i 1 j 1

n n u
  (n  1  1)  1  u  l 1
k 1 i 1 i l

n n
  n
k 1 i 1

n
1 2
 i 
2
n
i 1

n2
n
 n2
k 1
n
1 3
n3  n2 
3
n
i 1

(n 3 )
 D (0) , D(1) , .... D(n)

5
1 3 1 2 3
1 0 8 5
8 2 (0) 2 0 
1 W=D = 2
3  1 0
2

D (1)

 D (1)  D 1 [2, 3] min {D 0 [2, 3] , D 0 [2, 1]  D 0 [1, 3]}

 
D 1 [2, 3]

D (2)

D (2) 
 D 2 [1, 3] min {D 1 [1, 3] , D 1 [1, 2]

 D 1 [2, 3]}

D 2 [1, 3]

D 2 [3, 1]

D 2 [1, 3] D 2 [3, 1] min { D 1 [3, 1], D 1 [3, 2]  D 1 [2, 1]


 D 2 [3, 1]

D (3)

D (3)   D 3 [1, 2] min {D 2 [1, 2] , D 2 [1, 3]

 D 2 [3, 2]}

D 3 [1, 2]
 A B C D

A 0 3

B 2 0

C 7 0 1

D 6 0

D k 
min D (k– 1) i, j, D k– 1 i, k   D k– 1 k, j 

 

 

 

D k– 1
i, j, Dk– 1 i, k  Dk– 1 k, j
D 0 1,1, D 0 1,1 D 0 1,1

D  i, j, D  i, k D  k, j

k– 1 k– 1 k– 1

D  1,2, D  1,1 D  1,2

0 0 0
min , 0  


D k– 1

i, j, Dk– 1 i, k  Dk– 1 k, j

D 0 1,3, D 0 1,1 D 0 1,3



D k– 1

i, j, Dk– 1 i, k  Dk– 1 k, j

D 0 1,4 , D 0 1,1 D 0 1,4 

3, 0  3

 

 

 

 

 

 
  

 

0 2  1 8
6 0 3 2 
 
  0 4 
 
  2 0 3
 3    0 

D (k)  
min D (k– 1) [i, j], D (k– 1) [i, k]  D (k– 1) [k, j] 
D (1) D (2) D (3) D (4) D (5)


(0)
D   

 

  

D (1)

 
min D (k– 1) [i, j], D (k– 1) [i, k]  D (k– 1) [k, j]
min D 0 [1,1], D 0 [1,1]  D 0 [1,1]
D 1 [1, 1]

 
min D (k– 1) [i, j], D (k– 1) [i, k]  D (k– 1) [k, j]

min D 0 [1,2], D 0 [1,1]  D 0 [1,2]

D 1 [1, 2]

 
min D (k– 1) [i, j], D (k– 1) [i, k]  D (k– 1) [k, j]
min D 0 [1,3], D 0 [1,1]  D 0 [1,3]

min {  , 0   }
D 1 [1, 3] 

 
min D (k– 1) [i, j], D (k– 1) [i, k]  D (k– 1) [k, j]
min D 0 [1,4], D 0 [1,1]  D 0 [1,4]

D 1 [1, 4]

 
min D (k– 1) [i, j], D (k– 1) [i, k]  D (k– 1) [k, j]
min D 0 [1,5], D 0 [1,1]  D 0 [1,5]

D 1 [1, 5]

D1

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [2,1], D [2,1]  D [1,1]
0 0 0
D 1 [2, 1]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [2,2], D [2,1]  D [1,2]
0 0 0

D 1 [2, 2]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [2,3], D [2,1]  D [1,3]
0 0 0


D 1 [2, 3]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [2,4], D [2,1]  D [1,4]
0 0 0

D 1 [2, 4]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D 0 [2,5], D 0 [2,1]  D 0 [1,5]


D 1 [2, 5]

D (1)

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [3,1], D 0 [3,1]  D 0 [1,1]

  
D 1 [3, 1] 

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [3,2], D [3,1]  D [1,2]
0 0 0

 
D 1 [3, 2] 

 
min D 0 [i, j]+ D 0 [i, k]  D 0 [k, j]
min D [3,3], D [3,1]  D [1,3]
0 0 0

 
D 1 [3, 3]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [3,4], D [3,1]  D [1,4]
0 0 0


D 1 [3, 4]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [3,5], D [3,1]  D [1,5]
0 0 0

 
D 1 [3, 5] 

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [4,1], D [4,1]  D [1,1]
0 0 0
  
D 1 [4, 1] 

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]
min D [4,2], D [4,1]  D [1,2]
0 0 0

 
D 1 [4, 2] 

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [4,3], D 0 [4,1]  D 0 [1,3]

 
D 1 [4, 3]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [4,4], D 0 [4,1]  D 0 [1,4]


D 1 [4, 4]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [4,5], D 0 [4,1]  D 0 [1,5]


D 1 [4, 5]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [5,1], D 0 [5,1]  D 0 [1,1]

D 1 [5, 1]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [5,2], D 0 [5,1]  D 0 [1,2]


D 1 [5, 2]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [5,3], D 0 [5,1]  D 0 [1,3]

 
D 1 [5, 3] 

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [5,4], D 0 [5,1]  D 0 [1,4]


D 1 [5, 4]

 
min D 0 [i, j], D 0 [i, k]  D 0 [k, j]

min D 0 [5,5], D 0 [5,1]  D 0 [1,5]

D 1 [5, 5]
D (1)

D (1)
  

 

D (2)

  

 

D (3)

  

 

D (4)
 

 
D (5)
 A C

B D

A C C

Delete Delete Delete

E E
B A D

D D
B B,A

C
delete delete
E
C E
E
Sorted List : B,A,D
B,A,D,C B,A,D,C,E
 Input graph is

0 2

1 3
 2
5

1 3 7

6
4

2
5

3 7

6
4

2
5

6
4

6
4
 5

V1 Link Link V2

V4 Link Link V3
 V1
e1 e2
Here V1, V2, V3 and V4
are vertices and
V2 V3 e1, e2, e3 and e4
are edges.
e4 e3

V4
Static symbol table

Dynamic symbol table

 C

B
B

A C
A

Tree 1 Tree 2

 (Number of nodes  Number of comparisons)

Total number of nodes present in the tree

 (Number of nodes  Comparisons made) (1  3)  (1  2)  (1  1)

Total number of nodes 3

 (Number of nodes  Comparisons made) ( 2  2)  (1  1)

Total number of nodes 3
 P2
Level 1 B

P1 P3
Level 2 A C

Level 3
q0 q1 q2 q3

 n   n 
  p i ( Level of i node)     q i ( Level of failure node i) – 1
th
i  1  i  1 

pi qi

pi qi

 1 * 1  1 * 2  1 * 2   1 * 2  1 * 2  1 * 2  1 * 2   1  4   8 
7 7 7  7 7 7 7   7 7  7 

13
7
n th
 

number of external nodes of left subtree

total number of external nodes of tree

5/8
10

3/5
8 12 2/3

1/2
1/3
6 9 11
1/2
1/2
7
 

 p(i)   q (i)
1i n 1i n
 min
i k  j

min
i  k  j {C(i, k 1)  C k, j }  W i, j
 i
0 1 2 3 4

0 W00 = 2 W11 = 3 W22 = 1 W33 = 1 W44 = 1

1 W01 = 8 W12 = 7 W12 = 3 W34 = 3

j–i
2 W02 = 12 W13 = 9 W24 = 5

3 W03 = 14 W14 = 11

4 W04 = 16


 
min
i  k  j {C(i, k 1)  C k, j }

min{C(i, k 1)  C kj }  W ij
 i
0 1 2 3 4
C00 = 0 C11 = 0 C22 = 0 C33 = 0 C44 = 0
0
r00 = 0 r11 = 0 r22 = 0 r33 = 0 r44 = 0

C01 = 8 C12 = 7 C23 = 3 C34 = 3

1
r01 = 1 r12 = 2 r23 = 3 r34 = 4
j–i
C02 = 19 C13 = 12 C24 = 8
2
r02 = 1 r13 = 2 r24 = 3

C03 = 25 C14 = 19
3
r03 = 2 r14 = 2

}
C04 = 32
4 T04
r04 = 2

if

do int

while



















 







 P1
do

P2 P2
if
if
q3

P3 P1 P3
while do while
q2

q0 q1 q0 q1 q2 q3

I II

P3
while P3
while

P2
if P1 q3
do
q3

P1
do q0 if P2
q2

q0 q1 q1 q2

III IV
 P1
do

q0 while P3

P2 if q3

q1 q2

 P( i)  level ( a i )   q(i)   level (E i ) – 1

1 i  n 0 i n

 1  3  1  2  1  1   1  ( 4 – 1)  1  ( 4 – 1)  1  ( 3 – 1)  1  ( 2 – 1)  6 9

7 7 7  7 7 7 7  7 7

15
7
 1   1 1   1 1 1 1  5 8
 7  1    2  7  2  7   7  ( 3 – 1)  7  ( 3 – 1)  7  ( 3 – 1)  7  ( 3 – 1)  
7 7
     
13
7
 1  1  1  2  1  3   1  ( 2 – 1)  1  ( 3 – 1)  1  2  ( 4 – 1)  6 9

7 7 7  7 7 7  7 7
15
7

 1  1  1  2  1  3   1  ( 2 – 1)  1  ( 3 – 1)  1  ( 4 – 1)  1  ( 4 – 1)  6 9

7 7 7  7 7 7 7  7 7
 15
7
 1  1  1  2  1  3   1  ( 2 – 1)  1  ( 3 – 1)  1  ( 4 – 1)  1  ( 4 – 1) 
7 7 7  7 7 7 7 
15
7

(0.5  1  0.1  2  0.05  3)   0.05  1  0.05  2  0.15  3  0.1  3

P2  1  P1  2  P3  2 q 0  2  q 1  2  q 2  2  q 3  2
0.1  1  0.5  2  0.05  2  0.15  2  0.1  2  0.05  2  0.05  2

P1  3  P2  2  P3  1 3  ( q 0  q 1 )  2  ( q 2 )  1  q 3 
05 .  2  0.05  1 3  ( 015
.  3  01 . )  2  0.05  0.05
.  01

P1  2  P2  3  P3  1 2  q 0  3  ( q 1  q 2 )  1  q 3 
0.5  2  0.1  3  0.05  1  2  0.15  3  (0.1  0.05)  0.05 

P1  1  P2  3  P3  2 1  q 0  3  q 1  3  q 2  2  q 3 
0.5  1  0.1  3  0.05  2  1  0.15 3  0.1  3  0.05  2  0.05
 0 1 2 3 4
1 0 4

2 0 2
3 Fi 0 6
ll u
p
4 di 0 3
ag
on
5 al 0
ly
Cost table
C[1, 0]  0 
C[2, 1]  0  Using formulae

C[3, 2]  0  C[i, i - 1] = 0 and
C[4, 3]  0  C[n  1, n]  0

C[5, 4]  0 
C[1, 1] = 1 
C[2, 2] = 2  Using Formula

C[3, 3] = 3  C[i, i]  Frequency [i]
C[4, 4] = 4 

R[1, 1] = 1 
R[2, 2] = 2  Using Formula

R[3, 3] = 3  R[i, i]  i
R[4, 4] = 4 

j
min C[i, K  1]  C[K  1, j]   Ps
i K j s i

When k = 1
C [1, 0] + C [2, 2] + F [1] + F [2]
=0+2+4+2
=8
C [1, 2] =

When k = 2
C [1, 1] + C [3, 2] + P [1] + P [2]
=4+0+4+2
= 10
 

k=2
C [2, 1] + C [3, 3] + F [2] + F [3]
=0+6+2+6
C [2, 3] = = 14

k=3
C [2, 2] + C [4, 3] + F [2] + F [3]
=2+0+2+6
= 10

When k = 3
C [3, 2] + C [4, 4] + F [3] + F [4]
=0+3+6+3
= 12
C [3, 4] =

When k = 4
C [3, 3] + C [5, 4] + F [3] + F [4]
=6+0+6+3
= 15

0 1 2 3 4 1 2 3 4
1 0 4 8 1 1 1

2 0 2 10 2 2 3
3 0 6 12 3 3 3

4 0 3 4 4
5 0
 When k = 1
C [1, 0] + C [2, 3] + F [1] + F [2] + F [3]
= 0 + 10 + 4 + 2 + 6 = 22
When k = 2
C [1, 3] = C [1, 1] + C [3, 3] + F [1] + F [2] + F [3]
= 4 + 6 + 4 + 2 + 6 = 22
When k = 3
C [1, 2] + C [4, 3] + F [1] + F [2] + F [3]
= 8 + 0 + 4 + 2 + 6 = 20

When k = 2
C [2, 1] + C [3, 4] + F [2] + F [3] + F [4]
= 0 + 12 + 2 + 6 + 3 = 23
When k = 3
C [2, 4] = C [2, 2] + C [4, 4] + F [2] + F [3] + F [4]
= 2 + 3 + 2 + 6 + 3 = 16
When k = 4
C [2, 3] + C [5, 4] + F [2] + F [3] + F [4]
= 10 + 0 + 2 + 6 + 3 = 21

0 1 2 3 4 1 2 3 4
1 0 4 8 20 1 1 3

2 0 2 10 3 2 3 3

3 0 6 12 3 3

4 0 3 4
5 0

When k = 1
C [1, 0] + C [2, 4] + F [1] + F [2] + F [3] + F [4]
= 0 + 3 + 4 + 2 + 6 + 3 = 18
When k = 2
C [1, 1] + C [3, 4] + F [1] + F [2] + F [3] + F [4]
C [1, 4] = = 4 + 12 + 4 + 2 + 6 + 3 = 31
When k = 3
C [1, 2] + C [4, 4] + F [1] + F [2] + F [3] + F [4]
= 8 + 3 + 4 + 2 + 6 + 3 = 26
When k = 4
C [1, 3] + C [5, 4] + F [1] + F [2] + F [3] + F [4]
= 20 + 0 + 4 + 2 + 6 + 3 = 35
 0 1 2 3 4 1 2 3 4
0 4 8 20 18 1 1 1 3 1 Root

0 2 10 3 2 2 3 3

0 6 12 3 3 3

0 3 4 4
0

1 2 3 4
10 20 30 40

Root




10

30 T [2, 4] with k = 3

10

30

20 40

This is required OBST

with optimum cost C [1, 4] = 18
 BF = 2
10

BF = 2 BF = 0
10
8 15
BF = 0 BF = 0
8 15 BF = 2
9 12 18
7
BF = 1
7 9 12 18
5
BF = 0
4

Nh
 Nh N h 1  N h 2  1

Nh
 N0  0 N1  2

Nh N h 1  N h 2  1
2N h  2
4N h  4

2i N
h 2i

h
2 1

2 1
2h N2

2h 2 1  4 N2  4

(h  1) 2
2( h  1) 2 N 1

2(h  1) 2 1 N1  1

Fh

root

h–1 h

h–2

F h
 |F h| |F h  1||F h  2| 1
|F0| |F 1|

|F h| 1 (|F h  1| 1)  (|F h  2| 1)

|F h| 1

h 3
1  1 5 
|F h| 1   
5  2 

 |F h|

F0
F1
F2
F3

Sh Sh – 2  Sh – 1  1

B BF = 1
A BF = 0
When h = 0 A
Minimum nodes = 1 BF = 0
When h = 1
Minimum nodes = 2
Sh Sh – 2  Sh – 1  1
 Sm Sm – 2  Sm – 1  1

S k 1 S k  1– 2  S k  1– 1  1

S k 1 Sk – 1  Sk  1

Sm Sm – 2  Sm – 1  1

S k 1 Sk – 1  Sk  1

Sk Sk – 2  Sk  1

Sh Sh – 2  Sh – 1 1
 BF = 1
1
12 12

BF = –1 BF = +1 BF = 2
–1 +1
18 9 18
9

BF = 0 BF = 1
BF = 0
0 1 0
11 15 7 11 15
7

BF = 0
0 13
10 10

Original AVL tree Insert 13 property violated

+1
12

–1 0
9 15

0 +1 0 0
7 11 13 18

0
10

Restore AVL property

 12 12


9 18 9 15

7 11 15 7 11 13 18

10 13 10

By adjusting node 15 the

Nodes 18,15,13 entire tree satisfies AVL
are to be adjusted property
 Single rotation Double rotation

Left-Left Left-Right
(LL rotation) (LR rotation)

Right-Right Right-Left
(RR rotation) (RL rotation)

+2 0
A B

+1
4
0
 C
0
A
0

B
0 0 0 0
1 2 3 4
0
0 3
C

0
0 2
1
 –2 0
A B

0 0


0 –1 A C
1 B

0 0 0 0
1 2 3 4
0
0 C
2

0 0
3 4

+2 0
A C

B
–1
4
–2
 B
0
A
0

0 0 0 0 0
C 1 2 3 4
0
1

0 0
2 3
 –2 0
A C


+1
B 0 0
A B
0
1 0
0
C 4
0 0 0 0
1 2 3 4

0 0
2 3

10

+2
5
+1
14
A
+2 0 +1
3 7 13
0
18
B
+1
2 11

C
0
1
 0
10

+1
5
+1
14

0 0 +1
2 7 13
0
18
0
1 0
3 0
11

0
10

+1
5
0
14

0 0
2 7 +1 –1
13 18

0 0 0
1 3 25
0
11

–1 0
10 10

+1 +1
5 5
0
–1 14
14
0 0 A RR 0 0 0 B
2 7 +1 –2 2 7 +1 25
13 18 13
B C
0 0
–1 0 A 0 0
1 3 0 18 28
0
25 1 3 0
11 C 11
0
28
 0
10

+1
5
+1
14
0
7 A
0 0
2 +2 25
13
0
3 0 0
0 18 28
1 B –1
11

0
C 12

0
10

+1
5
0
14

0 0 C
2 7 0
0 25
12
0
0 28
0 0 18
1 3 B A
0 0
11 13

–1
30
0
30
0
50
 –2
30
0
50
–1 RR
50
0 0
30 110
0
110

–1 0
50 50

0 1 –1 1
30 110 30 110

0 0 0
80 40 80

0 0
50 50

0 1 0 0
30 110 30 110

0 0 0 0 0 0 0
10 40 80 10 40 80 120

–1 0
50 50

0 1 1 1
30 110 30 110

0 0 1 0 –1 0 1 0
10 40 80 120 10 40 80 120

0 0 0
60 20 60
 –1 0
50 50

1 2 1 1
30 110 30 110

LR
–1 0 2 0 –1 0 0 0
10 40 80 120 10 40 70 120

0 –1 0 0 0
20 60 20 60 80

0
70

–1 0
50 50

1 2 1 0
30 110 30 80

LR
–1 0 –1 0 –1 0 1 0
10 40 70 120 10 40 70 110

0 0 –1 0 0 0 0
20 60 80 20 60 100 120

0
100

–1
50

1 –1
30 80

–1 0 1 1
10 40 70 110

0 0 1 0
20 60 100 120

0
90

This is required AVL Tree

 10

5 Delete it
0
14

2 7
0
12 0
25
1

0 0 0 0
11 13 18 28

0
10 10

+1 0
5 5 18
+2 LL
25
–1
+1 25
2 0
7 0
2 7 +2 12
0
18 28 0
0 28
1
0 0 0
1 12 0 11 13
13
0
11
 10

5 14

7 12 25
2

1 3 11 13 18 28
 –1
A
0
A
0
no balancing z
no balancing

–2
A 0 –1
B B
+1 RL
Z 0 0 0 +1
A Z A Z
0
B
0
Y
 –2
B –1
B
+2 LL
A Z 0 0
A Y
+1
Y
0 0
C Z
0
C

–2
B 0
C
0 +1 RL
A Y +1 0
B Y
–1 0 0
C Z A 0 0
X Z
0
X

–1 –2 –1
C C C

+1 +1 +1 +2 +1 +1
B Y B Y B Y

0 0
A A 0
LR 0
+1 0 +2 0 0
X Z X Z A E Z

0 –1 0 0
D D D X

0
E
 –2 –1
C C
+1 +2 LR
B Y +1 0
B X
0
A –1 0 0
E Z A –1
0 Y
E
0
D +1
X 0 0 0
D V Z
0
V

0
–2 E
C

+1 +1 +1 0
RL C X
B X

0 +1 0
A –1
–1 –1 B D +1 Y
E Y V
0
0 A
D +1 0
V 0 0
Z Z
F
0
F

–1 0
E E

+1 +1 LR +1 0
C X C X

+1 0 –1
0 D
+1 D +2 –1 B 0 Y
B V Y M
0
A
0 0 0
A –1 Z 0 0
F V Z
F

0
M
 –1
E

+1 +1
C X
is a final AVL tree.
+1 0 –1
B D –1 Y
M
0
A
+1 0
0 Z
F V

0
R

0 –1
December December

0
Jan

–1
December
0
December

0 –1
April Jan
0 0
April Jan
0
March
 –2 –1
December December

RL 0
0 –2 July
April 0
Jan April

+1 0 0
March Jan March

0
July

0 –1
December December

–1 0 –1
+1 July
April July April

0 0 –1
Jan March 0 March
0 Jan
August 0
August

0
Oct

–2 –1
December December

RL
–1 –2 –1 –1
April July April July

0 –2 0
0 Nov
Jan March Jan
0 0
August August

+1
Oct 0 0
March Oct

0
Nov
 –1
December December

–2
April July RL –1 0
April March

+1 0
Jan Nov 0 +1
Nov
August August July

–1 0
Oct 0 0
March 0 Oct
Jan May

0
May

–1
December

–1 0
April March

0
0 Nov
July
0
August
0
0
0 Oct
0 May
Jan June

is a final AVL tree.

–1
30
0
30
0
31
 0
31
–2 RR
30
0 0
32 32
–1
31

0
32

+2 +1
31 31
+1
31 +2 0 LL 0
30 0
32 23 32
+1 0
30 32 +1
23
0 0
0 22 30
23 0
22

+2 0
31 30

–1 0 LR 0 –1
23 32 23 31

0 0
22 +1
30 0 0 32
22 28

0
28

+1 +1
30 30

–1 –1 –1 –1
23 31 23 31

0 0
0 +1 32 0 0 32
22 28 22 28

0 0 0
24 24 29
 +2 +1
30 30

–2 –1 0 –1
23 31 24 31

0 RL 0
0 +1 32 +1 0 32
22 28 23 28

0
–1 0 22 0 0
24 29 26 29

0
26

+2 0
30 28

LR
–1 –1 0 –1
24 31 24 30

0 –1
+1 +1 32 +1 –1 0 31
23 28 23 26 29
00
32
32
0 0
22 –1 0 22 0
26 29 27

0
27

–1 0
28 28

0 –2 0 –1
24 30 RR 24 30

–2 0
+1 –1 31 +1 26 0 32
23 26 29 23 29
–1 00
32 0
34
32
0 0 0
22 22 27 31
27
0
34
 –1 0
28 28

0
0 –2 0 32
24 30 RR 24

–1
0 34
–1 +1 30
+1 –1 0 32 23 –1
23 26 29 26
0
0
360
32
–1 0 0
0 34 22 29 31
0 0
22
0 31 27
27
0
36
is an AVL tree




0 –1 –2
40 40 40
RR
0
60
0 –1
60 60
0 0
40 80
0
80

+1 +2
60 60 60

–1 –2 0 RL
40 0 40 80 0 0
80 45 80

0 +1
50 50 0 0
40 50

0
45
 +2 0
60 50

45
–1
80
0 LR
0 –1
45 60

0 +1
40 50
0 0 0
40 47 80

0
47

+1
50 50
+2 +1
50

45
+1 –1 +2 –1 RL
60 45 60 +1 –1
45 60

–1 0 0
40 47 80
0
40
–2
47
0 80 0 0 80
0
42 47

0 +1
44 44 0 0
40 44
0
42

0 +1
50 50

+1 –2 +1 0
45 60 45 75
RL

0 0 –1 0 0 0
42 47 80 42 47 60 80

0 0 0 0 0
40 44 75 40 44
 +1 +2
50 50

0 0 +2 0
45 75 45 75
LL

0 +1 0 0 +1 +1 0 0
42 47 60 80 42 47 60 80

0 0 +1 0
40 44 46
0
40 44 46

0
41

0
45

+1 0
42 50

–1 +1 0
40 44 47 75

0 0 0 0
41 46 60 80

Final AVL Tree

+1
STA

0
STA

0
ADD
 –1
LDA
+2
STA

0 +1
ADD STA
–1 LR LDA
0
ADD

0 0 0
LDA ADD STA 0
MOV

This is final AVL tree

–1
10
0
10
0
20

–2 0
10 15

RL
+1 0 0
20 10 20

0
15

+1 0
15 15

–1 0 –1 –1
10 20 10 20

0 0 0
12 12 25
 –1 0
15 15

RR
–1 –2 –1 0
10 20 10 25

0 –1 0 0 0
12 25 12 20 30

Final AVL Tree

0
30

–1
15
0
15
0
20

–2
15 0
RR 20
–1 Rotation
20
0 0
15 24
0
24

+2 +1
20 20
+1
20
–2 0
LR
15 24 0 0
+1 Rotation 13 24
15 0
24
–1
10
0 0
10
0 10 15
0
13
 +2 0
20 13

13
+1 0 LL
24 +1 0
Rotation 10 20

+1 0
10 15
0 0 0
7 15 24

0
7

–1
13

+1 –1
10 20

0 –1
7
0 15 24

0
30

–2 –1
13 13

+1 –2 RR +1 –1
10 20 10 20
Rotation

0 –2 0 0
7
0 15 24 7
0 15 30

–1 0 0
30 24 36

0
36
 –2 –1
13 13

+1 –2 RL +1 0
10 20 10 24
Rotation

0 +1 +1 0
7
0 15 30 7
0 20 30

0
–1 0 15 0 0
24 36 25 36

0
25

+1 0
15 15
RR
–2 0 0 0
10 25 12 25

–1 0 0 0 0 0 0
12 20 30 10 14 20 30

0
14

–1
15

0 –1
12 25

0 0 –1 0
10 14 20 30

0
22
 –1
15

0 0
12 25

0 0 –1 –1
10 14 20 30

0 0
22 35

–2 –1
15 15
RR
0 –1 0 0
12 25 12 25

–2
0 0 –1 30 0 0 –1 0
10 14 20 10 14 20 35
–1
35
0
22 0 0 0
0 22 30 40
40

AVL tree
 70

Red node
40
90

Black node

30 50 80 100

NULL NULL
45 NULL NULL 88 NULL NULL

NULL NULL NULL NULL

 Cases of Insertion

Uncle of newly inserted Uncle of newly inserted

node is black node is red

p red

x red
Balancing
is done when in
red black tree
red p

x red
 g black g red

Uncle Red
case
red p u red black p u black
i) Change colour of
p and u to black
ii) Change colour
x of g to red x
red red

black g black p

Uncle black
LL case
red p black u red x red g

red x T3 T4 T5 black u
T1 T2 T3

T1 T2 T4 T5

black g black x

Uncle black
LR case
red p black u red p red g

T1 red x T4 T5 T1 T2 T3 black u

T2 T3 T4 T5
 black g black p

Uncle black
RR case
black u red p red g red x

T1 T2 T3 red x black u T3 T4 T5

T4 T5 T1 T2

black g black x

Uncle black
RL case
black u red p red g red p

T1 T2 x red T5 black u T3 T4 T5

T1 T2
T3 T4

As it is
2 red 2 black
root node

2 black

1 red
 2 black

1 red 4 red

2 black 2 black

Here uncle is
u 1 red p 4 red 1 black 4 black
red simply recolor

x 5 red 5 red

black 2

black 1 black 4
red parent
and red
child causes
u p 5 red unbalancing
No left
child means
black external 9 red
x
node.
Here u i.e.
uncle
node is black

2 black 2 black
Uncle black and
Right-Right
black 1 g 4 black case 1 black p 5 black
i) Left rotate g
ii) Swap colors
p 5 red of g and p g 4 red x 9 red
u

x 9 red
 black 2

black 1 black 5 Uncle

is red

red 4 p red 9 u

red parent and

red 3 x red child causes
unbalacing

2 black 2 black

Uncle red
g black i) Change p & u g red
black 1 5 1 black 5
to black
ii) Change g to red
p 4 red red 9 u p 4 black u 9 black

x 3 red x 3 red

2 black

As here parent
1 black 5 red node i.e. 9 is
black and
child node i.e.
4 black 9 black 6 is red, there is
no need for
adjustment.
3 red 6 red
 2 black

1 black 5 red

Uncle is
4 black g 9 black black

3 red p 6 red u
red Parent
and red child
x 7 red causes
unbalancing

2 black 2 black
Uncle black
and left
right case
1 black 5 red 1 black 5 red

black 4 u black 9 g 4 black 7 black

x

red 3 red 6 p u 3 red 6 p g 9

red 7 x

2 black

1 black 5 red

4 black 7 black

3 red 6 red 9 red

Delete
this node

black

NULL

black

Double
black

10 black 10 black

Either x
or y is red
y 8 black 12 black x 7 12
Delete 8
black black
x 7 red
 10 black
10 black
black black
y Delete 8
8 12 black NULL
NULL 12 black

x
x 15 red 15 red

Conversion from double black

to single black

Sibling s is black Sibling s is black Sibling is

and at least one and both red
child of sibling is red children are black.

black 10 p 10 black

black
on deleting
black 8 12
12 s 8 black NULL
NULL x

red 7 r 7
red

s
8
black
r
p
black 7 10 black
 black 10 p black 10 p
Delete 12
s s
NULL
black 8 12 black black 8 NULL

9 r 9 r
red red

10 black r 9 black

s
black NULL
8 NULL s 8 black 10 p

black black
red 9 r

black 10 p black 10 p

Delete 8 NULL
black 8 black 12 s black NULL black 12 s

11 15 r 11 15 r
red red red red

black 12 s

black 10 p black 15 r

11 red
 black 10 p black 10 p
black
Delete 8 NULL
black 8 black 12 s NULL black 12 s

11 r 11 r
red red

black 12 s

black 10 p black 11 r

p is subtree p is subtree

black 10 p black 10 p
delete 8

x black 12 s NULL
black 8 NULL black 12 s

p is subtree

black 10

Check for matching

NULL case from A, B, C to
NULL red 12 s remove double black
 p 10 black p 10 black

Delete 12 NULL
s 8 red 12 black s 8 red NULL black

r 7 black 9 black r 7 black 9 black

s 8 black

r 7 black p 10 black

9 red

black 10 p black 10 p

Delete 8 NULL
black 8 red 12 s black NULL red 12 s

black 11 black 15 black 11 black 15

black 12 p

black 10 black 15 s

red 11
 25 black

red 10 50 red

black 5 black 20 40 black 60 black

22 red

25 black

red 10 50 red

black 5 black 20 40 black 60 black

22 red

25 black

red 10 50 red
Case 2B
sibling is
NULL
NULL black black with
black 5 black 20 40 black both children
as black
Recolor
22 red
 25 black 25 black

red 10 50 black red 10 50 black

5 20 40 red 5 20 40 red
black black black black

22 red 22 red

25 black 25 black

red 10 50 black red 10 40 black

5 20 40 red 5 20
black black black black

22 red 22 red

25 black 25 black

NULL
red 10 40 black red 10 NULL black

5 20 5 20
black black black black

22 red 22 red
 10 black

black 5 red
25

NULL
20 black NULL

22
red

10 black

black 5 red
22

20 black 25 black
 2 black

1 black 5 red

3 black 7 black

4 red 8 red
 Horizontal links

Left horizontal Two consecutive

restriction links are not right links are
allowed not allowed

Apply Apply
remedy
skew operation spilt operation

red p x black p x

A B C A B C
 y

black red
black x y z x z

A B A B

8 Level 1

Level 3

Level 2

red 3 8 Level 1
 Level 3

Level 2

black 3 8 black Level 1

Level 3

Level 2

3 8 10 red Level 1

8 black Level 2

black 3 10 black Level 1

8 black Level 2

black 3 10 18 red Level 1

black
 8 Level 2

3 10 18 Level 1

12 red

8 Level 2

3 10 12 18 red Level 1

black 8 12 black Level 2

3 10 18 Level 1
black black black

8 12 Level 2

red 2 3 10 18 Level 1
 8 12 Level 2

2 3 10 18 Level 1
 8 16 Level 3

5 12 14 18 Level 2

4 6 11 13 15 17 20 Level 1

8 16 Level 3

5 12 14 18 Level 2

4 6 11 13 15 17 20 Level 1

red 8 16 Level 3

12 14 18 Level 2

5 6 11 13 15 17 20 Level 1
 red red
8 16

Level 2

12 14 18 red

5 6 11 13 15 17 20 Level 1

red red red

8 12 16

Level 2

14 18 red

5 6 11 13 15 17 20 Level 1

red red red red

8 12 14 16 18 red Level 2

5 6 11 13 15 17 20 Level 1
 red red red red
8 12 14 16 18 red

5 6 11 13 15 17 20

8 12 Level 3

red red red

8 14 16 18 Level 2

5 6 11 13 15 17 20 Level 1

8 12 Level 3

red red
8 14 16 18 red Level 2

5 6 11 13 15 17 20 Level 1

8 12 16 Level 3

8 14 14 18 Level 2

5 6 11 13 15 17 20 Level 1
 5, 8 x

5, 8 x

18, 14 y

5, 8 x

18, 14 y

12, 14 x
 5, 8 x

18, 14 y

8, 11 12, 14 x

5, 8 x

18, 14 y

8, 11 12, 14 x

10, 2 y

5, 8 x

3, 6 18, 14 y

8, 11 12, 14 x

10, 2 11, 20 y
 Y

20
(11, 20)

18

16

(12, 14) (18, 14)

14

12
(8, 11)
10

8 (5, 8)

6
(3, 6)

(10, 2)
2

X
2 4 6 8 10 12 14 16 18 20
 g


x

P D P g

A x A B C D

B C


x

P D A P

x C B g

A B C D
 
P x

x C A P

A B B C

4 50
12

2 6 10 14

1 3 5 7 9 11 13 15
 8

4 50
12

2 6 10 14

1 3 5 7 9 11 13 15

2 4

2 50
8

On expanding
above tree 1 4 12
we get this tree

6 10 14

5 7 9 11 13 15
 1

1 3

2 4

3 5

4 6 Zag-zag (RR) rotation

g
5 7
P
8 8
x
7

6
1 1

2 2
Zag -zag Zag -zag
3 3

4 8
g
5
P 5
P 8

g 4 7
7

6
6

1 8

8 1
Zag or R
3 operation 3

2 5 2 5

7 7
4 4

6 6

is a splay tree

0 P 2
Zag

rotation
2 x 0
 2 P 4
Zag

rotation
0 4 x 2

4 6
Zag

rotation
2 6 4

0 2

6 8
Zag

rotation 6
4 8

2 4

2
0

0
 8 13
Zag

rotation
6 13 8

4 6

2 4

2
0

13 11
g

Zig-zag
8 P 8 13
rotation

6 11 x 6

4 4

2
2

0
0
 10

6 12

7 8 15

7 10

12

15

10

6 15

7
 I do II if

if do while

while

III while IV while

if do

do if

V do

while

if
 TM

TECHNICAL PUBLICATIONS - An up thrust for knowledge

a1 a 2 a 3

a1

a2

a3

a4

a5
 Data file
Primary Primary index
key Block 1 RollNo Name Age
Search key Address 11AS01 AAA 25
(RegNo) (Pointer)
11AS03 BBB 15
11AS01

11AS011 
11AS30

Block 30

11AS30 XXX 32
11AS31 YYY 38
11AS32 ZZZ 41
log 2
n+1 (log 2
300) + 1 

log 2
n+1 (log 2
3) + 1 

10
10
20
20
30 
40
RollNo Pointer 50
50
10
100 100
1000 200 100

Primary 300 200

level
indexing 400 
500
500
Intermediate
indexing Disk block
 Agra Agra UP
Amritsar Amritsar Punjab
Bhopal Bhopal MP
Baroda Baroda Gujrat
Chennai Chennai Tamilnadu
Coimbatore Coimbatore Tamilnadu
Delhi Delhi Delhi

Agra Agra UP
Bhopal Amritsar Punjab
Chennai Bhopal MP
Delhi Baroda Gujrat
Chennai Tamilnadu
Coimbatore Tamilnadu
Delhi Delhi
 Here each node can have
F K O at the most 4 nodes.
Level 1
Hence this tree is said
to be of order 4.

C D G M N P Q W
Level 2

S T X Y Z
Level 3
1 3 7 14
 7 Here 1 and 3 are < 7
 These are at left branch.
Node 8 and 14>7
 These are at right branch.

1 3 8 14

1 3 5 8 11 14 17

7 13

1 3 5 8 11 14 17

7 13

1 3 5 6 8 11 12 14 17 20 23
 7 13 20

1 3 5 6 8 11 12 14 17 23 26

4 7 13 20

1 3 5 6 8 11 12 14 16 17 18 23 24 25 26

13

4 7 17 20

1 3 5 6 8 11 12 14 16 18 19 23 24 25 26

11 14 21 78
 21

11 14 78 97

21

11 14 74 78 85 97

21 78

11 14 63 74 85 97

21 78

11 14 42 45 63 74 85 97
 21 57 78

11 14 42 45 63 74 85 97

21 57 78

11 14 16 20 42 45 63 74 85 97

16 21 57 78

11 14 19 20 42 45 63 74 85 97

16 21 57 78

11 14 19 20 30 42 45 52 63 74 85 97
 42

16 21 57 78

11 14 19 20 21 30 45 52 63 74 85 97

12

10 12 50 85

6 10 50 85

12
12 70

6 10 50 60 70 85
6 10 50 60 80 85
 12 70

6 10 37 50 60 65 80 85 100 120

12 70 100

6 10 37 50 60 65 80 85 120 150

12 60 70 100

6 10 37 50 62 65 80 85 120 150

12 60 70 100

6 10 17 30 37 50 62 65 80 85 120 150
 60

12 30 70 100

6 10 15 17 37 50 62 65 80 85 120 150

60

12 30 70 100

6 10 15 17 28 37 50 62 65 75 78 80 85 120 150


 




13

4 7 17 20

1 3 5 6 8 11 12 14 16 18 19 23 24 25 26

13

4 7 17 20
Here 2 key  3
children allowed.

1 3 5 6 11 12 14 16 18 19 23 24 25 26
 13

4 7 17 23

1 3 5 6 11 12 14 16 18 19 24 25 26

13

4 7 17 24

1 3 5 6 11 12 14 16 19 23 25 26
 13

7 17 24

1 3 4 6 11 12 14 16 19 23 25 26

7 13 17 24

1 3 4 6 11 12 14 16 19 23 25 26

20

10 20
10 30
 12 20
20

10 15 30
10 15 30

12 20 20

12 40
10 15 30 40

10 15 30 50
 13

4 7 17 20

1 3 5 6 8 11 12 14 16 18 19 23 24 25 26


  

 ( m  1) 2 ( m  1) h  1
h
1  2m (m  1) i  1
i 1

n
log m  1
2m
 3 7 9 23

3 7 23 45

1 3 5 7 14 23 25 45

9 24

1 3 5 7 14 23 25 45
 9 24

1 3 5 7 11 13 14 23 25 45

5 9 24

1 3 7 8 11 13 14 23 25 45

5 9 14 24

1 3 7 8 11 13 19 23 25 45

5 9 14 24

1 3 4 7 8 11 13 23 25 31 35 45
 14

5 9 24 31

1 3 4 7 8 11 13 23 25 35 45 56

This is required B- tree

13

4 7 17 20

1 3 5 6 8 11 12 14 16 18 19 23 24 25 26

13

4 7 17 20
Here 2 key  3
children allowed.

1 3 5 6 11 12 14 16 18 19 23 24 25 26
 13

4 7 17 23

1 3 5 6 11 12 14 16 18 19 24 25 26

13

4 7 17 24

1 3 5 6 11 12 14 16 19 23 25 26

13

7 17 24

1 3 4 6 11 12 14 16 19 23 25 26
 7 13 17 24

1 3 4 6 11 12 14 16 19 23 25 26

13

4 7 17 24

1 3 4 5 6 7 11 12 13 14 16 17 19 23 24 25 26

R5 R6 R7 R11 R12 R13 R14 R16 R17 R19 R23 R24 R25 R26

R1 R3 R4
 Q

F S

F Q S

Q F Q

F K Q S C F K Q S

F Q

C F K L Q S
 K

F H Q

C F H K L Q S

F H Q S

C F H K L Q S T

K S

F H Q T

C F H K L Q S T V
 K S

F H Q T V

C F H K L Q S T V W

K S

F H Q L T V

C F H K Q L M S T V W

K S

F H Q L T V

C F H K Q L M R S T V W
 23 30 31 32

30

22 23 30 31 32

30

22 23 24 28 30 31 32

24 30

22 23 24 28 29 30 31 32
 24 30

15 22 23 24 26 27 28 30 31 32

24 30

15 22 23 24 26 27 28 30 31 32 34

24 30 32

15 22 23 24 26 27 28 30 31 32 34 39

24 30 32

15 22 23 24 26 27 28 30 31 32 34 36 39

is required B+ tree.
 28

1 42

1 28 42

28 28 31

1 21 28 42 1 21 28 31 42

28

10 31

1 10 21 28 31 42
 28

10 17 31

1 10 17 21 28 31 42

28

10 17 31 31

1 7 10 17 21 28 31 31 42

17 28

10 20 21 31 31

1 7 10 17 20 21 25 28 31 31 42
 17 28

10 20 21 31 31

1 7 10 17 20 21 25 28 31 31 42

17 28

10 20 21 31 31

1 7 10 17 18 20 21 25 28 31 31 42

1 4 7
 7

1 4 7 10

1 4 7 10 17

7 17

1 4 7 10 17 21

7 17

1 4 7 10 17 21 31
 7 17 25

1 4 7 10 17 21 25 31

7 17 25

1 4 7 10 17 19 21 25 31

20

7 17 25

1 4 7 10 17 19 20 21 25 31
 20

7 17 25 31

1 4 7 10 17 19 20 21 25 28 31 42

B+ tree

a b

r a
l n

l o d t d
e

n
o

t e
 m i n i m i z e m i n i m a

0 1 2 3 4 5 6 7 8 9 10 11 12 13

mi a ma i nima inima

zeminima nima ma nima zeminima mizeminima nimizeminima

4,5 13 12,13 1,1 10,13 9,13

6,13 10,13 12,13 10,13 6,13 4,13 2,13

Types of heap

Min heap Max heap

 18 10
Note that
every parent
12 4 8 node is
greater / equal
than its
11 10 7 children.

(a) (b)

4 7
Note that
every parent
12 14 15 18 node is
less than
its children.
12 20 25 45 20 25

(a) (b)

It should be a complete binary tree.

Heap

It should satisfy parental property.

 10 Level 0

Level 1
20 30 (20, 30)
Level 2
40 50 60 (40, 50, 60)
Level 3
70 (70)

10 Level 0

The maximum level

20 30 Level 1
in this tree is 3
hence height of this
tree is 3. 40 50 60 Level 2

70 Level 3

2i

i 0
At level 0  1 node (2 = 2 = 1)
i 1
At level 1  2 nodes (2 = 2 = 2)
i 2
At level 2  4 nodes (2 = 2 = 4)
10
i 3
At level 3  8 nodes (2 = 2 = 8)
 Total number of nodes in
20 30
h+1
complete binary tree are 2 –1.
Where, h is height of tree.
40 50 60 70 In the given tree height = 3
3+1 4
 2 –1 = 2 –1 = 16–1 = 15
80 90 91 92 93 94 95 96  Total 15 nodes in this complete
binary tree.
 10 10 10

20 30 20 30 20 30 Level 1

40 50 50 40

60 Level 3

Not almost
binary tree
Not almost nd
binary tree (because 2
property is not
st
(because 1 satisfied)
Almost complete property is not Note : Shaded nodes are
binary tree satisfied) leaf nodes
(a) (b) (c)
 10 20 20

8 10 8 10 8 10

7 6 3 4 7 6 6 3

is a heap is a heap Not a heap

20

10 8

3 4 6

20

10 8

3 4 6 7

Root node is stored at A [0].

Left child is at 2i + 1 position in array A.

For
array
A [size] Right child is at 2i + 2 position in array A.

Parent node is at i position in array A.

 0
20 Root is stored
at A [0].
0 1 2
20 20 10 8

0 1 2 3 4
10 8 Left child of
20 10 8 3 4
10 is at A[3]
Left
Right and right child of
3 4 6 7 10 is at A[4].
0 1 2 3 4 5 6
20 10 8 3 4 6 7

Left child
Right child

7 4

5 6 2 3

0 th
 9

Using formula
6 8 Left child = 2i +1
Right child = 2i + 2
Parent = i
2 5 7 we can draw a tree structure.

10 10 12 12

10 1
12 10

12 12 14

10 1 14 1 12 1

14 10 10

14 14 14

12 1 12 1 12 1

10 6 10 6 5 10 6 5 8
 14 4 4

12 1 12 1 15 1

10 6 5 8 15 6 5 8 12 6 5 8

15 10 10

15 15

4 1 12 1

12 6 5 8 4 6 5 8

10 10

15 15

12 1 12 1

10 6 5 8 10 6 5 8

4 4 3

15 15

12 1 12 1

10 6 5 8 10 9 5 8

4 3 9 4 3 6
 15 15

12 1 12 1

10 9 5 8 10 9 5 8

4 3 6 7 4 3 6 7 4

15 15

12 1 12 1

10 9 5 8 10 9 11 8

4 3 6 7 4 11 4 3 6 7 4 5

15 15

12 11 12 11

10 9 1 8 10 9 5 8

4 3 6 7 4 5 4 3 6 7 4 1

15 15

12 11 12 11

10 9 5 8 10 9 5 13

4 3 6 7 4 1 13 4 3 4 1 8
6 7
 15

12 13

10 9 5 11

4 3 6 7 4 1 8

15

12 13

10 9 5 11

4 3 6 7 4 1 2

15 15

12 13 12 13

10 9 5 11 10 9 5 20

4 3 6 7 4 1 21 20 4 3 6 7 4 1 2 11

15 20

12 20 12 15

10 9 5 13 10 9 5 13

4 3 6 7 4 1 2 11 4 3 6 7 4 1 2 11
 10
10
20

10 10
10
20 15 12 15
20 15
12 20

10 10

12 15 12 15

20 25 20 25 30

10 10

12 15 12 14

20 25 30 14 20 25 30 15
 10 10 10

12 14 12 14 2 14

20 25 30 15 2 25 12 25 30 15

2 20 20

10 14

12 25 30 15

20

2 2 2

10 14 10 14 5 14

12 25 30 15 5 25 30 15 10 25 30 15

20 5 20 12 20 12

2 2 2

5 14 5 14 4 14

10 25 30 15 10 4 30 15 10 5 30 15

20 12 4 20 12 25 20 12 25

This is required
min heap
 2 25
Swap

4 14 4 14

10 5 30 15 10 5 30 15

20 12 25 20 12 2 Delete it

25 4 4

This is final
4 14 25 14 5 14 min heap

10 5 30 15 10 5 30 15 10 25 30 15

20 12 20 12 20 12

10

10

12

1
10 1

12 10

12 1 12 10
14
 1 1 1 1

12 10 6 10 6 10 6 5

14 6 14 12 14 12 5 14 12 10

1 1 1

6 10 6 8 6 8

14 12 8 14 12 10 14 12 10 15

1 1

6 8 6 8

14 12 10 15 3 12 10 15

3 14

3 8

6 12 10 15

14

3 8

6 12 10 15

14 9
 1 1

3 8 3 8

6 12 10 15 6 7 10 15

14 9 7 14 9 12

1 1

3 8 3 8

6 7 10 15 6 4 10 15

14 9 12 4 14 9 12 7

3 8

6 4 10 15

14 9 12 7 11 13

This is Min Heap

1 Swap 13

3 8 3 8

6 4 10 15 6 4 10 15

14 9 12 7 11 13 14 9 12 7 11 1 Delete
it
 13 3

3 8 13 8

6 4 10 15 6 4 10 15

14 9 12 7 11 14 9 12 7 11

3 3

4 8 4 8

6 13 10 15 6 7 10 15

14 9 12 7 11 14 9 12 13 11

4 8

6 7 10 15

14 9 12 13 11 20

Final Heap

25 12
25

12 25
 12
12
25 27

25 27
30

12 12 5

25 27 5 27 12 27

30 5 30 25 30 25

5 5

12 27 12 10

30 25 10 30 25 27

12 10

30 25 27 17
 5 5

12 10 12 10

30 25 27 17 29 25 27 17

29 30

5
5

12 10 12 10

29 25 27 17 29 25 27 17

30 40 30 40 35

5 35
Swap

12 10 12 10

29 25 27 17 29 25 27 17

30 40 35 30 40 5 Delete 5
 35 10

12 10 12 35

29 25 27 17 29 25 27 17

30 40 30 40

10

12 17

29 25 27 35

30 40
 TM

TECHNICAL PUBLICATIONS - An up thrust for knowledge

 emp.dat

Rahul
Lekhana
Nandan
Archana
Yogesh

dept.dat
Accounts
Proof
Marketing
DTP
Graphics Design

memory block size of block

 File organization

Sequential Random access Index sequential Linked

organization or direct access file organization organization
This record structure is for the sequential file
For example
name emp_id salary
AAA 10 1000
BBB 20 2000
CCC 30 3000
User must enter the desired data in the
members of the structure Records
New values for the
updation of record
It's a logical deletion
 Random Access
Organization

Direct Addressing Directory Lookup Hashing

Calling Hash function to get the direct
location for the record in the file. Function
returns a hash key in variable h

Using h for getting actual

position in the file. Hence
offset is calculated
 Position Emp_ ID Name Salary

Emp_ ID Position 0

1 20 BBB 2000
10 5
2

3 40 DDD 4000
20 1
4

30 7 5 10 AAA 1000

6
40 3 7 30 CCC 3000

8
IND.DAT
9

10

EMP.DAT
 10 AAA 217

20 BBB 101

30 CCC 117

40 DDD 301

50 EEE 313

60 EEE 410

70 FFF 570

AAA AAA 217

BBB BBB 101

CCC BBB 117

Cluster
DDD BBB 120

EEE BBB 127

FFF CCC 117

CCC 119 Cluster

CCC 121

DDD 301

EEE 313

EEE 410

FFF 570
AAA 10 AAA

BBB 11 AAA

CCC 12 AAA

DDD 20 BBB

EEE 21 BBB

FFF 30 CCC

40 DDD

41 DDD

42 DDD

43 DDD

50 EEE

This record structure is for the sequential file

For example
name emp_id salary
AAA 10 1000
BBB 20 2000
CCC 30 3000

This record structure is for the index file

For example -
emp_id salary
10 0
20 1
30 2
 Opening both the
files for reading and
writing purpose

User must enter some records to

store them first in the sequential file.

Records for index file

are created from seq.file
and writing them to ind.file
This while loop will read the
record from index file and using
the index position the record
from sequential file is retrieved.
Marking this record as deleted in index
file b'coz this is the desired record
which we wish to delete from seq. file
Current position/size of
individual record = position
of record in ind. file
500 2 BBB EEE NULL

700 2 DDD AAA NULL

900 1
CCC NULL

Linked organization

Multilist Coral Inverted Cellular

files rings files partitions
Value Fifth Tenth Value Female Male

Length 2 3 Length 3 2

Pointer Pointer
to first BBB EEE to first BBB EEE
record record

Value First class Second class Pass class

Length 1 3 1

Pointer
to first EEE AAA BBB
record
 Rolll_no Index

Value 500 700 900

Length 2 2 1
Pointer
to first
record

Roll_no
NULL NULL NULL
link

Class CCC NULL NULL

Sex DDD AAA CCC NULL NULL

Marks NULL NULL CCC DDD NULL

BBB EEE DDD AAA CCC

 U V W X A _Link [i]
head
Fifth_std

head

The forward circular list contains nodes head U, V, W, X.

The reverse circular list contains nodes head W, V, U.

 Fifth BBB, CCC
437 BBB
EEE, DDD,
Tenth
488 EEE AAA

Fig. 6.7.6 (b) Class index

689 DDD

695 AAA
Female BBB, DDD, CCC
778 CCC Male EEE, AAA

First class EEE

Second class AAA, DDD, CCC

Pass class BBB

 10,000 records
i.e. 100 blocks

500 records
Output i.e. 5 blocks Disk
can be sorted

Main memory
F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20

G1 G2 G3 G4 G5 G6 G7 G8 G9 G10

H1 H2 H3 H4 H5

I1 I2 I3

J1 J2

Sorted
K1 record
 Tape 1
Input 1 Tape
Output
Tape 2
Input 2

Disk Disk
Main memory
(2 - way merge)


 


1 st 

1
  ( N M) runs
2

1 st
1 1
   ( N M) runs
2 2
 2 nd
1 1
   ( N M) runs
4 2

S
 2S M  ( 1 2 ) ( 1 2) ( N M) runs

2S M

2S

O(N log (N M))

Tape 1

Tape 2 Output

Output

Tape k
Disk
Disk

Main memory
(k - way merge)
 


 4

Min
element 4 12
out of
child nodes

15 4 12

8 12

15 8 12

9 12

15 9 12

12

15 12

15 20 12
 4

4 11

8 11

9 11
log k ( N M)
 n2
n2 n2
Reaching to level 0 and next
reference is set to right node
n2
 0

1 2 3

4
 1
0

4 3
 V1 V2
1
Mumbai Pune

2
2
3
Delhi Kolkata
3
V4 V3
 2

if

1
3
do int

4
while
 A tree can be

14

12 9

8 7 10 18

Heapified Tree is

18

12 14

8 7 10 9
 2
V1 V2

4 1 3 10

2 7
V3 V4 V5

8 4
5 6
V6 1 V7
 2
B C
10

A 1 4 7 9
8
3
E D
2