ADVANCE DATA STRUCTURES

UNIT I:
Introduction to Data Structures, Singly Linked Lists, Doubly Linked Lists, Circular Lists Algorithms. Stacks and Queues:
Algorithm Implementation using Linked Lists.

UNIT II:
Searching-Linear and Binary, Search Methods, Sorting-Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort.
Trees- Binary trees, Properties, Representation and Traversals (DFT, BFT), Expression Trees (Infix, prefix, postfix). Graphs-Basic
Concepts, Storage structures and Traversals.

ALGORITHMS
Definition: An Algorithm is a method of representing the step-by-step procedure
forsolving a problem.It isa method of finding the right answer toa problem or to
adifferentproblem bybreakingthe problem into simplecases.

Itmust possessthefollowingproperties:

1. Finiteness:An algorithmshouldterminateinafinitenumberofsteps.

2. Definiteness:Eachstep ofthealgorithmmustbeprecisely(clearly) stated.

3. Effectiveness: Each step must be effective. i.e.; it should be

easilyconvertibleintoprogramstatementandcan
beperformedexactlyinafiniteamountof time.

4. Generality:Algorithmshouldbe completeinitself, sothatit

canbeusedtosolveallproblems ofgiven typeforanyinputdata.

5. Input/output: Each algorithm must take zero, one or more quantities as

inputdataandgives oneof moreoutput values.
An algorithm can be written in English like sentences or in
anystandard representations. The algorithm written in English language is called
Pseudocode.

Example:To findthe averageof3numbers, the algorithmis asshownbelow.

Step1: Read the numbers a, b, c, and
d.Step2: Compute the sum of a, b, and
c.Step3: Divide thesum by3.
Step4: Store the result in variable of
d.Step5:End the program.

DevelopmentOf AnAlgorithm
Thestepsinvolvedin thedevelopmentofanalgorithmareasfollows:

Specifying the problem

statement.Designingan algorithm.

DSUsingC++ Page1
 Coding.De
bugging
Testing and
ValidatingDocumentationandMai
ntenance.

Specifying the problem statement: The problem which has to be implemented in to

aprogram must be thoroughly understood before the program is written. Problem must
beanalyzedto determinetheinputand output requirements of theprogram.

DSUsingC++ Page2
 DesigninganAlgorithm:Oncetheproblemisclearedthenasolutionmethodforsolvingthe
problem has to be analyzed. There may be several methods available for obtaining
therequired solution. The best suitable method is designing an Algorithm. To improve
theclarityand understandability oftheprogram flowchartsaredrawnusingalgorithms.
Coding: The actual program is written in the required programming language with the
helpofinformation depicted in flowcharts and algorithms.

Debugging:There is a possibility of occurrence of errors in program. These errors must

beremoved for proper working of programs. The process of checking the errors in the
programisknownas‗Debugging‘.
Therearethreetypesof errorsintheprogram.
SyntacticErrors: Theyoccurdueto wrongusageofsyntaxforthe statements.
Ex:x=a*%b
Here two operators are used in between
twooperands.RuntimeErrors:Theyaredeterminedattheexecutionti
meofthe program
Ex: Divide by
zeroRangeoutofboun
ds.
Logical Errors : They occur due to incorrect usage of instructions in the program. They
areneither displayed during compilation or execution nor cause any obstruction to the
programexecution. Theyonlycauseincorrect outputs.

Testing and Validating: Once the program is written , it must be tested and then
validated.i.e., to check whether the program is producing correct results or not for different
values ofinput.

DocumentationandMaintenance:Documentationistheprocessofcollecting,organizingand
maintaining, in written the complete information of the program for future
references.Maintenance is the process of upgrading the program, according to the
changingrequirements.

PERFORMANCEANALYSIS
When severalalgorithmscan be designed for thesolutionof a problem, there arisesthe
need to determine which among them is the best. The efficiency of a program or
analgorithmis measured bycomputingits timeand/or spacecomplexities.
Thetime complexityofanalgorithmis
afunctionoftherunningtimeofthealgorithm.
The space complexity is a function of the space required by it to run to
completion.Thetime complexityis therefore given in terms offrequency count.
Frequencycount is basicallyacount denotingnumberof timesa statement execution

AsymptoticNotations:
To choose the best algorithm, we need to check efficiency of each
algorithm.The efficiency can be measured by computing time complexity of
eachalgorithm. Asymptotic notation is a shorthand way to represent the
timecomplexity.
Usingasymptoticnotations wecangivetime complexityas―fastestpossible‖,
―slowest possible‖or ―averagetime‖.
DSUsingC++ Page3
 VariousnotationssuchasΩ,θ,Ousedarecalledasymptoticnotions.

DSUsingC++ Page4
 BigOhNotation
BigOhnotationdenotedby‗O‘isamethodofrepresentingtheupperboundofalgorith
m‘s running time. Using big oh notation we can give longest amount of
timetakenbythe algorithm to complete.

Definition:
Let, f(n) andg(n)aretwonon-
negativefunctions.Andifthereexistsanintegern0andconstantC suchthat C >0 and for all
integers n> n0, f(n)≤ c*g(n),then
f(n)=Og(n).

Various meanings associated with big-oh

areO(1) constantcomputingtime
O(n) linear
2
O(n ) quadratic
O(n3) cubic
n
O(2 ) exponential
O(logn) logarithmic

TherelationshipamongthesecomputingtimeisO(1)<
O(logn)<O(n)< O(nlogn)<O(n2)<O(2n)

OmegaNotation:-
Omeganotationdenoted‗Ω‘isamethodofrepresentingthelowerboundofalgorithm‘s
running time. Using omega notation we can denote shortest amount of timetaken
byalgorithm to complete.

Definition:
Let,f(n)andg(n)aretwonon-negativefunctions.Andifthereexistsanintegern0andconstant
C suchthatC >0and forall integersn >n0,f(n)>c*g(n), then
f(n)=Ω g(n).

DSUsingC++ Page5
DSUsingC++ Page6
 ThetaNotation:-
Thetanotationdenotedas‗θ‘isamethodofrepresentingrunningtimebetweenupperb
ound and lower bound.
Definition:
Let, f(n) and g(n) are two non-negative functions. There exists positive constants
C1andC2suchthat C1g(n)≤ f(n)≤ C2g(n)and f(n)=θ g(n)

How tocomputetimecomplexity
1 AlgorithmMessage(n) 0
2 { 0

3 fori=1 to ndo n+1

4 { 0
5 write(―Hello‖); n
6 } 0
7 } 0
total frequencycount 2n+1

Whilecomputingthe timecomplexitywewill neglect all theconstants, henceignoring2and

1 wewillget n. Hencethe timecomplexitybecomes O(n).

f(n)=Og(n).
i.ef(n)=O(2n+1)
=O(n)//ignoreconstants

1 Algorithmadd(A,B,m,n) 0

2 { 0
3 fori=1 to mdo m+1
4 forj=1 to ndo m(n+1)
5 C[i,j]=A[i,j]+B[i,j] mn

DSUsingC++ Page7
 6 } 0
total frequencycount 2mn+2m+1
f(n)=Og(n).
=>O(2mn+2m+1)//whenm=n;
=O(2n2+2n+1);Byneglectingtheconstants,
weget thetime complexityasO(n2).
Themaximumdegreeof thepolynomialhastobe considered.
BestCase,WorstCaseand AverageCaseAnalysis
If an algorithm takes minimum amount of time to run to completion for a specific
set of input then it iscalledbest casecomplexity.
If an algorithm takes maximum amount of time to run to completion for a specific
set of input then it iscalledworst case time complexity.
The time complexity that we get for certain set of inputs is as a average same.
Then for corresponding in put such a time complexity is called average case
time complexity.
Space Complexity: The space complexity can be defined as amount of memory
required by an algorithm to run.
Let p bean algorithm ,To compute the space complexity we use two factors: constant and
instance characteristics .The space requirement S(p)can be given as
S(p)=C +Sp
Where C is a constant i.e.. fixed part and it denotes the space of inputs and outputs.
Thisspaceis anamountof spacetakenbyinstruction,variablesand identifiers.
Spisaspacedependentuponinstancecharacteristics.Thisisavariablepartwhosespace
requirementdependonparticularprobleminstance.
Eg:1
Algorithm add(a,b,c)
{
Return a +b +c;
}
If weassumea,b,coccupyone wordsizethentotal sizecomestobe3S(p)=C
Eg:2
Algorithm add(x,n)
{

sum=0.0;
for i= 1 to n do
sum:=sum+x[i];
returnsum;
}S(p
)≥(n+3)
Then space required for x [], one space for n, one for i , and one for sum
Searching:Searching is the technique of finding desired data it emsthat has beenstored

within some data structure. Data structures can include linked lists, arrays, search trees,
hashtables, or various other storage methods. The appropriate search algorithm often
depends onthedata structurebeingsearched.
Search algorithms can be classified based on their mechanism of searching. They
areLinearsearching
Binarysearching
DSUsingC++ Page8
 Linear or Sequential searching:Linear Search is the most natural searching method and
Itis very simple but very poor in performance at times .In this method, the searching
beginswith searching every element of the list till the required record is found. The
elements in thelist maybein anyorder.i.e. sorted orunsorted.

We begin search by comparing the first element of the list with the target element.
Ifit matches, the search ends and position of the element is returned. Otherwise, we will
moveto next element and compare. In this way, the target element is compared with all
theelements until a match occurs. If the match do not occur and there are no more elements
tobecompared,weconcludethattargetelementisabsentinthelistbyreturningpositionas-1.

Forexampleconsiderthefollowinglist ofelements.
55 95 75 85 11 25 65 45
Supposewewanttosearchforelement11(i.e.Targetelement=11).Wefirstcompare the
target element with first element in list i.e. 55. Since both are not matching wemove on the
next elements in the list and compare. Finally we will find the match after 5comparisonsat
position 4 startingfrom position 0.
Linearsearch can beimplementedintwoways.i)Nonrecursiveii)recursive

AlgorithmforLinearsearch

Linear_Search(A[],N,val,pos)Ste
p 1 : Set pos = -1 and k = 0Step2 :
Repeat whilek<N
Begin
Step3 : if A[ k ]=val
Set pos =
kprint
posGotoste
p5
Endwhile
Step 4 : print ―Value is not
present‖Step5:Exit

BINARYSEARCHING

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This
searchalgorithm works on the principle of divide and conquer. Binary search looks for a
particularitem by comparing the middle most item of the collection. If a match occurs, then
the indexof item is returned. If the middle item is greater than the item, then the item is
searched inthe sub-array to the left of the middle item. Otherwise, the item is searched for in
the sub-array to the right of the middle item. This processcontinues on the sub-array as well
untilthesizeof thesubarrayreduces to zero.
Before applying binary searching, the list of items should be sorted in ascending
ordescendingorder.
Best case time complexity is
O(1)WorstcasetimecomplexityisO(log
n)

DSUsingC++ Page9
DSUsingC++ Page10
 Algorithm:
