Data Structure And Algorithms for Computer Science

This presentation deals with data and their structures and the algorithms required to process them.

1. UNIT –3 BINARYTREES
1

2. SYLLABUS
Terminologies,
RepresentationofbinaryTrees:UsingArraysandlinkedlists,
BinaryTreeTraversals:RecursiveandNon-Recursive
techniques,
ThreadedBinarytrees,
Binarysearchtreeoperations:Traversal,Searching,Inserting
andDeletingelements;
AVLsearchtreeoperations:InsertionandDeletion,
m-waysearchtree,SearchingInsertionandDeletioninanm-
waysearchtree,
B-treeSearching,InsertionandDeletioninaB-tree,
HeapSort.
2

3. Definition of Tree
•Atreeisafinitesetofoneormorenodes
suchthat:
•Thereisaspeciallydesignatednodecalled
theroot.
•Theremainingnodesarepartitionedinton>=0disjoint
setsT1,...,Tn,whereeachofthesesetsisatree.
•WecallT1,...,Tnthesubtreesoftheroot.
3

4. TREE–TERMINOLOGY
Root:Thebasicnodeofallnodesinthetree.
Child:asuccessornodeconnectedtoanodeiscalledchild.(B
andCarechildnodestothenodeA,LikethatDandEarechild
nodestothenodeB.)
Parent:anodeissaidtobeparentnodetoallitschildnodes.(A
isparentnodetoB,CandBisparentnodetothenodesDandF).
Leaf:anodethathasnochildnodes.(D,EandFareLeafnodes
)
Siblings:Twonodesaresiblingsiftheyarechildrentothesame
parentnode.
Ancestor:anodewhichisparentofparentnode(Aisancestor
nodetoD,EandF).
Descendent:anodewhichischildofchildnode(D,EandFare
descendentnodesofnodeA)
Degree:Thenumberofsubtreeofanode.Abinarytreeisdegree
2.
4