Binary_Search (A[ ],U_bound,VAL)
Step 1 : set BEG = 0 , END = U_bound , POS = -
1Step2 : Repeat while(BEG<=END )
Step 3: set MID=( BEG+END )/ 2
Step 4: if A [ MID ] == VAL
thenPOS= MID
printVAL―isavailableat―,POSGo
ToStep 6
End if
ifA[MID]>VALthensetE
ND=MID– 1
Else
setBEG =MID+1
End
ifEndwhil
e
Step5 : if POS = -1 then
printVAL―isnotpresent―End if
Step6:EXIT

SORTING

Arrangingtheelementsin alisteither inascendingor descendingorder.

varioussortingalgorithmsare
Bubble
sortselection
sortInsertion
sortQuick
sortMerge
sortHeapsort

DSUsingC++ Page11
 BUBBLESORT

The bubble sort is an example of exchange sort. In this method, repetitive comparison
isperformed among elements and essential swapping of elements is done. Bubble sort
iscommonly used in sorting algorithms. It is easy to understand but time consuming i.e.
takesmore number of comparisons to sort a list . In this type, two successive elements
arecompared and swapping is done. Thus, step-by-step entire array elements are checked. It
isdifferentfromtheselectionsort.Insteadofsearchingtheminimumelementandthenapplying
swapping, two records are swapped instantly upon noticing that they are not inorder.
ALGORITHM:
Bubble_Sort(A [], N)
Step1:Start
Step2:Takeanarrayof
nelementsStep3: fori=0,… n-2
Step 4: for j=i+1,…….n-
1Step5:ifarr[j]>arr[j+1]then
Interchange arr[j] and
arr[j+1]End ofif
Step6:PrintthesortedarrayarrSte
p 7:Stop

SELECTIONSORT

selectionsort:-Selectionsort(Select thesmallestand Exchange):

The first item is compared with the remaining n-1 items, and whichever of all
islowest, is put in the first position.Then the second item from the list is taken and
comparedwith the remaining (n-2) items, if an item with a value less than that of the second
item isfound on the (n-2) items, it is swapped (Interchanged) with the second item of the list
and soon.

DSUsingC++ Page12
 INSERTIONSORT

Insertion sort: It iterates, consuming one input element each repetition, and growing
asorted output list. Each iteration, insertion sort removes one element from the input
data,finds the location it belongs within the sorted list, and inserts itthere. It repeats until
noinputelements remain.

ALGORITHM:
Step1: start
Step 2: for i ← 1 to
length(A)Step3: j←i
Step4: while j > 0 and A[j-1] >
A[j]Step5: swap A[j] andA[j-1]
Step6: j←j-
1Step7: end
whileStep 8: end
forStep9: stop

QUICKSORT

Quicksort: It isa divide and conquer algorithm. DevelopedbyTonyHoarein1959.Quicksort

firstdividesalarge arrayintotwo smallersub-

arrays:thelowelementsandthehighelements.
Quick sort can then recursively sort the sub-
arrays.ALGORITHM:

Step1:Pickanelement,calledapivot,fromthe array.

Step 2: Partitioning: reorder the array so that all elements with values less than the
pivotcomebeforethepivot, whileallelements withvaluesgreater
thanthepivotcomeafter it (equal values can go either way). After this partitioning,
the pivot is in itsfinalposition. This is called thepartition operation.

Step 3: Recursively apply the above steps to the sub-array of elements with
smallervalues andseparatelyto thesub-arrayofelementswith greatervalues.

DSUsingC++ Page13
 MERGESORT

Merge sort is a sorting technique based on divide and conquer technique. In merge sort
theunsorted list is divided into N sublists, each having one element, because a list of
oneelement is considered sorted. Then, it repeatedly merge these sublists, to produce new
sortedsublists, and at lasts one sorted list is produced. Merge Sort is quite fast, and has a
timecomplexityof O(n logn).

Conceptually,mergesortworksasfollows:
1. Dividetheunsorted listinto two sublists of abouthalf thesize.
2. Divide each of the two sub lists recursively until we have list sizes of length 1, in
whichcasethe list itself is returned.
3. Mergethetwo sublistsback intoonesortedlist.

intmain()
{
int n,i;
intlist[30];
cout<<"enternoofelements\
n";cin>>n;
cout<<"enter"<<n<<"numbers";f
or(i=0;i<n;i++)
cin>>list[i];mergesor
t(list,0,n-1);
cout<<"aftersorting\
n";for(i=0;i<n;i+
+)cout<<list[i]<<‖\t‖;
return0;
}

RUN1:

enternoofelements5
enter5 numbers44 335511-1
aftersorting-1 1133 4455

DSUsingC++ Page14
 HEAPSORT

It is a completely binary tree with the property that a parent is always greater than
orequal to either of its children (if they exist). first the heap (max or min) is created
usingbinarytreeand then heapis sorted usingpriorityqueue.

StepsFollowed:

a) Startwithjustoneelement.Oneelement willalwayssatisfyheapproperty.
b) Insertnextelementsandmakethisheap.
c) Repeatstepb,until allelementsareincludedintheheap.

a) Exchangethe rootandlastelementintheheap.
b) Makethis heap again, but this timedo not includethe last node.
c) Repeatstepsa andbuntil thereisno elementleft.

Algorithm Worstcase Averagecase Bestcase

Bubblesort O(n2) O(n2) O(n2)

selectionsort O(n2) O(n2) O(n2)
Insertionsort O(n2) O(n2) O(n2)
Quicksort O(nlogn) O(nlogn) O(n2)
Mergesort O(nlogn) O(nlogn) O(nlogn)
Heapsort O(nlogn) O(nlogn) O(nlogn)
Linearsearch O(n) O(n) O(1)
Binarysearch O(logn) O(log n) O(1)

UNIT III:
Dictionaries, ADT, The List ADT, Stack ADT, Queue ADT, Hash Table Representation, Hash Functions, Collision Resolution-
Separate Chaining, Open Addressing-Linear Probing, Double Hashing.

Data structure A data structure is a specialized format for organizing and storing data.
General data structure types include the array, the file, the record, the table, the tree, and
soon. Any data structure is designed to organize data to suit a specific purpose so that it can
be accessed and worked with in appropriate ways

AbstractDataType

In computer science, an abstract data type (ADT) is a mathematical model for

datatypes where a data type is defined by its behavior (semantics) from the point of view
of auser of the data, specifically in terms of possible values, possible operations on data of
thistype, and the behavior of these operations. When a class is used as a type, it is an
abstract type that refers to a hidden representation. In this model an ADT is typically
DSUsingC++ Page15
 implemented as a class, and each instance of the ADT is usually a n object of that class. In
ADT all the implementation details are hidden

Lineardatastructuresarethedatastructuresin whichdataisarrangedinalist orina

sequence.
Nonlinear datastructures arethedata structures inwhich data
maybearrangedin a hierarchic al manner

LISTADT

Listisbasicallythecollectionofelementsarrange dinasequential
manner.Inmemory we can store the list in two ways: one way is we can store the
elements insequentialmemorylocations. That meanswe can storethe listin arrays.
Theotherwayis wecanusepointers orlinks toassociate
elementssequentially.Thisis known as linked list.

DSUsingC++ Page16
 LINKEDLISTS

The linked list is very different type of collection from an array. Using such lists, we
can store collections of information limited only by the total amount of memory that the OS
will allow us to use. Further more, there is no need to specify our needs in advance. The
linked list is very flexible dynamic data structure: items may be added to it or deleted from
it at will. A programmer need not worry about how many items a program will have to
accommodate in advance. This allows us to write robust programs which require much less
maintenance.

The linked allocation has the following drawbacks:

1. No direct access to a particular element.

2. Additional memory required for pointers.

Linked list are of 3 types:

1. Singly Linked List

2. Doubly Linked List
3. Circularly Linked List

SINGLYLINKEDLIST

A singly linked list, or simply a linked list, is a linear collection of data items.
Thelinearorderisgivenbymeans ofPOINTERS.Thesetypesof
listsareoftenreferredtoaslinearlinked list.
* Eachiteminthelistiscalledanode.
* Eachnodeof thelisthas two fields:
1. Information-contains theitem beingstored inthelist.
2. Nextaddress-contains theaddress ofthenext item in thelist.
* Thelast nodein thelistcontains NULLpointertoindicate thatit is
theendofthe list. Conceptual viewof SinglyLinkedList

Operationson Singlylinked list:

Insertion of a
nodeDeletions of a
nodeTraversingthe
list

DSUsingC++ Page17
 Structure of a

node:Method -1:

structnode
{ Data link
intdata;
structnode *link;
};

Method-2:

classnode
{
public:
int
data;node*
link;
};

Insertions:To place an elementsin thelist thereare3cases :

1. Atthebeginning
2. End ofthe list
3. Atagivenposition

case1:Insert atthebeginning

temp

head is the pointer variable which contains address of the first node and temp
containsaddressofnew nodeto beinserted then samplecodeis

temp->link=head;head=temp;

Afterinsertion:

DSUsingC++ Page18
 Codeforinsertfront:-

template<class T>
voidlist<T>::insert_front()
{
struct node
<T>*t,*temp;cout<<"Enterdat
aintonode:";cin>>item;temp=
create_node(item);if(head==N
ULL)
head=temp;
else
{temp->link=head;
head=temp;
}
}

case2:Insertingend ofthelist

temp

head is the pointer variable which contains address of the first node and temp
containsaddressof newnodeto beinserted then samplecodeis

t=head;
while(t->link!=NULL)
{
t=t->link;
}
t->link=temp;

Afterinsertion thelinkedlistis

DSUsingC++ Page19
 Codeforinsert End:-

template<class T>
voidlist<T>::insert_end()
{
structnode<T>*t,*temp;i
nt n;
cout<<"Enterdataintonode:";ci
n>>n;
temp=create_node(n);if(
head==NULL)
head=temp;
else
{t=head;while(t-
>link!=NULL)
t=t->link;
t->link=temp;
}
}

case3: Insertata position

insertnodeat position3
head is the pointer variable which contains address of the first node and temp
containsaddressof newnodeto beinserted then samplecodeis
c=1;
while(c<pos)
{
prev=cur;cur=cur->link;c++;
}
prev->link=temp;temp->link=cur;

DSUsingC++ Page20
 Codeforinserting anodeat agivenposition:-

template<class T>
voidlist<T>::Insert_at_pos(intpos)
{structnode<T>*cur,*prev,*temp;
intc=1;
cout<<"Enterdataintonode:";ci
n>>itemtemp=create_node(ite
m);if(head==NULL)
head=temp;
else
{
prev=cur=head;
if(pos==1)
{
temp-
>link=head;head
} =temp;
else
{
while(c<pos)
{c++;
prev=cu
r;
cur=cur->link;
}
prev-
>link=temp;temp
->link=cur;
}
}
}

Deletions:Removinganelementfrom thelist, withoutdestroyingtheintegrityof thelistitself.

Toplaceanelement fromthelistthereare3cases:
1. Deleteanodeat beginningof thelist
2. Deleteanodeat end of thelist
3. Deleteanodeat a givenposition

DSUsingC++ Page21
 Case1:Deleteanodeat beginningofthelisthead

head isthepointer variablewhichcontains addressofthe firstnode

samplecodeis
t=head;head=hea
d->link;
cout<<"node"<<t-
>data<<"Deletionissucess";delete(t);

head

Case2.Deletea nodeatendofthelist

head

Todeletelastnode,findthenode usingfollowingcode

structnode<T>*cur,*prev;cur=prev=head;
while(cur->link!=NULL)
{prev=cur;cur=cur-
>link;
}
prev->link=NULL;
cout<<"node "<<cur->data<<" Deletion is sucess";free(cur);

head

DSUsingC++ Page22
 Codefordeletinganodeatendofthelist
template<class T>
voidlist<T>::delete_end()
{
struct
node<T>*cur,*pre
v;cur=prev=head;if
(head==NULL)
cout<<"ListisEmpty\n";
else
{cur=prev=head;if(head-
>link==NULL)
{
cout<<"node "<<cur->data<<" Deletion
issucess";free(cur);
head=NULL;
}
else
{while(cur->link!=NULL)
{prev=cur;cur=cur-
>link;
}
prev->link=NULL;
cout<<"node"<<cur-
>data<<"Deletionissucess";free(cur);
}
}
}

CASE3. Deletea node atagiven position

head

Deletenode at position3
head isthepointervariable whichcontainsaddressof thefirstnode.Nodetobedeletedisnode
containing value
30.Findingnodeatposition
3

c=1;
while(c<pos)
{c++;
prev=cur;
cur=cur->link;
}

DSUsingC++ Page23
 prev cur

10 20 30 40
NUL
cur is the node to be deleted . before deleting update L
linkscodeto updatelinksprev->link=cur->link;
cout<<cur->data<<"isdeletedsuccessfully";deletecur;
prev

10 20 30 40

NUL
L
Traversing the list: Assuming we are given the pointer to the head of the list, how do
wegettheend ofthe list.

template <class
T>voidlist<T>::display
()
{
structnode<T>*t;

if(head==NULL)
{
cout<<"ListisEmpty\n";
}
else
{t=head;
while(t!
=NULL)
{cout<<t->data<<"-
>";t=t->link;
}
}
}

DSUsingC++ Page24
 DOUBLYLINKED LIST
A singly linked list has the disadvantage that we can only traverse it in one
direction.Many applications require searching backwards and forwards through sections of a
list. Auseful refinement that can be made to the singly linked list is to create a doubly linked
list.The distinction made between the two list types is that while singly linked list have
pointersgoing in one direction, doubly linked list have pointer both to the next and to the
previouselement in the list. The main advantage of a doubly linked list is that, they permit
traversingorsearchingof thelist in both directions.

Inthislinkedlisteachnodecontainsthreefields.
a) Oneto storedata
b) Remainingareself referentialpointerswhichpointstopreviousandnextnodesin
thelist

prev data next

ImplementationofnodeusingstructureM

ethod -1:

structnode
{
intdata;
struct node
*prev;structnode*
next;
};

ImplementationofnodeusingclassM

ethod -2:

classnode
{
public:
int
data;node
*prev;node
*next;
};

NU
NULL 10 20 30 LL
OperationsonDoublylinkedlist:In
sertion of a nodeDeletions
of a nodeTraversingthe
list

DSUsingC++ Page25
 DoublylinkedlistADT:

template <class
T>classdlist
{
intdata;

public: structdnode<T>*head;

dlist()
{
head=NULL;
}
voiddisplay();
struct dnode<T>*create_dnode(int
n);voidinsert_end();
void
insert_front();void
delete_end();void
delete_front();void
dnode_count();

void Insert_at_pos(int
pos);voidDelete_at_pos(intp
os);
};

Insertions:To place an elementsin thelist thereare3 cases

1. Atthebeginning
2. End ofthe list
3. Atagivenposition

case1:Insert atthebeginning

head is the pointer variable which contains address of the first node and temp
containsaddressof newnodeto beinserted then samplecodeis
NU
40 10 20
temp->next=head;head->prev=temp;head=temp; 30 LL

head

DSUsingC++ Page26
 Codeforinsertfront:-

template<class T>
voidDLL<T>::insert_front()
{
struct
dnode<T>*t,*temp;cout<<"E
nterdataintonode:";cin>>data;t
emp=create_dnode(data);if(he
ad==NULL)
head=temp;
else
{temp-
>next=head
;head-
>prev=temp
;
head=temp;
}
}
Codeto insert anodeatEnd:-

template<class T>

voidDLL<T>::insert_end()
{
struct dnode<T>
*t,*temp;int n;
cout<<"Enterdataintodnode:";ci
n>>n;
temp=create_dnode(n);if
(head==NULL)
head=temp;
else

{t=head;while(t-
>next!=NULL)
t=t-
>next;t-
>next=temp;

temp->prev=t;
}
}

DSUsingC++ Page27
Codeto inserta nodeat a position

template<class T>
voiddlist<T>::Insert_at_pos(intpos)
{
structdnode<T>*cr,*pr,*temp;
intcount=1;
cout<<"Enterdataintodnode:";ci
n>>data;temp=create_dnode(da
ta);display();
if(head==NULL)
{//whenlist is empty
head=temp;
}
else
{pr=cr=head;
if(pos==1)
{//
insertingatpo
s=1temp-
>next=head;
head=temp;
}
else
{
while(count<pos)
{count++;
pr=cr;
cr=cr->next;
}
pr-
>next=temp;te
mp-
>prev=pr;temp-
>next=cr;cr-
>prev=temp;
}
}
}

Deletions:Removinganelementfrom thelist, withoutdestroyingtheintegrityof thelistitself.

Toplaceanelement fromthelistthereare3cases:
1. Deleteanodeat beginningof thelist
2. Deleteanodeat end of thelist
3. Deleteanodeat a givenposition

DSUsingC++ Page28
 Case1: Delete anodeatbeginningof thelist

head

NULL NU
10 20 30 LL

headisthepointervariablewhichcontainsaddressofthefirstnodesamplecodei

s
t=head;head=head->next;
head->prev=NULL;
cout<<"dnode"<<t->data<<"Deletionissucess";delete(t);

head

NULL
NULL 10 NULL 30

20
codefordeletinga nodeat front

template<class T>
voiddlist<T>::delete_front()
{structdnode<T>*t;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{t=head;
head=head-
>next;head-
>prev=NULL;
cout<<"dnode"<<t-
>data<<"Deletionissucess";delete(t);
}
}

DSUsingC++ Page29
 Case2. Deleteanodeatendofthelist
Todeleted the last node find thelast node. findthenodeusingfollowingcode
structdnode<T>*pr,*cr;pr=cr=head;
while(cr->next!=NULL)
{pr=cr;cr=cr-
>next;
}
pr->next=NULL;
cout<<"dnode "<<cr->data<<" Deletion is sucess";delete(cr);

head

20 NULL 30
NULL 10 pr
NULL

cr

codefordeletinganodeatendofthelist

template<class T>
voiddlist<T>::delete_end()
{
structdnode<T>*pr,*cr;
pr=cr=head;if(he
ad==NULL)
cout<<"ListisEmpty\n";
else
{cr=pr=head;if(head-
>next==NULL)
{
cout<<"dnode "<<cr->data<<" Deletion
issucess";delete(cr);
head=NULL;
}
else
{while(cr->next!=NULL)
{pr=cr;
cr=cr->next;
}
pr->next=NULL;
cout<<"dnode"<<cr-
>data<<"Deletionissucess";delete(cr);
}
}
}

DSUsingC++ Page30
 CASE3. Deletea node atagiven position
head

Deletenode
NULL at position2
10 30 20 NULL
head isthepointer variablewhichcontains addressofthe firstnode.Node to bedeletedisnode
containing value
30.Findingnodeatposition2
.

while(count<pos)
{pr=cr;cr=cr-
>next;co
unt++;
}
pr->next=cr-
>next;cr->next-
>prev=pr;

head
NULL
NULL 10 30 20

cr
pr

DSUsingC++ Page31
 CIRCULARLYLINKED LIST
A circularly linked list, or simply circular list, is a linked list in which the last node
isalways points to the first node. This type of list can be build just by replacing the
NULLpointerat theendofthelist witha pointerwhich pointsto thefirst node.Thereis no
firstorlastnodein thecircular list.

Advantages:
Anynodecan be traversed startingfromanyother nodeinthelist.
There is no need of NULL pointer to signal the end of the list and hence,
allpointerscontain valid addresses.
In contrasttosinglylinkedlist,deletionoperationincircularlistissimplifiedasthesearch
for the previous node of an element to be deleted can be started from thatitem
itself.

head

STACK ADT:-A Stack is a linear data structure where insertion and deletion of items
takesplace at one end called top of the stack. A Stack is defined as a data structure which
operatesonalast-infirst-out basis.So itis alsois referred asLast-inFirst-out( LIFO).
Stackusesasingleindexorpointertokeeptrackoftheinformationinthestack.
Thebasicoperationsassociatedwiththestackare:
a) push(insert)anitemontothe stack.
b) pop(remove)anitemfromthestack.

Thegeneralterminology associatedwith thestack isas follows:

A stack pointer keeps track of the current position on the stack. When an element
isplaced on the stack, it is said to bepushedon the stack. When an objectis removed fromthe
stack, it is said to bepoppedoff the stack.Two additional termsalmostalways usedwith stacks
are overflow, which occurs when we try to push more information on a stackthat it can
hold, and underflow, which occurs when we try to pop an item off a stack whichisempty.

Pushingitemsontothestack:

Assumethat thearrayelements begin at 0( becausethe arraysubscript starts from 0)

and the maximum elements that can be placed in stack is max. The stack pointer, top,
isconsidered to be pointing to the top element of the stack. A push operation thus
involvesadjustingthestackpointertopointtonextfreeslotandthencopyingdataintothatslotofthest
ack.Initiallythe topis initialized to-1.

DSUsingC++ Page32
 //
codetopushanelementontostack;templ
ate<classT>
voidstack<T>::push()
{
if(top==max-1)
cout<<"StackOverflow...\n";
else
{
cout<<"Enteranelementtobepushed:";to
p++;
cin>>data;stk
[top]=data;
cout<<"PushedSucesfully.....\n";
}
}

Poppinganelementfromstack:
To remove an item, first extract the data from top position in the stack and
thendecrementthestack pointer, top.

ApplicationsofStack:
1. Stacksareusedinconversionofinfixtopostfixexpression.
2. Stacksare alsousedinevaluationofpostfixexpression.
3. Stacksareusedtoimplementrecursiveprocedures.
4. Stacksareusedincompilers.
5. ReverseString

An arithmetic expression can be written in three different but equivalent

notations,i.e.,withoutchangingthe
essenceoroutputofanexpression.Thesenotationsare−
1. InfixNotation
2. Prefix(Polish)Notation
3. Postfix(Reverse-Polish)Notation

DSUsingC++ Page33
 ConversionofInfix ExpressionstoPrefixandPostfix

Convertfollowinginfixexpressiontoprefixandpostfix(A+
B) *C -(D-E)* (F+G)

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower,[1] and
sometimespluralized)isamathematicalgameorpuzzle.Itconsistsofthreerods,andanumberofdisk
s of different sizes which can slide onto any rod. The puzzle starts with the disks in aneat
stack in ascending order of size on one rod, the smallest at the top, thus making
aconicalshape.

DSUsingC++ Page34
 Theobjectiveof thepuzzleis to move theentirestack toanotherrod,