5. TREE–TERMINOLOGY
Level:Thedistanceofanodefromtherootnode,
Therootisatlevel–0,(BandCareatLevel1andD,
E,FhaveLevel2.
Depthorheight:ofatreeisthemaximumnumber
ofnodesinabranchofT.thisturnsouttobe1more
thanthelargestlevelnumberofT.
Edge:ThelinedrawnfromanodeNofTtoa
successoriscalledanedge.
Path:Asequenceofconsecutiveedgesiscalled
path.
Aforestisadisjointunionoftrees.
5

6. 6

7. EXAMPLE
7

8. BINARYTREE
Abinarytreeisafinitesetofelementsthatiseitheremptyoris
partitionedintothreedisjointsubsets.
-Thefirstsubsetcontainsasingleelementcalledtherootofthe
tree.
-Theothertwosubsetsarethemselvesbinarytrees,calledtheleft
andrightsubtreesoftheoriginaltree.Aleftorrightsubtreecanbe
empty.Eachelementofatreeiscalledanodeofthetree.
B
G
E
D
IH
F
c
A Binary tree
8

9. STRUCTURESTHATARENOTBINARYTREES
9

10. TYPESOFBINARYTREE
1.Strictly binary trees
2.Complete binary tree
3.Extended binary tree
10

11. STRICTLYBINARYTREES
•Ifeverynon-leafnodeinabinarytreemusthavetwosubtree
leftandrightsub-trees,thetreeiscalledastrictlybinarytree.
•Astrictlybinarytreewithnleavesalwayscontains2n-1
nodes.
•Here, B,E,F,G are leaf nodes. So n=4, No. of nodes=2*4-1=7
B
D
G
F
E
C
A
11

12. COMPLETEBINARYTREE
Thetreeissaidtobecompletebinarytreeifallitslevels,except
possiblythelast,havethemaximumnumberofpossiblenodes
andifallthenodesatlastlevelappearasfarleftaspossible.
Maximumnumberofnodesatanylevelr=2
r
Eq:-atlevel0maximumnumberofnodes=2º=1
Atlevel2maximumnumberofnodes=2²=4andsoon.
.
12

13. COMPLETEBINARYTREE
Supposegivenacompletebinarytreehaving26nodes.Wearelabelingthe
nodesfrom1to26.
Leftchildofnodek=2*K
Rightchildofnodek=2*K+1
ParentofnodeK=[K/2]
DepthofcompletebinarytreeT
nwithnnode
D
n=[log
2n+1]
13

14. FULLBINARYTREEVSCOMPLETEBINARY
TREE
14

15. FULLVS. COMPLETEBINARYTREE
15

16. EXTENDEDBINARYTREE
•Anextendedbinarytreeisatransformationofanybinarytree
intoacompletebinarytree.Thistransformationconsistsof
replacingeverynullsubtreeoftheoriginaltreewith‘special
nodes.'
•Thenodesfromtheoriginaltreearetheninternalnodes,while
the``specialnodes''areexternalnodes.
•Forinstance,considerthefollowingbinarytreeinfig(a).Fig
(b)istheextendedbinarytree.
•Emptycirclesrepresentinternalnodes,andfilledcircles
representexternalnodes.Everyinternalnodeintheextended
treehasexactlytwochildren,andeveryexternalnodeisaleaf.
Theresultisacompletebinarytree.
16

17. EXAMPLE
a
b
17

18. REPRESENTATIONOFBINARYTREESINMEMORY
.
ArrayRepresentation
LinkedRepresentation
18

19. ARRAYREPRESENTATION
.
•TreeNodesarestoredinthearray.
•Rootnodeisstoredatindex‘0’
•Ifanodeisatalocation‘i’,thenits
leftchildislocatedat2*i+1
rightchildislocatedat2*i+2
•Thisstorageisefficientwhenitisacompletebinarytree,
becausealotofmemoryiswasted.
19

20. EXAMPLE1
20

21. EXAMPLE2
Disadvantages
(1) waste space
(2) insertion/deletion
problem
21

22. LINKEDREPRESENTATION
•Ifabinarytreeisnotcomplete,abetterchoiceforstoring
itistousealinkedrepresentation.
•ItusesthreearrayINFO,RIGHT,LEFT,andapointer
variableROOTasfollows.
•Firstofall,eachnodeNoftreeTwillcorrespondtoa
locationKsuchthat:
•INFO[K]containsthedataatnodeN.
•RIGHT[K]containsthelocationoftherightchildofnode
N.
•LEFT[K]containsthelocationoftheleftchildofnodeN.
•ROOTwillcontainthelocationoftherootRofT.
22

23. Linked Representation
struct node {
int info;
struct node *left;
struct node *right;
};
infoleft right
info
left right
23

24. LINKEDREPRESENTATION
ROOT
A
B x C x
x D x E x
x F x
24

25. LINKEDREPRESENTATION
1
2
3
4
5
6
7
8
9
10
B
C
D
E
A 3
6
8 9
X
X
X
7
X
X
1ROOT
F
4
5
X X
2AVAIL
25

26. TRAVERSINGABINARYTREE
Three methods:
1. inorder
2. preorder
3. postorder
Preorder
1. Visit the root
2. Traverse the left subtree in preorder
3. Traverse the right subtree in preorder
Root-left-right93
4
14
18
15
20
7
16
17
5
Postorder
1. Traverse the left subtree in postorder
2. Traverse the right subtree in postorder
3. Visit the root
Left-right-root
Inorder
1. Traverse the left subtree in inorder
2. Visit the root
3. Traverse the right subtree in inorder
Left-root-right
26

27. 27

28. TRAVERSINGABINARYTREE
Preorder
1. Visit the root
2. Traverse the left subtree in preorder
3. Traverse the right subtree in preorder
preorder: ABDGCEHIF
Postorder
1. Traverse the left subtree in postorder
2. Traverse the right subtree in postorder
3. Visit the root
postorder: GDBHIEFCA
D
B
A
F
C
E
G
IH
Inorder
1. Traverse the left subtree in inorder
2. Visit the root
3. Traverse the right subtree in inorder
inorder: DGBAHEICF
28

29. TRAVERSINGABINARYTREE
Preorder
1. Visit the root
2. Traverse the left subtree in preorder
3. Traverse the right subtree in preorder
preorder: ABCEIFJDGHKL
Inorder
1. Traverse the left subtree in inorder
2. Visit the root
3. Traverse the right subtree in inorder
inorder: EICFJBGDKHLA
Postorder
1. Traverse the left subtree in postorder
2. Traverse the right subtree in postorder
3. Visit the root
postorder: IEJFCGKLHDBA
C
B
A
L
H
D
K
G
E
I
F
J
29

30. APPLY EACH TRAVERSAL IN BINARY
TREE
30
PREORDER: ABDCEFG
INORDER: BDAECGF
POSTORDER: DBEGFCA

31. TRAVERSING
There are two solution for traversing
•Recursive
•Non-recursive
31

32. RECURSIVETRAVERSALOFBINARYTREE
32

33. INORDER
inorder (node *root)
{
if (root != NULL)
{
inorder (left[root]);
print (info[root]);
inorder (right[root]);
}
}
33

34. PREORDER
preorder (node *root)
{
if (root != NULL)
{
print (info[root]);
preorder (left[root]);
preorder (right[root]);
}
}
34

35. POSTORDER
postorder (node *root)
{
if (root != NULL)
{
postorder (left[root]);
postorder (right[root]);
print (info[root]);
}
}
35

36. NON-RECURSIVETRAVERSALOFBINARY
TREE
36

37. INORDERTRAVERSAL
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and
set current =current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
37

38. Innonrecursivetraversing,stackisusedtostorethenodeswhichhasto
bevisitedlater.
1.SetTop:=0
2.P=Root.
3.Repeatstep4to10while(P≠NULL)
4.RepeatSteps5to6while(P≠NULL)
5.Push(Stack,P)
6.P=Left[P]
[EndofStep4whileloop.]
7. IF(Stack is non empty)
8. P=Pop(Stack)
9. Print P
10. P=Right[P]
[End of If structure.]
[End of Step 3 while loop.]
11.Stop
INORDERTRAVERSAL
struct node {
int info;
struct node *left;
struct node *right;
};
38

39. EXAMPLE
39

40. PREORDERTRAVERSAL
1.P=Root.
2.Push(Stack,P)
3.Repeatstep4to9while(stackisnonempty)
4.P=Pop(Stack)
5.If(Right[P]!=Null)
6.Push(Stack,Right[P])
7.If(Left[P]!=Null)
8. Push(Stack, Left[P])
9. Print Info[P]
[End of Step 3 while loop.]
10.Stop
struct node {
int info;
struct node *left;
struct node *right;
};
40

41. EXAMPLE
41

42. POSTORDERTRAVERSAL
1.P=Root.
2.Push(Stack,Root)
3.Repeatstep4to13while(stackisnonempty)
4.P=Stack[Top]
5.If(Left[P]!=Null&&Visited[Left[P]]==FALSE)
6.Push(Stack,Left[P])
7.Else
8.If(Right[P]!=Null&&Visited[Right[P]]==FALSE)
9.Push(Stack,Right[P])
10.Else
11.Pop(Stack)
12. Print Info[P]
13.visited[P]=TRUE
[End of if]
[End of while]
14.Stop
#define BOOL int
struct node {
int info;
struct node *left;
struct node *right;
BOOL visited;
};
42

43. EXAMPLE
43

44. CREATIONOFBINARYTREEFROMPREORDER
ANDINORDERTRAVERSALS
Step1:Scanthepreordertraversalfromlefttoright.
Step2:Foreachnodescannedlocateitspositionin
inordertraversal.Letthescannednodex.
Step3:Thenodexprecedingxininorderfromitsleft
subtreeandnodessucceedingitfromrightsubtree.
Step4:Repeatstep1foreachsymbolinthe
preorder.
44

45. CONSTRUCTTREEFROMGIVENINORDERAND
PREORDERTRAVERSALS
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
Solution:InaPreordersequence,leftmostelementis
therootofthetree.Soweknow‘A’isrootforgiven
sequences.Bysearching‘A’inInordersequence,
wecanfindoutallelementsonleftsideof‘A’arein
leftsubtreeandelementsonrightareinright
subtree.Soweknowbelowstructurenow.
45

46. Werecursivelyfollowabovestepsandgetthe
followingtree.
46

47. Inorder sequence: CAFDGHB
Preorder sequence: DACFBGH
CONSTRUCTTREEFROMGIVENINORDERAND
PREORDERTRAVERSALS
47

48. A
B
C
F
G
H
SOLUTION
D
48

49. CONSTRUCTTHETREEFROMITSGIVEN
PREORDERANDPOSTORDER
Constructthetreefromitsgivenpreorderand
postordertraversal.Explainthestepsinvolved.
Preorder:ABDGHKCEF
Postorder:GKHDBEFCA
49

50. SOLUTION
Thenodeappearinthefirstpositionpreorderis
alwaystheroot.Sohere,‘A’istheroot.
A
Now,takeone-onenodefrompreorderandobserve
itspositioninpostorder.LikehereBisnextin
preorder.BisbeforeAinpostorder,soitchildofA.
A
B
50

51. Next node in preorder is D. D is before B in postorder.
Next node in preorder is G. G is before D in postorder.
51

52. Next node in preorder is H. H is before D in postorder.
But D is already having a left child. H will become right
child of D.
H
•Next node in preorder is K. K is before H in postorder.
52

53. NextnodeinpreorderisC.CisbeforeAin
postorder.ButAisalreadyhavingaleftchild.Cwill
becomerightchildofA.
53

54. NextnodeinpreorderisE.EisbeforeFin
postorder.EFisbeforeCinpostorder.
FE
54

55. HEADERNODES
SupposeabinarytreeTismaintainedinmemorybymeansofa
linkedrepresentation.Sometimesanextra,specialnode,calleda
headernode,isaddedtothebeginningofT.
Whenthisextranodeisused,thetreepointervariable,whichwecall
HEAD,willpointtotheheadernode,andtheleftpointerofthe
headernodewillpointtotherootofT.
55

56. Threaded Binary Trees
•Too many null pointers in current representation of binary trees
n: number of nodes
number of non-null links: n-1
total links: 2n
null links: 2n-(n-1)=n+1
•Thisspacemaybemoreefficientlyusedbyreplacingthenull
entriesbysomeothertypeofinformation.
•Wewillreplacenullentriesbyspecialpointerswhichpointto
nodeshigherinthetree.
•Thesespecialpointersarecalled“threads”,andbinarytrees
withsuchpointersarecalledthreadedtree.
•Thethreadsinabinarytreeareusuallyindicatedbydottedlines.
56

57. THREADEDBINARYTREES
Tree can be threaded using
•One way threading:
i.Right-in–threaded:athreadwillappearinthe
RIGHTNullfieldofeachnodeandwillpointto
thesuccessorofthatnodeunderinordertraversal.
ii.Left-in-threaded:athreadwillappearintheLEFT
Nullfieldofeachnodeandwillpointtothe
predecessorofthatnodeunderinordertraversal.
•Twowaythreading(fullythreadedtree):bothleftand
rightNullpointerscanbeusedtopointtopredecessor
andsuccessorofthatnodeunderinordertraversal.
57

58. RIGHT-IN–THREADED
Inorder:FBHGADCE
58

59. LEFT-IN-THREADED
Inorder:FBHGADCE
59

60. FULLYTHREADEDTREE
60

61. BINARYSEARCHTREES(BST)
AbinarysearchtreeTisabinarytreewhichis
eitheremptyoreachnodeofthetreecontainsa
keythatsatisfiesthefollowingconditions:
i.Allkeysintheleftoftherootarelessthanthekeyin
theroot.
ii.Allkeysintherightoftherootaregreaterthanthe
keyintheroot.
iii.Theleftandrightsubtreeoftherootarealsobinary
searchtrees.
61

62. EXAMPLE
62

63. EXAMPLES
20 35 48 8578
50
534512
7530
80
2012
155
10
63

64. ADVANTAGES& DISADVANTAGES OFBINARYSEARCHTREE
Advantages
i.Storeskeysinthenodesinawaythatsearching,insertionand
deletioncanbedoneefficiently.
ii.SimpleImplementation
iii.Nodesintreearedynamic
Disadvantages
i.Theshapeofthetreedependsontheorderofinsertions,anditcan
bedegenerated.
ii.Wheninsertingorsearchingforanelement,thekeyofeachvisited
nodehastobecomparedwiththekeyoftheelementtobe
inserted/found.
iii.Keysinthetreemaybelongandtheruntimemayincrease.
64

65. OPERATIONSON BINARYSEARCHTREE
•Traverse
•Searching
•Inserting
•Deleting
65

66. TRAVERSE
Theinorder,preorderandpostorderalgorithmswill
remainsameasbinarytree.WhenaBSTis
traversedininorder,theelementsareprintedin
ascendingorder.
Example:inorder:5,10,12,15,20
66

67. SEARCHING
ThesearchwillstartfromtherootX.
Kisthekeyvaluewhichwearesearchinginthe
tree.
TREE_SEARCH(X,K)
1.If(X==NULL)orK=Info[X]
returnX
2.IfK<Info[X]
returnTREE_SEARCH(Left[X],K)
3.Else
returnTREE_SEARCH(Right[X],K)
67

68. 68

69. INSERTION
Theoperationsofinsertionanddeletionchangethe
dynamicsetrepresentedbyabinarysearchtree.
BeforethenodecanbeinsertedintoaBST,the
positionofthenewnodemustbedetermined.
Theinsertoperationwillinsertanodetoatreeand
thenewnodewillbecomeleafnode.
Thisistoensurethataftertheinsertion,theBST
characteristicsisstillmaintained.
69

70. Insertion(T, Z) //TBinary Search Tree, Znew node
1. y=NULL
2. x=root
3. While x ≠ NULL
4. do y=x
5. If info[z] < info[x]
6. then x=left[x]
7. Else x=right[x]
[End while]
8. parent[z]=y
9. If y==NULL //tree was empty
10. then root=z
11. Else if info[z] < info[y]
12. then left[y]=z
13. Else right[y]=z
14. Stop 70

71. CONSTRUCT A BINARY SEARCH TREE
71

72. CONSTRUCTBINARYSEARCHTREE
Howcanyouconstructbinarysearchtreewiththe
followingelementsequence.
40,60,50,33,55,11
72
60
33
11 50
55
40

73. CONSTRUCTBINARYSEARCHTREE
Howcanyouconstructbinarysearchtreewiththe
followingelementsequence.
44,22,77,33,55,99,88
73
77
22
33 55
99
44
88

74. DELETION
Whenanodeisdeleted,thechildrenofthe
deletednodemustbetakencareoftoensurethat
thepropertyofthesearchtreeismaintained.
Thereare3possiblecasestodeleteanodeina
tree:
Case1:Deletealeaf
Case2:Deleteanodewithonechild
a)Deleteanodewithleftchild
b)Deleteanodewithrightchild
Case3:Deleteanodethathastwochildren 74