obeyingthefollowingsimplerules:
1. Onlyonediskcan bemoved at a time.
2. Eachmoveconsists oftakingtheupper diskfromoneof
thestacksandplacingitontopofanotherstack i.e. adisk can onlybemoved if itis
theuppermost disk on astack.
3. No disk maybeplaced on top of asmaller disk.

QUEUEADT
A queue is an ordered collection of data such that the data is inserted at one end
anddeletedfromanotherend. Thekeydifferencewhencompared stacksis that
inaqueuetheinformation stored is processed first-in first-out or FIFO. In other words the
informationreceivefrom aqueuecomesin thesameorderthat it was placedon the queue.

RepresentingaQueue:
Oneof themost commonwayto implementaqueueis usingarray. Aneasywayto do so isto
defineanarrayQueue,and twoadditional variablesfront
andrear.Therulesformanipulatingthese
variablesare
simple:
Each time information is added to the queue, increment
rear.Eachtimeinformationistakenfromthequeue,incrementfront.
Wheneverfront >rearorfront=rear=-1 thequeueis empty.
Array implementation of a Queue do have drawbacks. The maximum queue size has
tobe set at compile time, rather than at run time. Space can be wasted, if we do not use
thefull capacityof thearray.

DSUsingC++ Page35
 OperationsonQueue:
Aqueuehavetwobasic operations:
a) addingnew itemto the queue
b) removingitemsfrom queue.
The operation of adding new item on the queue occurs only at one end of the queue
calledtherear or back.
Theoperation ofremovingitemsof the queueoccursat theother endcalled thefront.

For insertion and deletion of an element from a queue, the array elements begin at 0
andthe maximum elements of the array is maxSize. The variable front will hold the
index ofthe item that is considered the front of the queue, while the rear variable will
hold theindex of thelast item in thequeue.
Assume that initially the front and rear variables are initialized to -1. Like
stacks,underflowandoverflowconditionsaretobechecked beforeoperations inaqueue.

Queueempty orunderflowconditionis
if((front>rear)||front= =-1)cout<‖Queueisempty‖;

QueueFulloroverflowconditionis
if((rear==max)cout<‖Queueisfull‖;

DSUsingC++ Page36
 ApplicationofQueue:
Queue, as the name suggests issued whenever we need to have any group of objects in
an order in which the first one coming in, also gets out first while the others wait
forthereturn, likein thefollowingscenarios :
1. Servingrequestson asingleshared resource,like aprinter,CPUtask schedulingetc.
2. Inreallife,Call Centerphonesystemswill useQueues,tohold
peoplecallingtheminanorder, until aservicerepresentativeis free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the
sameorderas theyarrive, Firstcome first served.

CIRCULARQUEUE
Oncethequeuegetsfilled up,nomoreelementscan beaddedto iteven if anyelementis
removed from it consequently. This is because during deletion, rear pointer is
notadjusted.

When the queue contains very few items and the rear pointer points to last element.
i.e.rear=maxSize-1,wecannotinsert anymoreitems
intoqueuebecausetheoverflowconditionsatisfies.That means a lot of spaceis wasted
.Frequentreshufflingofelementsistimeconsuming.Onesolutiontothisisarranging all
elements in a circular fashion. Such structures are often referred to as CircularQueues.

A circular queue is a queue in which all locations are treated as circular such
thatthefirst location CQ[0]follows the lastlocation CQ[max-1].

CircularQueueemptyorunderflowconditionis

if(front==-1)
cout<<"Queueisempty";

CircularQueueFulloroverflowconditionis

if(front==(rear+1)%max)
{
cout<<"CircularQueueisfull\n";
}

DSUsingC++ Page37
 InsertionintoaCircularQueue:
AlgorithmCQueueInsertion(Q,maxSize,Front,Rear,item)
Step1:If Rear =maxSize-1 then
Rear=0
else
Rear=Rear+1
Step 2: If Front = Rear
thenprint―QueueOverflo
w‖Return
Step3:Q[Rear] =item

Step 4: If Front = 0
thenFront=1
Step5: Return

DeletionfromCircular Queue:

AlgorithmCQueueDeletion(Q,maxSize,Front,Rear,item)
Step1:If Front=0then
print ―QueueUnderflow‖
Return
Step2:K=Q[Front]
Step 3: If Front = Rear
thenbegin
Front=-1
Rear=-1
end
else
If Front = maxSize-1
thenFront=0
else
Front=Front+1
Step4: Return K
DSUsingC++ Page38
 DEQUEUE
In a linear queue, the usual practice is for insertion of elements we use one end called
rearfor deletion of elements we use another end called as front. But in the doubly ended
queuewecanmakeuseofboththeendsforinsertionoftheelementsaswellaswecanuseboththe ends
for deletion of the elements. That means it is possible to insert the elements by rearaswell as
byfront. Similarlyit is possible to deletethe elements from rear.

Normallyinsertionof elementsis doneatrear endand deletethe elements fromfront

end.Forexampleelements 10,20,30 areinserted at rearend.
Toinsertanyelementfromfront endthenfirst shiftallthe elementstothe right.

HASHTABLEREPRESENTATION
Hash table is a data structure used for storing and retrieving data very quickly.
Insertionof data in the hash table is based on the key value. Hence every entry in the
hash table isassociatedwith some key.

Using the hash key the required piece of data can be searched in the hash table by few
ormore key comparisons. The searching time is then dependent upon the size of the
hashtable.

Theeffectiverepresentationofdictionarycanbedoneusinghashtable.Wecanplacethedictio
naryentriesin thehash table usinghashfunction.

HASHFUNCTION

Hash function is a function which is used to put the data in the hash table. Hence one
canuse the same hash function to retrieve the data from the hash table. Thus hash
function isusedto implement the hash table.

Theintegerreturnedbythehashfunctioniscalledhashkey.

For example: Consider that we want place some employee records in the hash table The
recordof employee is placed with the help of key: employee ID. The employee ID is a 7 digit
numberfor placing the record in the hash table. To place the record 7 digit number is converted
into 3digitsbytakingonlylast three digitsofthe key.
th
If the key is 496700 it can be stored at 0 position. The second key 8421002, the record of
nd
thosekeyisplaced at 2 position in thearray.
Hencethehashfunctionwillbe-H(key)=key%1000
Wherekey%1000isahashfunctionandkeyobtainedbyhashfunctioniscalledhashkey.
DSUsingC++ Page39
 Bucket and Home bucket: The hash function H(key) is used to map several
dictionaryentriesinthe hashtable.Eachposition ofthe hashtable iscalledbucket.

ThefunctionH(key)ishomebucketforthedictionarywithpairwhosevalueiskey.

TYPESOFHASHFUNCTION

Therearevarioustypesofhashfunctionsthatareusedtoplacetherecordinthehashtable-

1. Division Method: The hash function depends upon the remainder

ofdivision.Typicallythe divisor istablelength.
Foreg;Ifthe record54,72, 89,37isplacedinthe hashtableand ifthetable sizeis10 then

DSUsingC++ Page40
 h(key)=record%tablesize 0

1 72
54%10=4 2
54
72%10=2 3S

89%10=9 4 37

37%10=7 5 89

8
9
2. MidSquare:
Inthemid squaremethod,thekeyis squared andthemiddleormid partoftheresult isused asthe
index. If the key is a string, it has to be preprocessed to produce a number. Consider that ifwe
wanttoplacea record3111 then
2
3111 = 9678321
for the hash table of size
1000H(3111)=783(themiddle3digit
s)

3. Multiplicativehashfunction:
Thegivenrecordismultipliedbysomeconstantvalue.Theformulaforcomputingthehashkeyis-

H(key)=floor(p*(fractionalpartofkey*A))where pisintegerconstantandAisconstantrealnumber.

DonaldKnuthsuggested to useconstantA =0.61803398987

Ifkey107andp=50then

H(key) = floor(50*(107*0.61803398987))
=floor(3306.4818458045)
=3306
At3306locationinthehashtabletherecord107willbeplaced.

4. DigitFolding:
Thekeyisdividedintoseparatepartsandusingsomesimpleoperationthesepartsarecombine
dto produce the hash key.
For eg; consider a record 12365412 then it is divided into separate parts as 123 654 12
andtheseareaddedtogether

H(key)= 123+654+12

DSUsingC++ Page41
 = 789
Therecordwillbeplacedatlocation789

5. DigitAnalysis:
Thedigitanalysisisusedinasituationwhenalltheidentifiersareknowninadvance.We first transform the identifiers into
numbers using some radix, r. Then examine the digits ofeach identifier. Some digits having most skewed distributions are
deleted. This deleting of digitsis continued until the number of remaining digits is small enough to give an address in the
rangeofthe hash table.Thenthese digitsare used tocalculatethe hashaddress.

the hash function is a function that returns the key value using which the record can be placed
inthe hash table. Thus this function helps us in placing the record in the hash table at
appropriateposition and due to this we can retrieve the record directly from that location. This
function needto bedesigned very carefully and itshould notreturn thesamehash key address for
twodifferentrecords.Thisisan undesirablesituationinhashing.

Definition: The situation in which the hash function returns the same hash key (home bucket)for more than one

Similarly when there is no room for a new pair in the hash table then such a situation
iscalled overflow. Sometimes when we handle collision it may lead to overflow
conditions.Collisionand overflowshowthe poorhash functions.
0
Forexample,
1 131
Considerahash function. 2
43
3 44

H(key)= recordkey%10 havingthehash table size of10 4 36

57
5 78
19
Therecord keysto be placed are 6

131, 44, 43, 78, 19, 36,57and 77 8

131%10=1 9
44%10=4
43%10=3
78%10=8
19%10=9
36%10=6
57%10=7
77%10=7
DSUsingC++ Page42
 Now if we try to place 77 in the hash table then we get the hash key to be 7 and at index
7already the record key 57 is placed. This situation is calledcollision. From the index 7 if
welookfornextvacantpositionatsubsequentindices8.9thenwefindthatthereisnoroomtoplace77
in thehashtable.Thissituation iscalledoverflow.

COLLISIONRESOLUTIONTECHNIQUES
Ifcollisionoccursthenitshouldbehandledbyapplyingsometechniques.Suchatechniqueiscall
ed collision handlingtechnique.
1. Chaining
2. Openaddressing(linearprobing)3
.Quadraticprobing
4. Doublehashing
5. Double
hashing6.Rehashi
ng

DSUsingC++ Page43
CHAINING

Incollisionhandlingmethodchainingisaconceptwhichintroducesanadditionalfieldwithdata i.e.
chain. A separate chain table is maintained for colliding data. When collision occursthenalinked
list(chain)ismaintainedat the home bucket.

Foreg;

Considerthekeystobeplacedintheirhomebucketsare
131, 3,4, 21, 61, 7, 97, 8, 9

thenwe willapplya hashfunction asH(key)= key

%DWhere D is the size of table. The hash table will be-

Here D= 10

0
131 21 61
1 NULL

NULL
3
131 61
7 97
NULL

NULL

A chain is maintained for colliding elements. for instance 131 has a home bucket (key)
1.similarlykey21and 61demand forhomebucket1.Hencea chainismaintained atindex 1.

OPENADDRESSING –LINEARPROBING

This is the easiest method of handling collision. When collision occurs i.e. when two
recordsdemand for the same home bucket in the hash table then collision can be solved by
placing thesecond record linearly down whenever the empty bucket is found. When use linear
probing(open addressing), the hash table is represented as a one-dimensional array with
indices thatrange from 0 to the desired table size-1. Before inserting any elements into this
table, we mustinitialize the table to represent the situation where all slots are empty. This
allows us to detectoverflows and collisions when we inset elements into the table. Then using
some suitable hashfunctionthe elementcan beinsertedinto the hashtable.

Forexample:

Considerthatfollowingkeysaretobeinsertedinthehashtable131, 4,

8, 7, 21, 5, 31,61,9, 29

DSUsingC++ Page44
 Initially,wewillputthefollowingkeysinthehashtable.

WewilluseDivisionhashfunction.Thatmeansthekeysareplacedusingtheformula

H(key) = key %
tablesizeH(key) = key%
10

Forinstancetheelement131canbeplacedatH(

key) =131 % 10
=1

Index1will bethehomebucketfor 131.Continuinginthisfashionwewillplace4,8,7.Nowthe next

keyto beinsertedis21. Accordingtothe hash function

H(key)=21%10

H(key)= 1

Buttheindex1location isalready occupiedby 131i.e.collisionoccurs.Toresolvethiscollision we will

linearly move down and at the next empty location we will prob the element.Therefore 21 will
be placed at the index 2. If the next element is 5 then we get the home bucketfor 5 asindex 5
andthisbucketisemptyso we will put theelement 5atindex5.

Index
Key Key Key
0 NULL NULL NULL

1 131 131 131

NULL 21 21
2
NULL NULL 31

3 4 4 4

NULL 5 5
4
NULL NULL 61

5 7 7 7

8 8 8
6
NULL NULL NULL
7

DSUsingC++ Page45
 8

afterplacingkeys31,61

DSUsingC++ Page46
 The next record key is 9. According to decision hash function it demands for the home bucket
9.Hence we will place 9 at index 9. Now the next final record key 29 and it hashes a key 9.
Buthome bucket 9 is already occupied. And there is no next empty bucket as the table size is
limitedto index 9. The overflow occurs. To handle it we move back to bucket 0 and is the
th
location overthereisempty29 will be placed at 0 index.
Problemwithlinearprobing:
One major problem with linear probing is primary clustering. Primary clustering is a process
inwhicha blockofdataisformed in thehash table when collisionisresolved.
Key

39
19%10 = 9 clusterisformed 29

18%10 =8 8

39%10 =9
29%10 =9
8%10 = 8

rest of the table is 18

19
emptythisclusterproblem canbesolved byquadratic probing.

QUADRATICPROBING:

Quadraticprobingoperatesbytakingtheoriginalhashvalueandaddingsuccessive
valuesofanarbitraryquadraticpolynomialtothe startingvalue.Thismethodusesfollowingformula.

wheremcanbe tablesizeor anyprime number.

2
H(key)= (Hash(key) + i ) % m)
for eg; If we have to insert following elements in the hash table with table size