75. Delete(T,x)//deleteanodewithinfoxfromatreeT.
Firstsearchanodewithinfox.letthereisnodepwith
infoxandqbeitsparent.Ifnosuchpexiststhere,
xisnotpresentsonodeletionispossible.
Case1:Letpbealeafnode
If(q==null)androot=pthensetroot=null
Else
if(left[q]==p)thenleft[q]=null
elseright[q]=null
75

76. Case2(a):letphaveonlyleftchild
If(q==null)thenroot=left[p]
Else
If(left[q]==p)thenleft[q]=left[p]
elseright[q]=left[p]
76

77. EXAMPLE
77

78. Case2(b):letphaveonlyrightchild
If(q==null)thenroot=right[p]
else
If(left[q]==p)thenleft[q]=right[p]
elseright[q]=right[p]
78

79. Case 3:p has both left and right child,
replace the node's value with the min value in the
right subtree
delete the min node in the right subtree
79

80. BALANCEFACTOR(BF)
Foreachnodethebalancedfactor(bf)isdefinedas
bf(N)=heightofleftsubtreeofN–heightofrightsubtreeofN
80

81. AVL (HEIGHT-BALANCEDTREES)
Itisnamedaftertheirinventors,Adelson,Velskiiand
Landis.
AnAVLtreeisabinarysearchtreewhichhasthe
followingproperties:
Theheightoftheleftandrightsubtreesoftheroot
differsbyatmost1
TheleftandrightsubtreesoftherootareagainAVL
trees
Nodebalancefactorof+1ifnodeleftsubtreeishigh,
0ifnodebothsubtreeareatequalhightand-1isnode
rightsubtreeishigh.
81