10:37, 90, 55,22, 17,49,87 0 90

1 11
22
37 % 10 = 7 2

90 % 10 = 0 3 55

55 % 10 = 5 4 37
22 % 10 = 2 5

11 % 10 = 1 6
7
Nowifwe want to place17 a collision willoccuras17%10 = 7 and 8

bucket7 hasalreadyan element 37. Hencewe will apply 9

DSUsingC++ Page47
 quadraticprobingtoinsertthisrecordinthe
2
hashtable.Hi(key) = (Hash(key) + i ) % m

Consider i = 0
2
then(17 + 0 ) %10
=7

DSUsingC++ Page48
 2
(17+ 1 ) % 10 =8,wheni =1

Thebucket8isemptyhencewewillplacetheelementatindex8. 0
90
Thencomes49 which willbe placed atindex 9. 1 11
22
2

49 % 10 = 9 3
55
4
37
5 49
6
7

Nowtoplace87wewillusequadraticprobing.
0 90
(87+0)%10=7 1 11
22
(87+1)%10=8…butalready occupied 2
2
(87+2 )%10=1.. alreadyoccupied 3
55
2
(87+3 )%10=6 4 87
37
5 49
Itisobservedthatifwewantplaceallthenecessaryelements 6
inthehashtablethesizeofdivisor(m)shouldbetwiceas 7
largeastotal number ofelements. 8
9
DOUBLEHASHING
Double hashing is technique in which a second hash function is applied to the key when
acollision occurs. By applying the second hash function we will get the number of positions
fromthepoint ofcollision to insert.
There are two important rules to be followed for the second
function:itmustnever evaluateto zero.
must
makesurethatallcellscanbeprobed.Theformulato be
Key
used for doublehashingis
90
H1(key)=keymodtablesize
whereMisaprimenumbersmallerthanthesizeofthetable.
H2(key) = M– (keymodM)
22
Considerthefollowingelementstobeplacedinthehashtableofsize10 37,
90, 45, 22, 17, 49,55
45
DSUsingC++ Page49
 InitiallyinserttheelementsusingtheformulaforH1(key).Insert
37, 90, 45, 22

H1(37) = 37% 10= 7

H1(90) = 90% 10= 0
H1(45) = 45% 10= 5
H1(22) = 22% 10= 2
H1(49) = 49% 10= 9

DSUsingC++ Page50
 Nowif17 to be inserted then
Key
90
H1(17) = 17% 10 =7
17
H2(key) = M– (key% M)
22

HereMisprime numbersmallerthanthe
sizeofthetable.Primenumbersmallerthan table size 10is7
45

HenceM=7H2(17)=7

-(17%7) 37
avetotake
= 7– 3 = 4
49

Thatmeanswehavetoinserttheelement17at4placesfrom37.Inshortweh4jumps.
Thereforethe 17will beplacedatindex1.

Nowtoinsert number55
Key
H1(55) = 55% 10 =5 Collision 90

17
H2(55) = 7-(55 %7)
22
= 7– 6 = 1

Thatmeans wehavetotakeonejump fromindex5toplace55.

45
Finallythe hashtable willbe-
55

37

49

Comparisonof QuadraticProbing&DoubleHashing

Thedoublehashingrequiresanotherhashfunctionwhoseprobingefficiencyissameassomea
nother hash functionrequired when handlingrandomcollision.
The double hashing is more complex to implement than quadratic probing. The
quadraticprobingisfast techniquethan double hashing.

REHASHING

Rehashing is a technique in which the table is resized, i.e., the size of table is doubled
bycreating a new table. It is preferable is the total size of table is a prime number. There
aresituationsin which the rehashingisrequired.

DSUsingC++ Page51
 Whentableiscompletelyfull
Withquadraticprobingwhenthetableisfilledhalf.Wh
eninsertionsfailduetooverflow.

DSUsingC++ Page52
 Insuchsituations,wehavetotransferentriesfromoldtabletothenewtablebyrecomputingtheirpositi
onsusinghash functions.

Considerwehavetoinserttheelements37,90,55,22,17,49,and87.thetablesizeis10andwilluse hash
function.,

H(key)=keymodtablesize

37 % 10 =7
90 % 10=0
55 % 10= 5
22 % 10= 2
17 % 10 = 7 Collision solved by linear
probing49 % 10 = 9

Now this table is almost full and if we try to insert more elements collisions will occur
andeventually further insertions will fail. Hence we will rehash by doubling the table size. The
oldtable size is 10 then we should double this size for new table, that becomes 20. But 20 is not
aprimenumber,wewill prefertomake thetablesizeas23.Andnewhashfunctionwillbe

H(key) keymod 23 0
90
1 11
22
37 % 23 =14 2
90 % 23 =21 3
55
55 % 23 = 9 4 87
37
22 % 23 =22 5 49

17 % 23 =17 6
49 %23=3 7

87 % 23 =18 8

10

11

12

13

14

15

16

17
DSUsingC++ Page53
 18

19

20

21

22

23

Nowthehashtableissufficientlylargetoaccommodatenewinsertions.

DSUsingC++ Page54
 Advantages:

1. Thistechniqueprovidestheprogrammeraflexibilitytoenlargethetablesizeifrequired.
2. Onlythespacegetsdoubledwithsimplehashfunctionwhichavoidsoccurrenceofcollisi
ons.

EXTENSIBLEHASHING

Extensible hashing is a technique which handles a large amount of data. The data to
beplacedinthe hash table isbyextractingcertain number ofbits.
ExtensiblehashinggrowandshrinksimilartoB-trees.
Inextensiblehashingreferringthesizeofdirectorytheelementsaretobeplacedinbuckets.
Thelevelsare indicatedinparenthesis.

Foreg: Directory

0
1 Levels
0) (1)
00
1 111 data to
beplacedinbuck
01
et
0

Thebucketcanholdthedataofitsglobaldepth.Ifdatainbucketismorethanglobaldep
ththen, splitthebucketand doublethe directory.

Considerwehavetoinsert1, 4,5,7,8,10.Assumeeachpagecanhold2dataentries(2isthe depth).

Step1:Insert 1,4
1=001

4=100

We will examine last

bitofdataandinsertthedatai
nbucket.

DSUsingC++ Page55
 Insert5.Thebucketisfull.Hencedoublethedirectory.

DSUsingC++ Page56
 Thusthedataisinsertedusingextensiblehashing.

DeletionOperation:

Ifwewantotdelete 10then,simplymakethebucketof10empty.

00 01 11
1
(2) (2)
(1) 001 111
100 101
1000

Delete7.

00 01 10 11
(1) (1)
100 001 Notethatthelevelwasincreased
1000 101 whenweinsert 7.Nowondeletion
of7,thelevelshouldgetdecremented.

Delete8.Removeentryfromdirectory00.

0 (1) 00 (1) 1 1
100 00
1

10
1

DSUsingC++ Page57
 Applicationsof hashing:

1. Incompilerstokeeptrackofdeclaredvariables.
2. Foronlinespellingcheckingthehashingfunctionsareused.
3. HashinghelpsinGameplayingprogramstostorethemovesmade.
4. Forbrowserprogramwhilecachingthewebpages,hashingisused.
5. Constructamessage authenticationcode(MAC)
6. Digitalsignature.
7. Timestamping
8. Keyupdating:keyishashedatspecificintervalsresultinginnewkey

COMPARISONOF HASHING&SKIPLISTS

Hashing SkipList

This method is used to carry out Skiplistsareusedtoimplementdictionaryope

dictionaryoperationsusingrandomizedproc rationsusingrandomizedprocess.
esses.

Itisbasedonhashfunction Itdoesnotrequirehashfunction

Ifthesorted dataisgiven Thesorteddataimprovestheperformanceofs

thenhashingisnotaneffectivemethodtoim kiplist.
plement
dictionary.

The space requirement in hashing is The forward pointers are required for
forhashtableandaforwardpointerisrequired everylevelofskip list.
per node.

Hashingisanefficientmethodthanskiplist Theskiplistsarenot thatmushefficient.

s.

Skiplistsaremoreversatilethanhashtabl Worstcasespacerequirementislargerforski
e. plistthan hashing.

DSUsingC++ Page58
UNIT IV:
Priority queues- Definition, ADT, realizing a Priority Queue Using Heaps, Definition, Insertion, Deletion. Search Trees- Binary
Search Trees, Definition, ADT, Implementation, Operations Searching, Insertion, Deletion.

Priority
QueueDEFINITI
ON:
Apriorityqueueisacollectionofzero ormoreelements.Eachelementhasapriorityorvalue.
Unlikethequeues,whichareFIFOstructures,theorderofdeletingfrom
apriorityqueueisdeterminedbytheelement priority.
Elementsareremoved/
deletedeitherinincreasingordecreasingorderofpriorityratherthanintheorderinwhichtheyarrived in thequeue.
Thereare two typesofpriorityqueues:
Minpriorityqueue

Maxpriorityqueue

Minpriorityqueue:Collectionofelementsinwhichtheitemscanbeinsertedarbitrarily,butonlysmallestelementca
n be removed.

Max priority queue: Collection of elements in which insertion of items can be in any order but only
largestelementcan be removed.
Inpriorityqueue,theelementsarearrangedinanyorderandoutofwhichonlythesmallestorlargestelement
allowedto deleteeachtime.
The implementation of priority queue can be done using arrays or linked list. The data structure heap
isusedto implement the priorityqueueeffectively.
DSUsingC++ Page59
APPLICATIONS:
1. The typical example of priority queue is scheduling the jobs in operating system. Typically OS
allocatespriority to jobs. The jobs are placed in the queue and position of the job in priority queue
determines theirpriority. In OS there are 3 jobs- real time jobs, foreground jobs and background jobs. The
OS alwaysschedules the real time jobs first. If there is no real time jobs pending then it schedules
foreground jobs.Lastlyifnoreal timeandforeground jobsarependingthenOSschedulesthebackground jobs.
2. Innetworkcommunication,themanagelimitedbandwidthfortransmissionthepriorityqueueisused.
3. Insimulationmodelingtomanagethediscreteeventsthepriorityqueueisused.Vario
usoperationsthat can be performed on priorityqueueare-
1. Findanelement
2. Insertanewelement
3. Removeordeleteanelement
The abstract data type specification for a max priority queue is given below. The specification for a min
priorityqueueisthesameasordinaryqueueexceptwhiledeletion,findandremovetheelementwithminimumpriority

ABSTRACTDATATYPE(ADT):
AbstractdatatypemaxPriorityQueue
{
Instances
Finite collection of elements, each has a
priorityOperationsempty():returntrueiffthequeueise
mptysize():returnnumber ofelementsin thequeue
top():returnelementwithmaximumpriority
del():removetheelementwithlargestpriorityfromthequeueinsert(x):in
sert the elementx into thequeue
}

DSUsingC++ Page60
HEAPS

Heapisatree datastructuredenoted byeithera maxheaporaminheap.

Amaxheapis atreein whichvalue ofeachnodeisgreaterthan orequal tovalue ofitschildren nodes.Aminheap

is atreein which valueof each nodeisless than or equalto valueofits children nodes.

18 4

12 4 12 14

11 10 18 20

Max heap Minheap

InsertionofelementintheHeap:

Consideramaxheapasgiven below:

Nowifwewanttoinsert7.
Wecannotinsert7asleftchildof4.Thisisbecausethemaxheaphasapropertythatvalueofanynode isalways greaterthan
theparentnodes.Hence 7willbubbleup 4willbeleft childof7.
Note:Whena newnode isto beinsertedincompletebinarytreewe startfrombottomand
fromleftchildonthecurrent level.Theheap isalwaysa complete binarytree.

DSUsingC++ Page61
 18

12 7 inserted!

11
10 4

Ifwewanttoinsertnode25,thenas25isgreatestelementitshouldbetheroot.Hence25willbubbleupand18willmove
down.
25 inserted!

12 18

11
10 4

Theinsertionstrategyjustoutlinedmakesa single bubblingpass fromaleaftowardtheroot. Ateachlevelwedo

(1)work, so weshould beable to implement thestrategyto havecomplexityO(height)=O(logn).

voidHeap::insert(intitem)
{
int //tempnodestarts atleafandmovesup.
temp;temp=+
+size;
while(temp!=1&&heap[temp/2]<item) //movingelementdown
{
H[temp] =H[temp/2];temp=temp/2;
//findingtheparent
}
H[temp]=item;
}

DSUsingC++ Page62
Deletionof elementfromtheheap:

Fordeletionoperationalwaysthemaximumelementisdeletedfromheap.InMaxheapthemaximumelementisal
wayspresent atroot.And ifrootelement isdeletedthenwe needtoreheapifythetree.

ConsideraMaxheap

25

12 18

11
10 4

Deleterootelement:25,Nowwecannotputeither12or18asrootnodeandthatshouldbegreaterthanallitschildrenelem
ents.

18

12
4

11 10

Nowwecannot put4at therootasitwillnot satisfytheheap property.Hencewe willbubbleup 18andplace 18at

root,and 4at positionof18.

If18getsdeletedthen12becomesrootand11becomesparentnodeof10.

Thusdeletionoperationcan beperformed.Thetimecomplexityofdeletion operationisO(logn).

1. Removethemaximumelementwhichispresentattheroot.Thenaholeiscreatedattheroot.
2. Nowreheapifythetree.Startmovingfromroottochildrennodes.Ifanymaximumelementisfoundthenplaceit
atroot.Ensurethat thetree issatisfyingthe heap propertyor not.
3. Repeatthe step1 and 2ifanymoreelementsaretobe deleted.

DSUsingC++ Page63
voidheap::delet(intitem)

int item,
temp;if(size==
0)
cout<<‖Heapisempty\n‖;else
{
//
removethelastelemntandreheapifyite
m=H[size--];

DSUsingC++ Page64
//item is placed at root
temp=1;child=2;
while(child<=size)
{

Fordeletionoperationalwaysthemaximumelementisdeletedfromheap.InMaxheapthemaximumelementisal
wayspresent atroot.And ifrootelement isdeletedthenwe needtoreheapifythetree.

ConsideraMaxheap

25

12 18

11
10 4

Deleterootelement:25,Nowwecannotputeither12or18asrootnodeandthatshouldbegreaterthanallitschildrenelem
ents.

18

12
4

11 10

Nowwecannot put4at therootasitwillnot satisfytheheap property.Hencewe willbubbleup 18andplace 18at

root,and 4at positionof18.

If18getsdeletedthen12becomesrootand11becomesparentnodeof10.

Thusdeletionoperationcan beperformed.Thetimecomplexityofdeletion operationisO(logn).

4. Removethemaximumelementwhichispresentattheroot.Thenaholeiscreatedattheroot.
5. Nowreheapifythetree.Startmovingfromroottochildrennodes.Ifanymaximumelementisfoundthenplaceit
atroot.Ensurethat thetree issatisfyingthe heap propertyor not.
6. Repeatthe step1 and 2ifanymoreelementsaretobe deleted.

voidheap::delet(intitem)

int item,
DSUsingC++ Page65
temp;if(size==
0)
cout<<‖Heapisempty\n‖;else
{
//
removethelastelemntandreheapifyite
m=H[size--];
//itemisplacedatroottemp=1;

DSUsingC++ Page66
child=2;while(chil
d<=size)
{
if(child<size&&H[child]<H[child+1])child+
+;if(item>=H[child])
break;
H[temp]=H[child];t
emp=child;child=c
hild*2;
}
//
pl;acethelargestitematrootH[t
emp]=item;
}

ApplicationsOf Heap:

1. Heapisusedin sortingalgorithms.Onesuchalgorithmusingheap isknownasheapsort.

2. Inpriorityqueueimplementationtheheapisused.

HEAPSORT

Heap sort is a method in which a binary tree is used. In this method first the heap is created using binary tree and
thenheapissorted usingpriorityqueue.

Eg:

25 57 48 38 10 91 84 33

In the heap sort methodwe first take all these elementsin the array―A‖

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]

25 57 48 38 10 91 84 33

Nowstartbuildingtheheap structure.Informingtheheapthekeypointisbuildheapin sucha

waythatthehighest value in thearraywillalwaysbe a root.

Insert25
+
Thenextelementis84,which91>84>57themiddleelement.So84willbetheparentof57.Formakingthecompl
ete binarytree 57 will beattachedasrightof84.

DSUsingC++ Page50
Now the heap is formed. Let us sort it. For sorting the heap remember two main things the first thing is that
thebinarytreeformoftheheapshouldnotbedistributedatall.Forthecompletesortingbinarytreeshouldberemained.Andt
he second thingisthat wewill start sortingthehigher elementsattheendofarrayin sorted manneri.e..
A[7]=91, A[6]=84 and soon..
Step1:-ExchangeA[0]with A[7]

DSUsingC++ Page51
DSUsingC++ Page52
ep5:-ExchaneA[0]withA[2]

DSUsingC++ Page53
 //
Iflargestisnotrootif
(largest!=i)
{

swap(&arr[i],&arr[largest]);

// Recursively heapify the affected

sub-treeheapify(arr,n, largest);
}
}

//function to do heap
sortvoidheapSort(intarr[],int
n)
{inti;
//Buildheap(rearrangearray)for(i=
n/2-1; i>= 0;i--)

heapify(arr,n,i);

// One by one extract an element

fromheap for ( i=n-1;i>=0;i--)
{
//
Movecurrentroottoendswa
p(&arr[0],&arr[i]);

//
callmaxheapifyonthereducedheaphea
pify(arr,i, 0);
}
}
/* A utility function to print array of size n
*/voidprintArray(int arr[], int n)
{
for(inti=0;i<n;+
+i)cout<<arr[i]<<"";
cout<<"\n";
}
intmain()
{
intn,i;

DSUsingC++ Page54
intlist[30];
cout<<"enter no of elements\
n";cin>>n;

cout<<"enter "<<n<<" numbers

";for(i=0;i<n;i++)
cin>>list[i];heap
Sort(list,n);

cout<< "Sorted array is \

n";printArray(list,n);
return0;
}

BINARYSEARCHTREE
Inthesimplebinarytreethenodesarearrangedinanyfashion.Dependingonuser‘sdesirethe new
nodes can be attached as a left or right child of any desired node. In such a case finding
foranynodeisalongcutprocedure,becauseinthatcasewehavetosearchtheentiretree.Andthusthesearchin
gtimecomplexitywillgetincreasedunnecessarily.Sotomakethesearchingalgorithmfasterinabinarytree
wewillgoforbuildingthebinarysearchtree.Thebinarysearchtreeisbasedonthebinarysearchalgorithm.
Whilecreatingthebinarysearchtreethedataissystematically arranged. That means values at left sub-
tree < root node value < right sub-treevalues.

DSUsingC++ Page55
OperationsOnBinarySearchTree:
Thebasic operations which can beperformed on binarysearch treeare.
1. Insertionof anodeinbinarysearch tree.
2. Deletionofanode frombinarysearchtree.
3. Searchingforaparticular nodein binarysearch tree.
Insertionof anodeinbinarysearchtree.
While inserting any node in binary search tree, look for its appropriate position in the binary
searchtree. We start comparing this new node with each node of the tree. If the value of the node
which isto be inserted is greater than the value of the current node we move on to the right sub-
branchotherwisewemoveontotheleftsub-
branch.Assoonastheappropriatepositionisfoundweattachthis newnodeas left orright child
appropriately.