82. PERFECTLYBALANCEDBINARYTREE
82

83. AVL TREES
83

84. NON-AVL TREES
84

85. INSERTIONALGORITHM
Insert(T,x)
Step1:InsertxintoTusingBSTinsertionalgorithm.
Step2:Recalculatethebalancefactorforeachnode.
Step3:Backtracktowardsrootfollowingthepathof
insertion.Stopatfirstnodewhichdoesnothavea
balancefactorbelongingto(0,1,-1).Ifnosuchnode
isfound,stopandinsertionisover.Ifonesuch
nodeisfound,thengoforrotation.
85

86. SINGLE& DOUBLEROTATIONS
Single
LL and RR
Double
LR:LR is RR followed by LL
RL:RL is LL followed by RR
86

87. AVLROTATION
Inordertobalanceatree,therearefourtypesof
rotations
LLRotation:insertednodeisaddedtotheleft
subtreeoftheleftchildoftheunbalancednode.
RRRotation:insertednodeisaddedtotheright
subtreeoftherightchildoftheunbalancednode.
LRRotation:insertednodeisaddedtotheright
subtreeoftheleftchildoftheunbalancednode.
RLRotation:insertednodeisaddedtotheleft
subtreeoftherightchildoftheunbalancednode.
87

88. LLROTATION
88

89. LL ROTATIONEXAMPLE
89
Insert node 10 in this tree

90. RRROTATION
90

91. RRROTATIONEXAMPLE
91

92. LRROTATION
92

93. LRROTATIONEXAMPLE
93

94. RLROTATION
94

95. RLROTATIONEXAMPLE
95

96. CONSTRUCTAVLTREE
96
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

97. AVL TREEROTATIONS
97
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

98. AVL TREEROTATIONS
98
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

99. AVL TREEROTATIONS
99
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

100. AVL TREEROTATIONS
100
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

101. AVL TREEROTATIONS
101
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

102. AVL TREEROTATIONS
102
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

103. AVL TREEROTATIONS
103
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

104. AVL TREEROTATIONS
104
Insert the following nodes in an AVL tree:
40, 30,20, 60,50, 80,15,28,25

105. DELETIONINANAVL TREES
Thesequenceofstepstobefollowedindeletinganode
fromanAVLtreeisasfollows:
1.Initially,theAVLtreeissearchedtofindthenodetobe
deleted.
2.TheprocedureusedtodeleteanodeinanAVLtreeis
thesameasdeletingthenodeintheBST.
3.Afterdeletionofthenode,checkthebalancefactorof
eachnode.
4.RebalancetheAVLtreeifthetreeisunbalanced.For
this,AVLrotationsareused.
105

106. OndeletionofanodeXfromtheAVLtree,letAbethe
closestancestornodeonthepathfromXtotheroot
node,withabalancefactorof+2or-2.Torestore
balancetherotationisfirstclassifiedasLorRdepending
onwhetherthedeletionoccurredontheleftorright
subtreeofA.
BistherootoftheleftorrightsubtreeofA.Now
dependinguponthevalueofbalancefactorofB,theR
orLrotationisfurtherclassifiedasR0,R1andR-1or
L0,L1,L-1.
106

107. TYPESOFROTATION
R0 (LL) L0 (RR)
R1 (LL) L1 (RR)
R-1(LR) L-1(RL)
107

108. R0 ROTATION
108
WhenbalancefactorofBis0andBistherootofleft
subtreeofA.R0rotationisused.(R0rotationaresimilar
toLL).

109. 109
R0 rotation

110. EXAMPLER0 ROTATION
110

111. R1 ROTATION
111
WhenbalancefactorofBis1andBistherootofleft
subtreeofA.R1rotationisused.(R1rotationare
similartoLL).

112. EXAMPLER1 ROTATION
112

113. R(-1) ROTATION
113
WhenbalancefactorofBis-1andBistherootofleftsubtree
ofA.R(-1)rotationisused.(R(-1)rotationaresimilarto
LR).

114. EXAMPLEL0 ROTATION
114
WhenbalancefactorofBis0andBistherootofrightsubtree
ofA.L0rotationisused.(L0rotationaresimilartoRR).

115. L1 ROTATION
115
WhenbalancefactorofBis1andBistherootofright
subtreeofA.L1rotationisused.(L1rotationare
similartoRR).

116. 116
Insertthefollowingkeysinordershowntoconstructan
AVLtree10,20,30,40,50.deletethelasttwokeysinthe
orderofLIFO.

117. 117

118. 118
Advantages
1.Search is O(log N) since AVL trees are always balanced.
2.Insertion and deletions are also O(logn)
3.The height balancing adds no more than a constant factor to the speed of
insertion.
Disadvantages
1.Difficult to program & debug; more space for balance factor.
2.Asymptotically faster but rebalancing costs time.
3.Most large searches are done in database systems on disk and use other
structures (e.g. B-trees).
Pros and Cons of AVL Trees

119. M-way search tree
Searching , Insertion and Deletion
119

120. DEFINITION
Amulti-waytreeoforderm(oranm-waytree)isatreeTin
which
i.Eachnodesholdbetween1tom-1distinctkeysandeach
nodehas,atmostmchildnodes.
ii.Inanode,valuesarestoredinascendingorder:K
1<K
2<
...<K
m-1
iii.Thesubtreesareplacedbetweenadjacentvalues:each
valuehasaleftandrightsubtree.
k
irightsubtree=k
i+1leftsubtree.
Allthevaluesink
ileftsubtreeare<k
i
Allthevaluesink
irightsubtreeare>k
i
iv.EachofthesubtreeA
i,1≤i≤marealsom-waysearchtrees.
120