BeforeInsertion

Intheabovefig,ifwewantoinsert23.Thenwewillstartcomparing23withvalueofrootnode
i.e.10.As23isgreaterthan10,wewillmoveonrightsub-tree.Nowwewillcompare23with20andmove
right,compare23 with22 and moveright. Nowcompare23 with 24but it isless than
24. Wewillmove onleftbranch of24. Butasthereisnodeas leftchildof 24, wecanattach23asleftchild
of 24.

DSUsingC++ Page56
Deletionofanodefrombinarysearchtree.
Fordeletionofanynodefrombinarysearchtreethere arethree whicharepossible.
i. Deletionofleafnode.
ii. Deletionofa nodehavingonechild.
iii. Deletionofanodehavingtwo children.
Deletionofleafnode.

Thisisthesimplestdeletion,inwhichwesettheleftorrightpointerofparentnodeasNULL.

10

7 15

Beforedeletion

5 9 12 18

Fromtheabovefig,wewanttodeletethenodehavingvalue5thenwewillsetleftpointerofitsparentnodeasNU
LL. That isleft pointer ofnode havingvalue 7issettoNULL.

DSUsingC++ Page57
Deletionof anodehavingonechild.

Toexplainthiskindofdeletion,consideratreeasgivenbelow.

If we want to delete the node 15, then

wewill simply copy node 18 at place of
16andthen set thenodefree

Deletionof anodehavingtwochildren.

Consideratree asgiven below.

DSUsingC++ Page58
Letusconsiderthatwewanttodeletenodehavingvalue7.Wewillthenfindouttheinordersuccessorof node
7. We will then find out the inorder successor of node 7. The inorder successor will be
simplycopiedatlocation ofnode7.
Thatmeanscopy8at thepositionwhere valueofnodeis7. Setleft pointerof9asNULL.
Thiscompletesthedeletion procedure.

Searchingforanodeinbinary searchtree.
In searching, the node which we want to search is called a key node. The key node will be
comparedwith each node starting from root node if value of key node is greater than current node
then
wesearchforitonrightsubbranchotherwiseonleftsubbranch.Ifwereachtoleafnodeandstillwedonot get
the value ofkeynode then we declare ―node isnot present in the tree‖.

DSUsingC++ Page59
 In the above tree, if we want to search for value 9. Then we will compare 9
with root node 10. As 9is less than 10 we will search on left sub branch.
Now compare 9 with 5, but 9 is greater than 5.
Sowewillmoveonrightsubtree.Nowcompare9with8but9isgreaterthan8wew
illmoveonrightsubbranch.Asthenode
wewillgetholdsthevalue9.Thusthedesirednodecanbesearched.

DSUsingC++ Page60
UNIT-5:
Search Trees- AVL Trees, Definition, Height of AVL Tree, Operations-, Insertion, Deletion and
Searching, Introduction to Red-Black and Splay Trees, B-Trees, Height of B-Tree, Insertion, Deletion
and Searching, Comparison of Search Tree

AVL TREES:

AVL Tree Data structure

AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary

search tree but it is a balanced tree. A binary tree is said to be balanced if, the difference

between the heights of left and right subtrees of every node in the tree is either -1, 0 or +1.

In other words, a binary tree is said to be balanced if the height of left and right children of

every node differs by either -1, 0 or +1. In an AVL tree, every node maintains an extra

information known as balance factor. The AVL tree was introduced in the year 1962 by

G.M. Adelson-Velsky and E.M. Landis.

An AVL tree is defined as follows...

An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every
node is either -1, 0 or +1.

Balance factor of a node is the difference between the heights of the left and right subtrees
of that node. The balance factor of a node is calculated either height of left subtree -
height of right subtree (OR) height of right subtree - height of left subtree. In the
following explanation, we calculate as follows...

Balance factor = heightOfLeftSubtree - heightOfRightSubtree

DSUsingC++ Page61
Example of AVL Tree

The above tree is a binary search tree and every node is satisfying balance factor condition.
So this tree is said to be an AVL tree.

Every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL
tree.

AVL Tree Rotations

In AVL tree, after performing operations like insertion and deletion we need to check
the balance factor of every node in the tree. If every node satisfies the balance factor
condition then we conclude the operation otherwise we must make it balanced. Whenever
the tree becomes imbalanced due to any operation we use rotation operations to make the
tree balanced.

Rotation operations are used to make the tree balanced.

Rotation is the process of moving nodes either to left or to right to make the tree
balanced.

There are four rotations and they are classified into two types.

DSUsingC++ Page62
Single Left Rotation (LL Rotation)
In LL Rotation, every node moves one position to left from the current position. To
understand LL Rotation, let us consider the following insertion operation in AVL Tree...

Single Right Rotation (RR Rotation)

In RR Rotation, every node moves one position to right from the current position. To
understand RR Rotation, let us consider the following insertion operation in AVL Tree...

DSUsingC++ Page63
Left Right Rotation (LR Rotation)
The LR Rotation is a sequence of single left rotation followed by a single right rotation. In LR
Rotation, at first, every node moves one position to the left and one position to right from
the current position. To understand LR Rotation, let us consider the following insertion
operation in AVL Tree...

Right Left Rotation (RL Rotation)

The RL Rotation is sequence of single right rotation followed by single left rotation. In RL
Rotation, at first every node moves one position to right and one position to left from the
current position. To understand RL Rotation, let us consider the following insertion
operation in AVL Tree...

Height of an AVL Tree

Let N(h) be the minimum number of nodes in an AVL tree of height hℎ. We can
say that N(0)=1 and N(1)=2.
DSUsingC++ Page64
Let there be a node with a height hℎ and one of its child has a height
of h−1ℎ−1, then for an AVL tree, the minimum height of the other child will
be h−2ℎ−2.

It means that the minimum number of nodes at height hℎ will be the sum of
the minimum number of nodes at heights h−1ℎ−1 and h−2ℎ−2 + 1 (the node
itself).

Let's learn about the insertion and deletion in an AVL tree.

DSUsingC++ Page65
Operations on an AVL Tree
The following operations are performed on AVL tree...

1. Search
2. Insertion
3. Deletion

Search Operation in AVL Tree

In an AVL tree, the search operation is performed with O(log n) time complexity. The search
operation in the AVL tree is similar to the search operation in a Binary search tree. We use
the following steps to search an element in AVL tree...

 Step 1 - Read the search element from the user.

 Step 2 - Compare the search element with the value of root node in the tree.
 Step 3 - If both are matched, then display "Given node is found!!!" and terminate the
function
 Step 4 - If both are not matched, then check whether search element is smaller or
larger than that node value.
 Step 5 - If search element is smaller, then continue the search process in left
subtree.
 Step 6 - If search element is larger, then continue the search process in right
subtree.
 Step 7 - Repeat the same until we find the exact element or until the search element
is compared with the leaf node.
 Step 8 - If we reach to the node having the value equal to the search value, then
display "Element is found" and terminate the function.
 Step 9 - If we reach to the leaf node and if it is also not matched with the search
element, then display "Element is not found" and terminate the function.

Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL
Tree, a new node is always inserted as a leaf node. The insertion operation is performed as
follows...

 Step 1 - Insert the new element into the tree using Binary Search Tree insertion logic.
 Step 2 - After insertion, check the Balance Factor of every node.
 Step 3 - If the Balance Factor of every node is 0 or 1 or -1 then go for next
operation.
 Step 4 - If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is
said to be imbalanced. In this case, perform suitable Rotation to make it balanced
and go for next operation.

DSUsingC++ Page66
Example: Construct an AVL Tree by inserting
numbers from 1 to 8.

DSUsingC++ Page67
DSUsingC++ Page68
Deletion Operation in AVL Tree

Deletion in AVL Tree

In deletion also, we delete the node to be deleted in the same way as we do

with a normal binary search tree. After that, we fix the unbalance of any
ancestor node with suitable rotations. The only thing is that unlike insertion, it
might be possible that the unbalance propagates above the tree in deletion
which makes us rebalance the ancestor nodes. Let's look at some examples of
deletion and then the reason for the same will be clear.
As we have already discussed, there can be three cases of deletion - the node to
be deleted has no child, the node to be deleted has one child or the node to be
deleted has 2 children. In the third case when the node has 2 children, we
replace the content of the nodes with its successor and it reduces to the
deletion of the node with either one child or none.
After the deletion procedure, the heights of ancestor nodes will decrease and
this may cause unbalance in the tree. Let's look at the loss of balances that can
happen and how to fix them.
Let's assume that the first ancestor which is unbalanced is x and y is its child
with greater height among the heights of the two children of x. And z is the
child of y with greater height among the children of y.

DSUsingC++ Page69
We fix the unbalancing by performing the required rotations involving the
nodes x, y and z as we did in the insertion part.
Let's talk about the outside case first in which the node x is unbalanced because
of the deletion of a node from the subtree a.

The height of the subtree a is h before deletion and the node x is balanaced.
Since x is balanced, it means that the height of the node y can be h, h-1 or h+1.
But after deletion, the height of the subtree a is changed to h-1 and the
node x is unbalanced now. It means that the only possible height of the
node y can be h+1.
Since z is the child of y with larger height, so its height will be h. As y is balanced,
the height of b will be either h or h-1.
The heights of the nodes c and d can be either h-1 or h-2. However, one of these
must have a height of h-1 because the height of node x is h.
After deletion, the height of the node a changed to h-1 and thus caused the
unbalance on the node x. To fix this, we have performed a right rotation on the
node x as we did in insertion.

Now, the node y is the root of the subtree. Initially, this subtree has a height
of h+2 but now it has a height of h+1 or h+2. If it is changed to h+1, it might
DSUsingC++ Page70
have caused unbalance somewhere in its ancestor. In this way, the unbalance
propagates above the tree in deletion.
Let's take deletion of inside case.

Let's perform the rotations to fix this.

Node z is now the root of the subtree with a height of h+1 which initially
was h+2, so we need to check further if any ancestor requires any balancing or
not.
One thing should be noted that the subtree d can have a height of either h-
1 or h. But if it is h (equal to its sibling), then both children of y have same
heights and there isn't a taller child. In that case, we will pick the root of the
subtree d as z which will lead to the outside case and thus requiring only one
rotation to fix the unbalance. However, the reason for picking the root of the
subtree d as z and going for the outside case is not to fix the unbalance in a
single rotation only but if we would have picked the other node and gone for

DSUsingC++ Page71
the double rotation (inside case), then it wouldn't fix the unbalance. This is
shown in the following picture.

RED BLOCK TREES:

Red - Black Tree Datastructure

Red - Black Tree is another variant of Binary Search Tree in which every node is colored

either RED or BLACK. We can define a Red Black Tree as follows...

Red Black Tree is a Binary Search Tree in which every node is colored either RED or

BLACK.

n Red Black Tree, the color of a node is decided based on the properties of Red-Black Tree.
Every Red Black Tree has the following properties.

Properties of Red Black Tree

 Property #1: Red - Black Tree must be a Binary Search Tree.
 Property #2: The ROOT node must be colored BLACK.
 Property #3: The children of Red colored node must be colored BLACK. (There