121. 5-WAYSEARCHTREE
121

122. ALGORITHMFORSEARCHINGFORA
VALUEINANM-WAYSEARCHTREE
1.IfX<K
1,recursivelysearchforXinK
1'sleft
subtree.
2.IfX>K
m-1,recursivelysearchforXinK
m-1'sright
subtree.
3.IfX=K
i,forsomei,thenwearedone(Xhas
beenfound).
4.Theonlyremainingpossibilityisthat,forsomei,
K
i<X<K
i+1.InthiscaserecursivelysearchforX
inthesubtreethatisinbetweenK
iandK
i+1
122

123. INSERTIONINANM-WAYSEARCHTREE
Toinsertanewelementintoanm-waysearchtree
weproceedinthesamewayasonewouldinorder
tosearchfortheelement.
Toinsert6intothe5-waysearchtree,weproceed
tosearchfor6andfindthatwefalloffthetreeat
thenode[7,12]withthefirstchildnodeshowinga
nullpointer.
Sincethenodehasonlytwokeysanda5-key
searchtreecanaccommodateupto4keysina
node,6isinsertedintothenodeas[6,7,12].
Buttoinsert146,thenode[148,151,172,186]is
alreadyfull,henceweopenanewchildnodeand
insert146intoit.
123

124. INSERTIONINAN5-WAYSEARCHTREE
124

125. DELETIONINANM-WAYSEARCHTREE
LetKbeakeytobedeletedfromthem-waysearch
tree.Todeletethekeyweproceedasonewouldto
searchforthekey.
Letthenodeaccommodatingthekeyasshowninfigure
125

126. DELETIONINANM-WAYSEARCHTREE
Therearefourcase
Case1:if(A
i=A
j=NULL)thendeleteK.
Case2:if(A
i≠NULL,A
j=NULL)thenchoosethelargestofthekey
elementK’inthechildnodepointedtobyA
i,deletethekeyK’and
replaceKbyK’.ObviouslydeletionofK’maycallforsubsequent
replacementsandthereforedeletionsinasimilarmanner,toenable
thekeyK’moveupthetree.
Case3:if(A
i=NULL,A
j≠NULL)thenchoosethesmallestofthe
keyelementK’’inthechildnodepointedtobyA
j,deletethekeyK’’
andreplaceKbyK’’.AgaindeletionofK’’maytriggersubsequent
replacementsanddeletionstoenableK’’moveupthetree.
Case4:if(A
i≠NULL,A
j≠NULL)thenchooseeitherthelargestof
thekeyelementK’inthechildnodepointedtobyA
i,orthesmallest
ofthekeyelementsK’’fromthesubtreepointedtobyA
j,to
replaceK.TomoveK’orK’’upthetreeitmaycallforsubsequent
replacementsanddeletions. 126

127. CASE1
Todelete151,wesearchfor151andobservethatintheleafnode
[148,151,172,186]whereitispresent,bothitsleftsubtreepointer
andrightsubtreepointeraresuchthat((A
i=A
j=NULL).
Wethereforesimplydelete151andthenodebecomes[148,172,
186].Deletionof92alsofollowsthesameprocess.
127

128. CASE2
To delete 12 (in the figure of slide 120), we find the
node [7,12] accommodates 12 and key satisfies (A
i≠
NULL, A
j = NULL). Hence we choose the largest of the
keys from the node pointed to by A
i10 and replace 12 with
10.
128

129. CASE3
Todelete262(inthefigureofslide120,wefinditsleftandright
subtreepointersA
iandA
jrespectively,aresuchthat(A
i=NULL,
A
j≠NULL).
Hencewechoosethesmallestelement272fromthechildnode[272,
286,300],delete272andreplace262with272.todelete272the
deletionprocedureneedstobeobservedagain.
129

130. CASE4
Todelete198(inthefigureofslide120,wefinditsleftandright
subtreepointersA
iandA
jrespectively,aresuchthat(A
i≠NULL,
A
j≠NULL).
Hencewechoosethelargestelement141fromthechildnode[80,
92,198],delete141andreplace198with141.inplaceof141,148
willcome.
130

131. B TREE
131

132. INTRODUCTION
M-waysearchtreeshavetheadvantagesof
minimizingfileaccessesduetotheirrestricted
height.
Howeveritisessentialthattheheightofthetreebe
keptaslowaspossibleandthereforetherearises
theneedtomaintainbalancedm-waysearchtrees.
Suchabalancedm-waysearchtreeiswhatis
definedasaB-tree.
132

133. DEFINITIONOFAB-TREE
AB-treeofordermisanm-waysearchtreeinwhich:
1.theroothasatleasttwochildnodesandatmostm
childnodes.
2.allinternal(non-leaf)nodesexcepttheroothaveat
leastm/2(ceil)childnodesandatmostmchild
nodes.
3.thenumberofkeysineachinternal(non-leaf)nodeis
onelessthanthenumberofitschildandthesekeys
partitionthekeysinthesubtreeofthenodeina
mannersimilartothatofm-waysearchtrees.
4.allleafnodesareonthesamelevel.
133

134. B-TREEOFORDER5
134

135. SEARCHINGINAB-TREE
Searching for a key in a B-tree is similar to one an
m-way search tree. The number of accesses
depends on the height h of the B-tree.
135

136. INSERTINGINTOAB-TREE
TheinsertionofakeyinaB-treeproceedsasifonewere
searchingforthekeyinthetree.Thenthekeyisinserted
accordingtothefollowingprocedure:
Case1:iftheleafnodeinwhichthekeyistobeinsertedis
notfull,thentheinsertionisdoneinthenode.Anodeis
saidtobefullifitcontainsamaximumof(m-1)keys,
giventheorderoftheB-treetobem.
Case2:ifthenodeweretobefull,theninsertthekeyin
orderintotheexistingsetofkeysinthenode,splitthe
nodeatitsmedianintotwonodesatthesamelevel,
pushingthemedianelementintheparentnodeifitisnot
full.
136

137. INSERTIONINTOAB-TREE
137
Consider the B-tree of order 5 shown below. Insert the elements 4,5, 58, 6 in
The order given.

138. AFTERINSERTION
138

139. 139
Suppose we start with an empty B-tree and keys arrive in the
following order:1 12 8 2 25 6 14 28 17 7 52 16 48 68
3 26 29 53 55 45
We want to construct a B-tree of order 5
The first four items go into the root:
To put the fifth item in the root would violate condition
Therefore, when 25 arrives, pick the middle key to make a new
root
CONSTRUCTINGAB-TREE
12812

140. 140
CONSTRUCTINGAB-TREE(CONTD.)
12
8
1225
6, 14, 28 get added to the leaf nodes:
12
8
12146 2528

141. 141
CONSTRUCTINGAB-TREE(CONTD.)
Adding 17 to the right leaf node would over-fill it, so we take the
middle key, promote it (to the root) and split the leaf
817
1214 2528126
7, 52, 16, 48 get added to the leaf nodes
817
1214 2528126 16 48527

142. 142
CONSTRUCTINGAB-TREE(CONTD.)
Adding 68 causes us to split the right most leaf, promoting 48 to the
root, and adding 3 causes us to split the left most leaf, promoting 3
to the root; 26, 29, 53, 55 then go into the leaves
381748
525355682526282912 67 121416
Adding 45 causes a split of25262829
and promoting 28 to the root then causes the root to split

143. 143
CONSTRUCTINGAB-TREE(CONTD.)
17
38 2848
12 67 121416 525355682526 2945

144. 144
Suppose we start with an empty B-tree and keys arrive in the
following order: 10 20 50 60 40 80 100 70 130 90 30 120 140
25 35 160 180
We want to construct a B-tree of order 5
CONSTRUCTINGAB-TREE
70
25 40 100140
2010 3035 5060 8090120130 160180

145. 145
DELETIONFROMAB-TREE
1.Ifthekeyisalreadyinaleafnode,andremovingitdoesn’tcause
thatleafnodetohavetoofewkeys,thensimplyremovethekeyto
bedeleted.
2.Ifthekeyisnotinaleafthenitisguaranteedthatitspredecessoror
successorwillbeinaleaf--inthiscasewecandeletethekeyand
promotethepredecessororsuccessorkeytothenon-leafdeleted
key’sposition.
If(1)or(2)leadtoaleafnodecontaininglessthantheminimum
numberofkeysthenwehavetolookatthesiblingsimmediately
adjacenttotheleaf:
3.ifoneofthemhasmorethanthemin.numberofkeysthenwe
canpromoteoneofitskeystotheparentandtaketheparentkey
intoourlackingleaf
4.ifneitherofthemhasmorethanthemin.numberofkeysthenthe
lackingleafandoneofitsneighbourscanbecombinedwiththeir
sharedparent(theoppositeofpromotingakey)andthenewleaf
willhavethecorrectnumberofkeys;ifthisstepleavetheparent
withtoofewkeysthenwerepeattheprocessuptotherootitself,
ifrequired

146. 146
CASE#1: SIMPLELEAFDELETION
122952
2791522 5669723143
Delete 2: Since there are enough
keys in the node, just delete it
Assuming a 5-way
B-Tree, as before...

147. 147
CASE#2: SIMPLENON-LEAFDELETION
122952
791522 5669723143
Delete 52
Borrow the predecessor
or (in this case) successor
56

148. 148
CASE#4: TOOFEWKEYSINNODEANDITS
SIBLINGS
122956
791522 69723143
Delete 72
Too few keys!
Join back together

149. 149
CASE#4: TOOFEWKEYSINNODEANDITS
SIBLINGS
1229
791522 69563143

150. 150
CASE#3: ENOUGHSIBLINGS
1229
791522 69563143
Delete 22
Demote root key and
promote leaf key

151. 151
CASE#3: ENOUGHSIBLINGS
12
297915
31
695643

152. 152
Consider the B-tree of order 5 shown below. Delete the keys 95, 226 , 221
and 70.

153. DELETIONINAB-TREE
Thedeletionofkey95issimpleandstraightsincetheleafnodehas
morethantheminimumnumberofelements.
Todelete226,theinternalnodehasonlytheminimumnumberof
elementsandhenceborrowstheimmediatesuccessorviz.,300from
theleafnodewhichhasmorethanthenumberofelements.
Deletionof221callsforthehaulingofkey440totheparentnode
andpullingdownof300totaketheplaceofthedeletedentryinthe
leaf.
Lastlythedeletionof70isalittlemoreinvolvedinprocess.Since
noneoftheadjacentleafnodescanaffordlendingakey,twoofthe
leafnodesarecombinedwiththeinterveningelementfromthe
parenttoformanewleafnode,viz,[32,44,85,81]leaving86alone
intheparentnode.
Thisisnotpossiblesincetheparentnodeisnowrunninglowonits
minimumnumberofelements.Henceweonceagainproceedto
combinetheadjacentsiblingnodesofthisyieldsthe
node[86,110,120,440]whichisthenewroot.

153

154. EXAMPLE
154
OntheB-treeoforder3givenbelow,performthe
followingoperationsintheorderoftheir
appearance:
Insert75,57delete35,65

155. SOLUTION
155

156. ALGORITHMTOFINDTHENO. OFLEAFNODES
INTHEBINARYTREE
get_leaf_node(node)
1. If node==Null then
Return 0
2. If left[node]=Null && right[node]==Null then
Return 1
3. Else
Return get_leaf_node(left[node])+
get_leaf_node(right[node])
156

157. HEAPSORT
157

158. A DATASTRUCTUREHEAP
A heapis an array object that can be viewed as a
nearly complete binary tree.
35
2 4
1
6
6 5 3 24 1
1
2
3
4 5 6
158

159. 159
ARRAYREPRESENTATION OFHEAPS
A heap can be stored as an array
A.
Root of tree is A[1]
Left child of A[i] = A[2i]
Right child of A[i] = A[2i + 1]
Parent of A[i] = A[ i/2]

160. 160
HEAPTYPES
Max-heaps(largestelementatroot),havethemax-heap
property:
for all nodes i, excluding the root:
A[PARENT(i)] ≥ A[i]
Min-heaps(smallestelementatroot),havethemin-heap
property:
for all nodes i, excluding the root:
A[PARENT(i)] ≤ A[i]

161. 161
ADDING/DELETINGNODES
New nodes are always inserted at the bottom level (left to right)
Nodes are removed from the bottom level (right to left)

162. 162
OPERATIONSONHEAPS
Maintain/Restore the max-heap property
MAX-HEAPIFY
Create a max-heap from an unordered array
BUILD-MAX-HEAP
Sort an array in place
HEAPSORT

163. 163
MAINTAININGTHEHEAPPROPERTY
Supposeanodeissmallerthanachild
LeftandRightsubtreesofiaremax-heaps
Toeliminatetheviolation:
Exchangewithlargerchild
Movedownthetree
Continueuntilnodeisnotsmallerthanchildren

164. 164
EXAMPLE
MAX-HEAPIFY(A, 2, 10)
A[2] violates the heap property
A[2] A[4]
A[4] violates the heap property
A[4] A[9]
Heap property restored

165. 165
MAINTAININGTHEHEAPPROPERTY
Assumptions:
Left and Right
subtrees of i are
max-heaps
A[i] may be
smaller than its
children
Alg:MAX-HEAPIFY(A, i, n)
1.l ← LEFT(i)
2.r ← RIGHT(i)
3.ifl ≤ n and A[l] > A[i]
4.thenlargest ←l
5.elselargest ←i
6.ifr ≤ n and A[r] > A[largest]
7.thenlargest ←r
8.iflargest i
9.thenexchange A[i] ↔ A[largest]
10. MAX-HEAPIFY(A, largest, n)

166. 166
BUILDINGAHEAP
Alg:BUILD-MAX-HEAP(A)
1.n= length[A]
2.fori ←n/2downto1
3. doMAX-HEAPIFY(A, i, n)
Convert an array A[1 … n] into a max-heap (n = length[A])
The elements in the subarray A[(n/2+1) .. n] are leaves
Apply MAX-HEAPIFY on elements between 1 and n/2
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
4132169101487A:

167. 167
EXAMPLE: A
4132169101487
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
1
16
7
4
10
9 3
1
2 3
4 5 6 7
8 9 10
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
16
7
1
4
10
9 3
1
2 3
4 5 6 7
8 9 10
8
2 4
14
7
1
16
10
9 3
1
2 3
4 5 6 7
8 9 10
i= 5 i= 4 i= 3
i= 2 i= 1

168. 168
HEAPSORT
Goal:
Sort an array using heap representations
Idea:
Build a max-heapfrom the array
Swap the root (the maximum element) with the last element
in the array
“Discard” this last node by decreasing the heap size
Call MAX-HEAPIFY on the new root
Repeat this process until only one node remains

169. 169
EXAMPLE: A=[7, 4, 3, 1, 2]
MAX-HEAPIFY(A, 1, 4) MAX-HEAPIFY(A, 1, 3) MAX-HEAPIFY(A, 1, 2)
MAX-HEAPIFY(A, 1, 1)

170. 170
ALG: HEAPSORT(A)
1.BUILD-MAX-HEAP(A)
2.for i ←length[A]downto 2
3. do exchange A[1] ↔A[i]
4. MAX-HEAPIFY(A, 1, i -1)