should not be two consecutive RED nodes).
 Property #4: In all the paths of the tree, there should be same number of BLACK
colored nodes.
 Property #5: Every new node must be inserted with RED color.
 Property #6: Every leaf (e.i. NULL node) must be colored BLACK.

DSUsingC++ Page72
Example
Following is a Red-Black Tree which is created by inserting numbers from 1 to 9.

The above tree is a Red-Black tree where every node is satisfying all the properties of Red-
Black Tree.

Every Red Black Tree is a binary search tree but every Binary Search Tree need not be
Red Black tree.

Insertion into RED BLACK Tree

In a Red-Black Tree, every new node must be inserted with the color RED. The insertion
operation in Red Black Tree is similar to insertion operation in Binary Search Tree. But it is
inserted with a color property. After every insertion operation, we need to check all the
properties of Red-Black Tree. If all the properties are satisfied then we go to next operation
otherwise we perform the following operation to make it Red Black Tree.

 1. Recolor
 2. Rotation
 3. Rotation followed by Recolor

The insertion operation in Red Black tree is performed using the following steps...

 Step 1 - Check whether tree is Empty.

 Step 2 - If tree is Empty then insert the newNode as Root node with color Black and
exit from the operation.

 Step 3 - If tree is not Empty then insert the newNode as leaf node with color Red.

DSUsingC++ Page73
  Step 4 - If the parent of newNode is Black then exit from the operation.

 Step 5 - If the parent of newNode is Red then check the color of parentnode's sibling
of newNode.

 Step 6 - If it is colored Black or NULL then make suitable Rotation and Recolor it.

 Step 7 - If it is colored Red then perform Recolor. Repeat the same until tree
becomes Red Black Tree.

DSUsingC++ Page74
Example

Red-Black Trees | Deletion

DSUsingC++ Page75
The deletion process in a red-black tree is also similar to the deletion process of
a normal binary search tree. Similar to the insertion process, we will make a
separate function to fix any violations of the properties of the red-black tree.

Just go through the DELETE function of binary search trees because we are going
to develop the code for deletion on the basis of that only. After that, we will
develop the code to fix the violations.
Let's recap the delete procedure of binary search tree.

DSUsingC++ Page76
In the first two cases when z has less than two children, x is taking the position
of y/z.
In the next two cases, y is the minimum of the right subtree of z and x is again
taking y's position. We are also replacing the node z with y but we are recoloring
it to the original color of z.
Any violations of properties of red-black can only happen because of x taking
the position of y. So, we will store the original color of y along the process and
use it to see if any property is violated during the process or not.

For x taking the position of y:

 Property 1 can't be violated.

DSUsingC++ Page77
  Property 2 can be violated if y is root and x taking its position is red. In
this case, the original color of y will be black.
 Property 3 is not going to be violated.
 Property 4 can be violated only if the parent and child (x) of y are red. In
this case also, the original color of y will be black and after removing it,
there will be two consecutive reds.
 Property 5 can also be violated only if y is black because removing it will
affect the black height of the nodes.

Take a note that any violation is going to happen if the original color of y was
black and we will use this as the condition to run the code for fixing the
violation.
The above claim can also be justified as if y was red:

 removing it is not going to affect the black height

 if it was red, then it can't be the root, so root is still black
 no red nodes are made consecutive

Splay Tree Datastructure

Splay tree is another variant of a binary search tree. In a splay tree, recently accessed

element is placed at the root of the tree. A splay tree is defined as follows...

Splay Tree is a self - adjusted Binary Search Tree in which every operation on element

rearranges the tree so that the element is placed at the root position of the tree.

In a splay tree, every operation is performed at the root of the tree. All the operations in
splay tree are involved with a common operation called "Splaying".

DSUsingC++ Page78
 Splaying an element, is the process of bringing it to the root position by performing
suitable rotation operations.

In a splay tree, splaying an element rearranges all the elements in the tree so that splayed
element is placed at the root of the tree.

By splaying elements we bring more frequently used elements closer to the root of the tree
so that any operation on those elements is performed quickly. That means the splaying
operation automatically brings more frequently used elements closer to the root of the tree.

Every operation on splay tree performs the splaying operation. For example, the insertion
operation first inserts the new element using the binary search tree insertion process, then
the newly inserted element is splayed so that it is placed at the root of the tree. The search
operation in a splay tree is nothing but searching the element using binary search process
and then splaying that searched element so that it is placed at the root of the tree.

In splay tree, to splay any element we use the following rotation operations...

Rotations in Splay Tree

 1. Zig Rotation
 2. Zag Rotation
 3. Zig - Zig Rotation
 4. Zag - Zag Rotation
 5. Zig - Zag Rotation
 6. Zag - Zig Rotation

Example

Zig Rotation
The Zig Rotation in splay tree is similar to the single right rotation in AVL Tree rotations. In
zig rotation, every node moves one position to the right from its current position. Consider
the following example...

Zag Rotation
DSUsingC++ Page79
The Zag Rotation in splay tree is similar to the single left rotation in AVL Tree rotations. In
zag rotation, every node moves one position to the left from its current position. Consider
the following example...

Zig-Zig Rotation
The Zig-Zig Rotation in splay tree is a double zig rotation. In zig-zig rotation, every node
moves two positions to the right from its current position. Consider the following example...

Zag-Zag Rotation
The Zag-Zag Rotation in splay tree is a double zag rotation. In zag-zag rotation, every node
moves two positions to the left from its current position. Consider the following example...

Zig-Zag Rotation

DSUsingC++ Page80
The Zig-Zag Rotation in splay tree is a sequence of zig rotation followed by zag rotation. In
zig-zag rotation, every node moves one position to the right followed by one position to the
left from its current position. Consider the following example...

Zag-Zig Rotation
The Zag-Zig Rotation in splay tree is a sequence of zag rotation followed by zig rotation. In
zag-zig rotation, every node moves one position to the left followed by one position to the
right from its current position. Consider the following example...

Every Splay tree must be a binary search tree but it is need not to be balanced tree.

Insertion Operation in Splay Tree

The insertion operation in Splay tree is performed using following steps...

 Step 1 - Check whether tree is Empty.

 Step 2 - If tree is Empty then insert the newNode as Root node and exit from the
operation.

 Step 3 - If tree is not Empty then insert the newNode as leaf node using Binary
Search tree insertion logic.

DSUsingC++ Page81
  Step 4 - After insertion, Splay the newNode

Deletion in a Splay Tree

 To delete a node in a splay tree, we first splay that node to the root.

 After this, we just delete the root which gives us two subtrees.

 We find the largest element of the left subtree and splay it to the root.

 Lastly, we attach the right subtree as the right child of the left subtree.

DSUsingC++ Page82
B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of
order m can have at most m-1 keys and m children. One of the main reason of using
B tree is its capability to store large number of keys in a single node and large key
values by keeping the height of the tree relatively small.

A B tree of order m contains all the properties of an M way tree. In addition, it

contains the following properties.

1. Every node in a B-Tree contains at most m children.

2. Every node in a B-Tree except the root node and the leaf node contain at least m/2
children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.

It is not necessary that, all the nodes contain the same number of children but, each
node must have m/2 number of nodes.

A B tree of order 4 is shown in the following image.

While performing some operations on B Tree, any property of B Tree may violate
such as number of minimum children a node can have. To maintain the properties of
B Tree, the tree may split or join.

Operations

DSUsingC++ Page83
Searching:
Searching in B Trees is similar to that in Binary search tree. For example, if we search
for an item 49 in the following B Tree. The process will something like

following:

1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.

Searching in a B tree depends upon the height of the tree. The search algorithm
takes O(log n) time to search any element in a B tree.

Inserting
Insertions are done at the leaf node level. The following algorithm needs to be
followed in order to insert an item into B Tree.

1. Traverse the B Tree in order to find the appropriate leaf node at which the node can
be inserted.
2. If the leaf node contain less than m-1 keys then insert the element in the increasing
order.
3. Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
o Split the node into the two nodes at the median.
o Push the median element upto its parent node.
DSUsingC++ Page84
 o If the parent node also contain m-1 number of keys, then split it too by
following the same steps.

Example:

ADVERTISEMENT

Insert the node 8 into the B Tree of order 5 shown in the following image.

8 will be inserted to the right of 5, therefore insert 8.

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore, split
the node from the median i.e. 8 and push it up to its parent node shown as follows.

Deletion
Deletion is also performed at the leaf nodes. The node which is to be deleted can
either be a leaf node or an internal node. Following algorithm needs to be followed
in order to delete a node from a B tree.

1. Locate the leaf node.

DSUsingC++ Page85
 2. If there are more than m/2 keys in the leaf node then delete the desired key from the
node.
3. If the leaf node doesn't contain m/2 keys then complete the keys by taking the
element from eight or left sibling.
o If the left sibling contains more than m/2 elements then push its largest
element up to its parent and move the intervening element down to the node
where the key is deleted.
o If the right sibling contains more than m/2 elements then push its smallest
element up to the parent and move intervening element down to the node
where the key is deleted.
4. If neither of the sibling contain more than m/2 elements then create a new leaf node
by joining two leaf nodes and the intervening element of the parent node.
5. If parent is left with less than m/2 nodes then, apply the above process on the parent
too.

If the the node which is to be deleted is an internal node, then replace the node with
its in-order successor or predecessor. Since, successor or predecessor will always be
on the leaf node hence, the process will be similar as the node is being deleted from
the leaf node.

Example 1

Delete the node 53 from the B Tree of order 5 shown in the following figure.

ADVERTISEMENT

53 is present in the right child of element 49. Delete it.

DSUsingC++ Page86
Now, 57 is the only element which is left in the node, the minimum number of
elements that must be present in a B tree of order 5, is 2. it is less than that, the
elements in its left and right sub-tree are also not sufficient therefore, merge it with
the left sibling and intervening element of parent i.e. 49.

The final B tree is shown as follows.

Application of B tree
B tree is used to index the data and provides fast access to the actual data stored on
the disks since, the access to value stored in a large database that is stored on a disk
is a very time consuming process.

Searching an un-indexed and unsorted database containing n key values needs O(n)
running time in worst case. However, if we use B Tree to index this database, it will be
searched in O(log n) time in worst case.

Comparison of Search Trees in Data

Structure
Here we will see some search trees and their differences. There are many
different search trees. They are different in nature. The basic search tree is
Binary Search Tree (BST). Some other search trees are AVL tree, B tree,
Red-Black tree, splay tree etc.

DSUsingC++ Page87
These trees can be compares based on their operations. We will see the time
complexity of these trees

Search Tree Average Case

Insert Delete Search

Binary Search Tree O(log n) O(log n) O(log n)

AVL tree O(log2 n) O(log2 n) O(log2 n)

B Tree O(log n) O(log n) O(log n)

Red-Black Tree O(log n) O(log n) O(log n)

Splay Tree O(log2 n) O(log2 n) O(log2 n)

Search Tree Worst Case

Insert Delete Search

Binary Search Tree O(n) O(n) O(n)

AVL tree O(log2 n) O(log2 n) O(log2 n)

B Tree O(log n) O(log n) O(log n)

Red-Black Tree O(log n) O(log n) O(log n)

Splay Tree O(log2 n) O(log2 n) O(log2 n)

DSUsingC++ Page88