UNIT-I

Data structure A data structure is a specialized formatfororganizingandstoringdata. General

datastructure types include the array,the file,the record,thetable,the tree,andso on. Any data structure
s designed to organize data to suit a specific purpose so that it can be accessed and worked with in
appropriateways
AbstractDataType
In computer science, an abstract data type (ADT) is a mathematical model for data types
where adata type isdefinedbyitsbehavior(semantics)fromthepointofviewofauser
ofthedata,specificallyintermsofpossiblevalues,possible operationsondataofthistype, and the behavior
of these operations. When a class is used as a type,itis anabstract typethat refersto a hidden
[Link] thismodel an ADTis typically implemented as a class, and each instance of the
ADT is usually a n object of thatclass.
InADTalltheimplementationdetailsarehidden

 Lineardata structuresarethedatastructuresinwhichdata isarrangedina listor ina

sequence.
 Nonlinear data structuresarethedata structures inwhichdatamaybe arrangedina
hierarchic al manner
LISTADT
Listisbasicallythecollectionof [Link] wecan
storethelist in twoways:one wayiswecanstorethe elementsinsequential memory locations. That
means we can store the list in arrays.
The other way is we can use pointers or links to associate elements sequentially.
This is known as linked list.

LINKEDLISTS
The linked list is very different type of collection from an array. Using such lists, we can
storecollections ofinformation limitedonly by thetotalamount of memorythat theOSwillallow us
[Link] more, there is no need tospecify our needs inadvance. The linked list isvery
flexibledynamic datastructure:items maybe addedtoitor deletedfromitat will. Aprogrammer need
not worry about how many items a program will have to accommodate inadvance. This allows us
to write robust programs which require much lessmaintenance.

[Type text]
 Thelinkedallocationhasthefollowingdrawbacks:
1. Nodirectaccesstoaparticularelement.
2. Additionalmemoryrequiredforpointers.

Linkedlistareof3types:
1. SinglyLinkedList
2. DoublyLinkedList
3. CircularlyLinkedList

SINGLYLINKEDLIST
A singly linked list, or simply a linked list, isa linear collection of data items. The linear order is
given bymeansof [Link] typesof lists are often referred to as linearlinkedlist.
* Eachiteminthelistiscalledanode.
* Eachnodeofthelisthastwofields:
1. Information-containstheitembeingstoredinthelist.
2. Nextaddress-containstheaddressofthenextiteminthelist.
*ThelastnodeinthelistcontainsNULLpointertoindicatethatitistheendofthelist.

ConceptualviewofSinglyLinkedList

OperationsonSinglylinked list:
 Insertionofanode
 Deletionsofanode
 Traversing thelist

Structure of a node:

Method -1:

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

Method-2:

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

[Type text]
 Insertions:Toplaceanelementsinthelistthereare3cases:
1. Atthebeginning
2. Endof thelist
3. Atagivenposition

case1:Insertatthebeginning

temp

head is the pointer variable which contains address of the first node andtemp contains address of
new node to be inserted then sample codeis
temp->link=head; head=temp;

Afterinsertion:

Codeforinsertfront:-
template<class T>
void list<T>::insert_front()
{
structnode<T>*t,*temp;
cout<<"Enterdataintonode:";
cin>>item;
temp=create_node(item);
if(head==NULL)
head=temp;
else
{ temp->link=head;
head=temp;
}
}

[Type text]
 case2:Insertingendofthelist

temp

head is the pointervariable which contains address of thefirst node and temp contains address of new
node to be inserted then sample code is

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

After insertionthelinkedlistis

CodeforinsertEnd:-

template<class T>
void list<T>::insert_end()
{
structnode<T>*t,*temp;
int n;
cout<<"Enterdataintonode:";
cin>>n;
temp=create_node(n);
if(head==NULL)
head=temp;
else
{ t=head;
while(t->link!=NULL)
t=t->link;
t->link=temp;
}
}

[Type text]
 case3:Insertataposition

insertnodeatposition3
head is the pointervariable which contains address of thefirst node and temp contains address of new
node to be inserted then sample code is

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

Codeforinsertinganodeatagivenposition:-

template<classT>
voidlist<T>::Insert_at_pos(intpos)
{structnode<T>*cur,*prev,*temp;
int c=1;
cout<<"Enter data into node:";
cin>>item
temp=create_node(item);
if(head==NULL)
head=temp;
else
{
prev=cur=head;
if(pos==1)
{
temp->link=head;

[Type text]
 head=temp;
}
else
{
while(c<pos)
{ c++;
prev=cur;
cur=cur->link;
}
prev->link=temp;
temp->link=cur;
}
}
}

Deletions: Removing an element from the list, without destroying the integrity of the list itself.
To placean elementfrom thelist there are3cases:
1. Deleteanodeatbeginningofthelist
2. Deleteanodeatendofthelist
3. Deleteanodeatagivenposition

Case1:Deleteanodeatbeginningofthelist

head

head is the pointer variable which contains address of thefirst node

sample code is
t=head; head=head->link;
cout<<"node"<<t->data<<"Deletionissucess"; delete(t);

head

codefordeletinganodeat front

template<class T>
void list<T>::delete_front()
{
struct node<T>*t;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{ t=head;
[Type text]
 head=head->link;
cout<<"node"<<t->data<<"Deletionissucess"; delete(t);
}
}

[Link]

head

Todeletelastnode,findthenodeusingfollowing code

struct node<T>*cur,*prev; cur=prev=head;

while(cur->link!=NULL)
{prev=cur; cur=cur->link;
}
prev->link=NULL;
cout<<"node"<<cur->data<<"Deletionissucess"; free(cur);

head

codefordeletinganodeatendofthelist
template<class T>
void list<T>::delete_end()
{
struct node<T>*cur,*prev;
cur=prev=head;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{ cur=prev=head;
if(head->link==NULL)
{
cout<<"node"<<cur->data<<"Deletionissucess";
free(cur);
head=NULL;
}

[Type text]
 else
{ while(cur->link!=NULL)
{ prev=cur;
cur=cur->link;
}
prev->link=NULL;
cout<<"node"<<cur->data<<"Deletionissucess";
free(cur);
}
}
}

[Link]

head

Deletenodeatposition3
head is the pointer variable which contains address of thefirst node. Nodeto be deleted is node
containing value 30.
Findingnodeatposition3

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

prev cur

10 20 30 40

NULL
cur isthenodetobedeleted. beforedeletingupdatelinks code to

update links prev->link=cur->link;

cout<<cur->data<<"isdeletedsuccessfully"; delete cur;

prev cur
10 20 30 40
NULL

[Type text]
 Traversingthelist:Assuming we are given thepointer tothe head of the list, how do weget the end of
the list.

template <class T>

voidlist<T>::display()
{
struct node<T>*t;

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

#include<iostream.h>
#include<stdlib.h>tem
plate <class T> struct
node
{
Tdata;
structnode<T>*link;
};
template<classT>
class list
{
intitem;
structnode<T>*head;
public:
list();
void display();
structnode<T>*create_node(intn);
void insert_end();
void insert_front();
voidInsert_at_pos(intpos);
void delete_end();
voiddelete_front();
voidDelete_at_pos(intpos);
void Node_count();
};

[Type text]
 template<classT>list<T>::
list()
{
head=NULL;
}

template <class T>

voidlist<T>::display()
{
struct node<T>*t;

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

template<class T>
structnode<T>*list<T>::create_node(intn)
{structnode<T>*t;
t=newstructnode<T>;
t->data=n;
t-
>link=NULL;return t;
}

template<class T>
void list<T>::insert_end()
{structnode<T>*t,*temp;
int n;
cout<<"Enterdataintonode:";
cin>>n;
temp=create_node(n);
if(head==NULL)
head=temp;
else
{ t=head;
while(t->link!=NULL)
t=t->link;
t->link=temp;
}
}

[Type text]
 template<class T>
void list<T>::insert_front()
{
structnode<T>*t,*temp;
cout<<"Enterdataintonode:";
cin>>item;
temp=create_node(item);
if(head==NULL)
head=temp;
else
{ temp->link=head;
head=temp;
}
}

template<class T>
void list<T>::delete_end()
{
struct node<T>*cur,*prev;
cur=prev=head;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{ cur=prev=head;
if(head->link==NULL)
{
cout<<"node"<<cur->data<<"Deletionissucess";
free(cur);
head=NULL;
}
else
{ while(cur->link!=NULL)
{ prev=cur;
cur=cur->link;
}
prev->link=NULL;
cout<<"node"<<cur->data<<"Deletionissucess";
free(cur);
}
}
}

template<class T>
void list<T>::delete_front()
{
struct node<T>*t;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{ t=head;
head=head->link;

[Type text]
 cout<<"node"<<t->data<<"Deletionissucess";
delete(t);
}
}

template<class T>
void list<T>::Node_count()
{
structnode<T>*t;
int c=0;
t=head;
if(head==NULL)
{
cout<<"ListisEmpty\n";

}
else
{ while(t!=NULL)
{ c++;
t=t->link;
}
cout<<"NodeCount="<<c<<endl;
}
}

template<class T>
voidlist<T>::Insert_at_pos(intpos)
{struct node<T>*cur,*prev,*temp;
int c=1;
cout<<"Enterdataintonode:";
cin>>item
temp=create_node(item);
if(head==NULL)
head=temp;
else
{prev=cur=head;
if(pos==1)
{
temp->link=head;
head=temp;
}
else
{
while(c<pos)
{ c++;
prev=cur;
cur=cur->link;
}
prev->link=temp;
temp->link=cur;
}

[Type text]
 }
}

template<class T>
voidlist<T>::Delete_at_pos(intpos)
{
struct node<T>*cur,*prev,*temp;
int c=1;

if(head==NULL)
{
cout<<"ListisEmpty\n";
}
else
{prev=cur=head;
if(pos==1)
{
head=head->link;
cout<<cur->data<<"isdeletedsucesfully";
delete cur;
}
else
{
while(c<pos)
{ c++;
prev=cur;
cur=cur->link;
}
prev->link=cur->link;
cout<<cur->data<<"isdeletedsucesfully";
delete cur;
}
}
}

intmain()
{
intncount,ch,pos;
list <int> L;
while(1)
{
cout<<"\n***OperationsonLinkedList***"<<endl;
cout<<"\[Link] node at End"<<endl;
cout<<"[Link] node at Front"<<endl;
cout<<"[Link] node at END"<<endl;
cout<<"[Link] node at Front"<<endl;
cout<<"[Link] at a position "<<endl;
cout<<"[Link] at a position "<<endl;
cout<<"[Link] Count"<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link] Screen "<<endl;

[Type text]
 cout<<"[Link] "<<endl;
cout<<"EnterYourchoice:";
cin>>ch;
switch(ch)
{
case1: L.insert_end();
break;
case2:L.insert_front();
break;
case3:L.delete_end();
break;
case 4:L.delete_front();
break;
case5:cout<<"Enterpositiontoinsert";
cin>>pos;
L.Insert_at_pos(pos);
break;
case6:cout<<"Enterpositiontoinsert";
cin>>pos;
L.Delete_at_pos(pos);
break;
case7: L.Node_count();
break;
case 8: [Link]();
break;
case 9:system("cls");
break;
case 10:exit(0);

default:cout<<"Invalidchoice";
}
}
}

DOUBLYLINKEDLIST
A singly linked list has the disadvantage that we can only traverse it in one direction. Many
applications require searching backwardsand forwards through sectionsof a list. A useful refinement
[Link] between the two list
types is that while singly linked list have pointers going in one direction, doubly
linkedlisthavepointerbothtothenextand to [Link] adoubly
linked lististhat,theypermittraversingorsearchingofthe listin bothdirections.

Inthislinkedlisteachnodecontainsthreefields.
a) Onetostoredata
b) Remainingareselfreferentialpointerswhichpointstopreviousandnextnodesinthelist

prev data next

[Type text]
 Implementationofnodeusingstructure
Method-1:

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

Implementationofnodeusingclass
Method-2:

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

NULL 10 20 30 NULL

OperationsonDoublylinkedlist:
 Insertionofanode
 Deletionsofanode
 Traversingthe list

DoublylinkedlistADT:

template<classT>
class dlist
{
intdata;
struct dnode<T>*head;
public:
dlist()
{
head=NULL;
}
void display();
structdnode<T>*create_dnode(intn);
void insert_end();
void insert_front();
void delete_end();
void delete_front();
voiddnode_count();

[Type text]
 void Insert_at_pos(int pos);
voidDelete_at_pos(intpos);
};

Insertions:Toplaceanelementsinthelistthereare3cases
 [Link]
 [Link] thelist
 [Link]

case1:Insertatthebeginning
head

NULL 10 20 30 NULL

temp NULL 40 NULL

head is the pointervariable which contains address of thefirst node and temp contains address of new
node to be inserted then sample code is

temp->next=head; head->prev=temp; head=temp;

head

40 10 20 30 NULL

Codeforinsertfront:-
template<class T>
voidDLL<T>::insert_front()
{
struct dnode <T>*t,*temp;
cout<<"Enterdataintonode:";
cin>>data;
temp=create_dnode(data);
if(head==NULL)
head=temp;
else
{temp->next=head;head-
>prev=temp;
head=temp;
}
}

[Type text]
 case2:Insertingendofthelist

head

NULL 10 20 30 NULL

temp NULL 40 NULL

headisthepointer variablewhichcontainsaddressofthefirstnodeandtempcontainsaddressof new

node to be inserted then sample code is

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

head

NULL 10 20 30 NULL

NULL 40 NULL

CodetoinsertanodeatEnd:-

template<class T>
voidDLL<T>::insert_end()
{
structdnode<T>*t,*temp;
int n;
cout<<"Enterdataintodnode:";
cin>>n;
temp=create_dnode(n);
if(head==NULL)
head=temp;
else
{ t=head;
while(t->next!=NULL)
t=t->next;

[Type text]
 t->next=temp;
temp->prev=t;
}
}

case3:Insertingatagiveposition

head

NULL 10 20 30 NULL

temp
40

insert40atposition2
head is the pointervariable which contains address of thefirst node and temp contains address of new
node to be inserted then sample code is

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

head pr cr

NULL 10 20 30 NULL

NULL 40 NULL

temp

[Type text]
 Codetoinsertanodeataposition

template<class T>
voiddlist<T>::Insert_at_pos(intpos)
{
struct dnode<T>*cr,*pr,*temp;
int count=1;
cout<<"Enterdataintodnode:";
cin>>data;
temp=create_dnode(data);
display();
if(head==NULL)
{//whenlistisempty
head=temp;
}
else
{ pr=cr=head;
if(pos==1)
{ //insertingatpos=1
temp->next=head;
head=temp;
}
else
{
while(count<pos)
{ count++;
pr=cr;
cr=cr->next;
}
pr->next=temp;
temp->prev=pr;
temp->next=cr;
cr->prev=temp;
}
}
}

Deletions: Removing an element from the list, without destroying the integrity of the list itself.
To placean elementfrom thelist there are3cases:
1. Deleteanodeatbeginningofthelist
2. Deleteanodeatendofthelist
3. Deleteanodeatagivenposition

Case1:Deleteanodeatbeginningofthelist

head

NULL 10 20 30 NULL

[Type text]
 head is the pointer variable which contains address of thefirst node

sample code is

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

head

NULL 10 NULL 20 30 NULL

codefordeletinganodeat 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);
}
}

[Link]
[Link]

structdnode<T>*pr,*cr;
pr=cr=head; while(cr->next!=NULL)
{pr=cr;
cr=cr->next;
}
pr->next=NULL;
cout<<"dnode"<<cr->data<<"Deletionissucess"; delete(cr);

[Type text]
 head

NULL 10 20 NULL 30 NULL

pr cr

codefordeletinganodeatendofthelist

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

[Link]

head
NULL 10 30 20
NULL
Deletenodeatposition2
head is the pointer variable which contains address of thefirst node. Nodeto be deleted is node
containing value 30.
Findingnodeatposition2.

[Type text]
 while(count<pos)
{pr=cr;
cr=cr->next; count++;
}
pr->next=cr->next; cr->next->prev=pr;

head
NULL 10 30 20 NULL

pr cr

code fordeletinganodeataposition

template<class T>
voiddlist<T>::Delete_at_pos(intpos)
{
structdnode<T>*cr,*pr,*temp;
int count=1;
display();
if(head==NULL)
{
cout<<"ListisEmpty\n";
}
else
{pr=cr=head;
if(pos==1)
{
head=head->next;
head->prev=NULL;
cout<<cr->data<<"isdeletedsucesfully";
delete cr;
}
else
{
while(count<pos)
{ count++;
pr=cr;
cr=cr->next;
}
pr->next=cr->next;
cr->next->prev=pr;
cout<<cr->data<<"isdeletedsucesfully";
delete cr;
}
}
}

[Type text]
 DynamicImplementationofDoublylinkedlistADT

#include<iostream.h>t
emplate <class T>
struct dnode
{
Tdata;
structdnode<T>*prev;
structdnode<T>*next;
};
template<classT>
class dlist
{
intdata;
struct dnode<T>*head;
public:
dlist();
structdnode<T>*create_dnode(intn);
void insert_front();
void insert_end();
voidInsert_at_pos(intpos); void
delete_front();
void delete_end();
voidDelete_at_pos(intpos);
void dnode_count();
void display();
};

template<classT>dlist<T>:
:dlist()
{
head=NULL;
}

template<class T>
structdnode<T>*dlist<T>::create_dnode(intn)
{
structdnode<T>*t;
t=newstructdnode<T>;
t->data=n;
t->next=NULL;
t->prev=NULL;
returnt;
}
template<class T>
void dlist<T>::insert_front()
{
struct dnode <T>*t,*temp;
cout<<"Enterdataintodnode:";

[Type text]
 cin>>data;
temp=create_dnode(data);
if(head==NULL)
head=temp;
else
{temp->next=head;head-
>prev=temp;
head=temp;
}
}
template<class T>
void dlist<T>::insert_end()
{
structdnode<T>*t,*temp;
int n;
cout<<"Enterdataintodnode:";
cin>>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;
}
}

template<class T>
voiddlist<T>::Insert_at_pos(intpos)
{
structdnode<T>*cr,*pr,*temp;
int count=1;
cout<<"Enterdataintodnode:";
cin>>data;
temp=create_dnode(data);
display();
if(head==NULL)
{//whenlistisempty
head=temp;
}
else
{ pr=cr=head;
if(pos==1)
{ //insertingatpos=1
temp->next=head;
head=temp;
}
else

[Type text]
 {
while(count<pos)
{ count++;
pr=cr;
cr=cr->next;
}
pr->next=temp;
temp->prev=pr;
temp->next=cr;
cr->prev=temp;
}
}
}

template<class T>
voiddlist<T>::delete_front()
{structdnode<T>*t;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{ display();
t=head;
head=head->next;
head->prev=NULL;
cout<<"dnode"<<t->data<<"Deletionissucess";
delete(t);
}
}
template<class T>
void dlist<T>::delete_end()
{
structdnode<T>*pr,*cr;
pr=cr=head;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{ cr=pr=head;
if(head->next==NULL)
{
cout<<"dnode"<<cr->data<<"Deletionissucess";
delete(cr);
head=NULL;
}
else
{ while(cr->next!=NULL)
{ pr=cr;
cr=cr->next;
}
pr->next=NULL;
cout<<"dnode"<<cr->data<<"Deletionissucess";
delete(cr);

[Type text]
 }
}
}
template<class T>
voiddlist<T>::Delete_at_pos(intpos)
{
structdnode<T>*cr,*pr,*temp;
int count=1;
display();
if(head==NULL)
{
cout<<"ListisEmpty\n";
}
else
{pr=cr=head;
if(pos==1)
{
head=head->next;
head->prev=NULL;
cout<<cr->data<<"isdeletedsucesfully";
delete cr;
}
else
{
while(count<pos)
{ count++;
pr=cr;
cr=cr->next;
}
pr->next=cr->next;
cr->next->prev=pr;
cout<<cr->data<<"isdeletedsucesfully";
delete cr;
}
}
}
template<class T>
void dlist<T>::dnode_count()
{
structdnode<T>*t;
int count=0;
display();
t=head;
if(head==NULL)
cout<<"ListisEmpty\n";
else
{ while(t!=NULL)
{ count++;
t=t->next;
}
cout<<"nodecountis"<<count;

[Type text]
 }
}
template
<classT>voiddlist<T>::
display()
{
structdnode<T>*t;
if(head==NULL)
{
cout<<"ListisEmpty\n";
}
else
{ cout<<"Nodesinthelinkedlistare...\n";
t=head;
while(t!=NULL)
{ cout<<t->data<<"<=>";
t=t->next;
}
}
}
intmain()
{
intch,pos;dlist
<int>DL;
while(1)
{
cout<<"\n***OperationsonDoublyList***"<<endl;
cout<<"\[Link] dnode at End"<<endl;
cout<<"[Link] dnode at Front"<<endl;
cout<<"[Link] dnode at END"<<endl;
cout<<"[Link] dnode at Front"<<endl;
cout<<"[Link] nodes "<<endl;
cout<<"[Link] Nodes"<<endl;
cout<<"[Link] ata position "<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link] "<<endl;
cout<<"[Link] Screen "<<endl;
cout<<"Enter Your choice:";
cin>>ch;
switch(ch)
{
case1: DL.insert_end();
break;
case2:DL.insert_front();
break;
case 3:DL.delete_end();
break;
case4:DL.delete_front();
break;
case5://displaycontents
[Link]();
break;

[Type text]
 case6: DL.dnode_count();
break;
case7:cout<<"Enterpositiontoinsert";
cin>>pos;
DL.Insert_at_pos(pos);
break;
case8: cout<<"EnterpositiontoDelete";
cin>>pos;
DL.Delete_at_pos(pos);
break;
case9:exit(0);
case10:system("cls");
break;
default:cout<<"Invalidchoice";
}
}
}

CIRCULARLYLINKEDLIST
Acircularlylinkedlist,orsimplycircularlist,isalinkedlistinwhichthelastnodeisalwayspoints tothe first node.
This type of list canbe buildjust by replacing the NULL pointer at the end of the list with
apointerwhichpointsto the [Link] isnofirstorlastnodein thecircularlist.

Advantages:
 Anynodecanbetraversedstartingfromanyothernodeinthelist.
 There is no need of NULL pointer to signal the end of the list and hence, all pointers contain
valid addresses.
 In contrast to singlylinked list, deletion operation in circularlist is simplified as the search for
the previousnodeof anelementtobedeletedcan bestarted from thatitem itself.

head

DynamicImplementationofCircularlinkedlistADT

#include<iostream.h>
#include<stdlib.h>tem
plate <class T> struct
cnode
{
Tdata;
structcnode<T>*link;
};
//CodefotcircularlinkedListADT template
<class T>

[Type text]
 classclist
{
intdata;
structcnode<T>*head;
public:
clist();
structcnode<T>*create_cnode(intn);
void display();
void insert_end();
void insert_front();
void delete_end();
void delete_front();
voidcnode_count();

};
//codefordefautconstructor
template <class
T>clist<T>::clist()
{
head=NULL;
}

//codetodisplayelementsinthelist template
<class T>
voidclist<T>::display()
{
structcnode<T>*t;
if(head==NULL)
{
cout<<"clistisEmpty\n";
}
else
{ t=head;
if(t->link==head)
cout<<t->data<<"->";
else
{
cout<<t->data<<"->";
t=t->link; while(t!
=head)
{
cout<<t->data<<"->";
t=t->link;
}
}
}
}

//Codetocreatenode
template <class T>
structcnode<T>*clist<T>::create_cnode(intn)

[Type text]
 {
structcnode<T>*t;
t=newstructcnode<T>;
t->data=n;
t-
>link=NULL;return t;
}
//Codetoinsertnodeattheend
template <class T>
voidclist<T>::insert_end()
{
struct cnode<T>*t;
structcnode<T>*temp;
int n;
cout<<"Enterdataintocnode:";
cin>>n;
temp=create_cnode(n);
if(head==NULL)
{
head=temp;
temp->link=temp;
}
else
{
t=head;
if(t->link==head)//listcontainingonlyonenode
{
t->link=temp;
temp->link=t;
}
else
{
while(t->link!=head)
{
t=t->link;
}
t->link=temp;
temp->link=head;
}
}
cout<<"Nodeinerted"<<endl;
}

//Codetoinsertnodeatfront
template <class T>
voidclist<T>::insert_front()
{
struct cnode <T>*t;
structcnode<T>*temp;
cout<<"Enterdataintocnode:";
cin>>data;

[Type text]
 temp=create_cnode(data);
if(head==NULL)
{
head=temp;
temp->link=temp;
}
else
{
t=head;
if(t->link==head)
{
t->link=temp;
temp->link=t;
}
else
{
//codetofindlastnode
while(t->link!=head)
{
t=t->link;
}
t->link=temp;//linkinglastandfirstnode
temp->link=head;
head=temp;

}
}
cout<<"Nodeinserted\n";
}

//Codetodeletenodeatend
template <class T>
voidclist<T>::delete_end()
{
structcnode<T>*cur,*prev;
cur=prev=head;
if(head==NULL)
cout<<"clistisEmpty\n";
else
{ cur=prev=head;
if(cur->link==head)
{
cout<<"cnode"<<cur->data<<"Deletionissucess";
free(cur);
head=NULL;
}
else
{ while(cur->link!=head)
{ prev=cur;
cur=cur->link;
}

[Type text]
 //prev=cur;
//cur=cur->link;
prev->link=head;//pointstohead
cout<<"cnode"<<cur->data<<"Deletionissucess";
free(cur);
}
}
}
//Codetodeletenodeatfront
template <class T>
voidclist<T>::delete_front()
{
structcnode<T>*t,*temp;
if(head==NULL)
cout<<"circularlistisEmpty\n";
else
{ t=head;
//head=head->link;
if(t->link==head)
{
head=NULL;
cout<<"cnode"<<t->data<<"Deletionissucess"; delete(t);

}
else
{
//codetofindlastnode
while(t->link!=head)
{
t=t->link;
}
temp=head;
t->link=head->link; //linkinglastandfirstnode
cout<<"cnode "<<temp->data<<" Deletion is sucess";
head=head->link;
delete(temp);
}
}
}
//Codetocountnodesinthecircularlinkedlist template
<class T>
voidclist<T>::cnode_count()
{
structcnode<T>*t;
int c=0;
t=head;
if(head==NULL)
{
cout<<"circularlistisEmpty\n";

[Type text]
 else
{ t=t->link;
c++;
while(t!=head)
{ c++;
t=t->link;
}
cout<<"NodeCount="<<c;

}
intmain()
{
int ch,pos;
clist<int>L;
while(1)
{
cout<<"\n***OperationsonCircularLinkedclist***"<<endl;
cout<<"\[Link] cnode at End"<<endl;
cout<<"[Link] Cnode at Front"<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link] Nodes "<<endl;
cout<<"[Link] Count"<<endl;
cout<<"[Link] "<<endl;
cout<<"[Link]"<<endl;
cout<<"Enter Your choice:";
cin>>ch;
switch(ch)
{
case1: L.insert_end();
break;
case2:L.insert_front();
break;
case3:L.delete_end();
break;
case 4:L.delete_front();
break;
case5://displaycontents
[Link]();
break;
case6: L.cnode_count();
break;
case7:exit(0);
case8:system("cls");
break;
default:cout<<"Invalidchoice";
}
}
}

[Type text]
 UNIT-II

STACK ADT:- A Stackis alineardatastructure where insertion and deletion of items takes place at
one end called topof the stack. A Stack is defined as a data structure which operates on a last-in first-
[Link]-inFirst-out(LIFO).
Stack uses a single indexor pointer to keep track of the information in the stack. The basic
operations associated with the stack are:
a) push(insert)anitemontothestack.
b) pop(remove)anitemfromthestack.

Thegeneralterminologyassociatedwiththestackisasfollows:
A stack pointer keeps track of the current position on the stack. When an element is placedon
the stack,it issaid to be pushedon the [Link] an objectis removed from the stack,itis said to be
popped off the stack. Two additional terms almost always usedwithstacksare overflow, which
occurs when we try to push more information on a stack that it can hold, and underflow, which
occurs when wetry to popan item off a stack which is empty.

Pushingitemsontothestack:

Assumethatthearrayelementsbeginat0(becausethearraysubscriptstartsfrom0)
and themaximumelementsthatcan be placed instack [Link] stackpointer, top,isconsidered to
[Link]
topointtonextfreeslotandthencopyingdataintothatslotofthe [Link] thetopisinitialized to -1.

//codetopushanelement ontostack;
template<class T>
voidstack<T>::push()
{
if(top==max-1)
cout<<"StackOverflow...\n";
else
{
cout<<"Enteranelementtobepushed:"; top++;
cin>>data;
stk[top]=data;
cout<<"PushedSucesfully......\n";

}
}

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

//codetoremoveanelementfromstack
template<class T>
voidstack<T>::pop()
{
if(top==-1)
cout<<"StackisUnderflow";
else
{
data=stk[top];
top--;
cout<<data<<"ispopedSucesfully........\n";
}
}

StaticimplementationofStackADT

#include<stdlib.h>
#include<iostream.h>#
define max 4
template<class T>
class stack
{
private:
inttop;
Tstk[max],data;
public:
stack();void
push();
voidpop();
void display();
};
template<classT>
stack<T>::stack()
{
top=-1;

35
}
//codetopushanelement ontostack;
template<class T>
voidstack<T>::push()
{
if(top==max-1)
cout<<"StackOverflow...\n";
else
{
cout<<"Enteranelementtobepushed:"; top++;
cin>>data;
stk[top]=data;
cout<<"PushedSucesfully......\n";

}
}
//codetoremoveanelementfromstack
template<class T>
voidstack<T>::pop()
{
if(top==-1)
cout<<"Stackis Underflow";
else
{
data=stk[top];
top--;
cout<<data<<"ispopedSucesfully........\n";
}
}
//codetodisplaystackelements
template<class T>
voidstack<T>::display()
{
if(top==-1)
cout<<"StackUnderFlow";
else
{ cout<<"ElementsintheStack are........\n";
for(inti=top;i>-1;i--)
{
cout<<<<stk[i]<<"\n";
}
}
}
intmain()
{
int choice;
stack<int>st;
while(1)
{
cout<<"\n*****MenuforStackoperations*****\n";
cout<<"[Link]\[Link]\[Link]\[Link]\n";

36
 cout<<"EnterChoice:";
cin>>choice;
switch(choice)
{
case1: [Link]();
break;
case 2: [Link]();
break;
case 3: [Link]();
break;
case4:exit(0);
default:cout<<"Invalidchoice...Tryagain...\n";
}
}
}
output:
*****MenuforStackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
EnterChoice:1
Enteranelementtobepushed:11
Pushed Sucesfully....
*****MenuforStackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
EnterChoice:1
Enteranelementtobepushed:22
Pushed Sucesfully....

*****Menufor Stackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
EnterChoice:1
Enteranelementtobepushed:44
Pushed Sucesfully....

*****MenuforStackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
EnterChoice:1
EnterChoice:1
Enteranitemtobepushed:55 Pushed
Sucesfully....

37
*****MenuforStackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
Enter Choice:1
StackOverflow...

*****MenuforStackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
EnterChoice:2
55ispopedSucesfully....

*****MenuforStackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
EnterChoice:3
ElementsintheStackare.... 44
22
11

*****MenuforStackoperations*****
1. PUSH
2. POP
3. DISPLAY
4. EXIT
EnterChoice:4

DynamicimplementationofStackADT

#include<iostream.h>t
emplate <class T>
struct node
{
Tdata;
structnode<T>*link;
};
template<classT>
class stack
{
intdata;
struct node<T>*top;

38
 public:
stack()
{
top=NULL;
}
voiddisplay();
void push();
void pop();
};
template<class T>
voidstack<T>::display()
{
struct node<T>*t;

if(top==NULL)
{
cout<<"stackisEmpty\n";
}
else
{ t=top; while(t!
=NULL)
{ cout<<"|"<<t->data<<"|"<<endl;
t=t->link;
}
}
}

template <class
T>voidstack<T>::push
()
{
structnode<T>*t,*temp;
cout<<"Enterdataintonode:";
cin>>data;
temp=newstructnode<T>;
temp->data=data;
temp->link=NULL;
if(top==NULL)
top=temp;
else
{ temp->link=top;
top=temp;
}
}

template <class
T>voidstack<T>::pop(
)
{
struct node<T>*t;
if(top==NULL)
cout<<"stackisEmpty\n";

39
 else
{ t=top;
top=top->link;
cout<<"node"<<t->data<<"Deletionissucess"; delete(t);
}
}

intmain()
{
intch;
stack<int>st;
while(1)
{
cout<<"\n***OperationsonDynamicstack***"<<endl;
cout<<"\[Link]"<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link] "<<endl;
cout<<"[Link] "<<endl;
cout<<"EnterYourchoice:";
cin>>ch;
switch(ch)
{
case1: [Link]();
break;
case 2: [Link]();
break;
case 3:[Link]();;
break;
case 4:exit(0);
default:cout<<"Invalid choice";
}
}
}

ApplicationsofStack:
1. Stacksareusedinconversionofinfixtopostfix expression.
2. Stacksarealsousedinevaluationofpostfixexpression.
3. Stacksareusedtoimplementrecursiveprocedures.
4. Stacksareusedincompilers.
5. ReverseString

An arithmetic expression can be written in three different but equivalent notations, i.e., without
changingtheessenceoroutputof [Link]−
1. InfixNotation
2. Prefix(Polish)Notation
3. Postfix(Reverse-Polish)Notation

40
 ConversionofInfix ExpressionstoPrefixand Postfix

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

TheTowerofHanoi(alsocalledtheTowerofBrahmaorLucas'Tower,[1]andsometimes
pluralized)[Link] consistsofthreerods,andanumberofdisksof
[Link] inaneatstackin
ascendingorderofsizeononerod,thesmallestat thetop,thusmakingaconicalshape.

41
Theobjectiveofthepuzzleistomovetheentirestacktoanotherrod,obeyingthefollowingsimple rules:
1. Onlyonediskcanbemovedatatime.
2. Each move consists of taking the upperdisk from one of the stacks and placing it ontop of another
stack i.e. adisk canonly bemoved ifitistheuppermostdiskon astack.
3. Nodiskmaybeplacedontopofasmaller disk.

QUEUEADT
Aqueueisanorderedcollectionofdatasuchthat thedataisinsertedatoneendanddeletedfrom
[Link] processed first-
in first-outor FIFO. In other words the information receive froma queue comes in the same order that it
was placed on the queue.

RepresentingaQueue:
Oneof themostcommonwaytoimplementaqueueisusing [Link] define
anarrayQueue, and two additional variables front and rear. The rules formanipulating these variables
are
simple:
 Eachtimeinformationisaddedtothequeue,incrementrear.
 Eachtimeinformationistakenfromthequeue,incrementfront.
 Wheneverfront>rearorfront=rear=-1thequeueisempty.
Array implementationof aQueuedo [Link] tobeset at compile time,
rather thanat run time. Space can be wasted,if we do notusethe full capacity of the array.

42
OperationsonQueue:
Aqueuehavetwobasicoperations:
a) addingnewitemto thequeue
b) removingitemsfromqueue.
The operation of adding new item onthe queue occursonlyat one endof the queue called the rear or
back.
Theoperationofremovingitemsofthequeueoccursattheotherendcalledthefront.

Forinsertionanddeletionof anelementfrom aqueue,thearrayelementsbeginat 0andthe maximum elements

of the array is maxSize. The variable front will hold the indexof the item that is
consideredthefrontofthequeue,whiletherearvariablewillholdtheindexof thelastiteminthe queue.
Assume that initially the front and rear variables are initialized to-1. Like stacks, underflow
andoverflowconditionsare to bechecked beforeoperationsin aqueue.

Queueemptyorunderflowconditionis
if((front>rear)||front= =-1)
cout<”Queue is empty”;

QueueFulloroverflowconditionis
if((rear==max) cout<”Queue is full”;

StaticimplementationofQueueADT

#include<stdlib.h>
#include<iostream.h>
#define max 4
template <class T>
class queue
{
T q[max],item;
intfront,rear;
public: queue();
void insert_q();
void delete_q();
voiddisplay_q();
};
template <class
T>queue<T>::queue()
{
front=rear=-1;
}
//code to insert an item into queue;
template <class T>
voidqueue<T>::insert_q()

43
{
if(front>rear)
front=rear=-1;
if(rear==max-1)
cout<<"queueOverflow...\n";
else
{
if(front==-1)
front=0;
rear++;
cout<<"Enter an item to be inserted:";
cin>>item;
q[rear]=item;
cout<<"insertedSucesfully..intoqueue..\n";
}
}
template<classT>
voidqueue<T>::delete_q()
{
if((front==-1&&rear==-1)||front>rear)
{
front=rear=-1;
cout<<"queueisEmpty..\n";
}
else
{
item=q[front];
front++;
cout<<item<<"isdeletedSucesfully...\n";
}
}
template<classT>
voidqueue<T>::display_q()
{
if((front==-1&&rear==-1)||front>rear)
{
front=rear=-1;
cout<<"queueisEmpty..\n";
}
else
{
for(int i=front;i<=rear;i++)
cout<<"|"<<q[i]<<"|<--";
}
}
intmain()
{
intchoice;
queue<int>q;
while(1)
{
cout<<"\n\n*****Menufor operations onQUEUE*****\n\n";
cout<<"[Link]\[Link]\[Link]\[Link]\n";

44
 cout<<"Enter Choice:";
cin>>choice;
switch(choice)
{
case1: q.insert_q();
break;
case 2: q.delete_q();
break;
case3:cout<<"Elementsinthequeueare...\n";
q.display_q();
break;
case4:exit(0);
default:cout<<"Invalidchoice...Tryagain...\n";
}
}
}

DynamicimplementationofQueueADT

#include<stdlib.h>
#include<iostream.h>t
emplate <class T>
struct node
{
T data;
structnode<T>*next;
};
template <class T>
class queue
{
private:
Titem;
node<T>*front,*rear;
public:
queue();
void insert_q();
void delete_q();
voiddisplay_q();
};
template <class
T>queue<T>::queue()
{
front=rear=NULL;
}
//code to insert an item into queue;
template <class T>
voidqueue<T>::insert_q()
{
node<T>*p;
cout<<"Enteranelementtobeinserted:";

45
 cin>>item;p=new
node<T>; p-
>data=item;
p->next=NULL;
if(front==NULL)
{
rear=front=p;
}
else
{
rear->next=p;
rear=p;
}
cout<<"\nInsertedintoQueueSucesfully...\n";
}
//code to delete an elementfrom queue
template <class T>
voidqueue<T>::delete_q()
{
node<T>*t;
if(front==NULL)
cout<<"\nQueue is Underflow";
else
{
item=front->data;
t=front;
front=front->next;
cout<<"\n"<<item<<"isdeletedfromQueue...\n";
}
delete(t);
}
//code to display elements in queue
template <class T>
voidqueue<T>::display_q()
{
node<T>*t;
if(front==NULL)cout<<"\nQueue
Under Flow";
else
{
cout<<"\nElements in theQueue are... \n";
t=front;
while(t!=NULL)
{
cout<<"|"<<t->data<<"|<-";
t=t->next;
}
}
}
intmain()
{
intchoice;
queue<int>q1;

46
 while(1)
{
cout<<"\n\n***Menu for operations on Queue***\n\
n";cout<<"[Link]\[Link]\[Link]\[Link]\
n";cout<<"Enter Choice:";
cin>>choice;
switch(choice)
{
case1:q1.insert_q();
break;ca
se2:q1.delete_q();
break;
case 3: q1.display_q();
break;
case4:exit(0);
default:cout<<"Invalidchoice...Tryagain...\n";
}
}
}

Application of Queue:
Queue, as the name suggests is used whenever we need to have any group of objects in an order in
which thefirstonecomingin, also getsout firstwhiletheotherswaitfor thereturn,likein the following
scenarios :
1. Servingrequestsonasinglesharedresource,likeaprinter,CPUtaskschedulingetc.
2. In real life, Call Center phone systemswill use Queues, to hold people calling them in an order,
until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the sameorder as they
arrive, First come first served.

CIRCULARQUEUE
Once the queue gets filled up,no more elementscan beadded to iteven if any elementis removed from
[Link],rearpointerisnotadjusted.

Whenthequeuecontainsveryfewitemsandtherearpointerpointstolastelement.i.e. rear=maxSize-
1,wecannotinsert any more items into queue because the overflow condition satisfies. That means a lot of
space is wasted
.[Link]
[Link].

47
 A circular queueis a queue in which all locations aretreated as circular such that the first
location CQ[0] follows thelast location CQ[max-1].

CircularQueueemptyorunderflowconditionis

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

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

InsertionintoaCircularQueue:
Algorithm CQueueInsertion(Q,maxSize,Front,Rear,item)
Step 1: If Rear = maxSize-1 then
Rear=0
else
Rear=Rear+1
Step 2: If Front =Rearthen print
“Queue Overflow”
Return
Step3:Q[Rear]=item

48
Step 4: If Front = 0 then
Front = 1
Step5:Return

DeletionfromCircularQueue:

AlgorithmCQueueDeletion(Q,maxSize,Front,Rear,item)
Step1:IfFront=0then
print “Queue Underflow”
Return
Step2:K=Q[Front]
Step 3: If Front = Rear then
begin
Front=-1
Rear=-1
end
else
If Front = maxSize-1 then
Front = 0
else
Front=Front+1
Step4:ReturnK

StaticimplementationofCircularQueueADT

#include<iostream.h>
#define max 4
template <class T>
class CircularQ
{
T cq[max];int
front,rear;
public:
CircularQ();void
insertQ(); void
deleteQ(); void
displayQ();
};
template <class
T>CircularQ<T>::CircularQ
()
{
front=rear=-1;
}
template<classT>
voidCircularQ<T>::insertQ()
{
intnum;
if(front==(rear+1)%max)
{
cout<<"CircularQueueisfull\n";
}

49
 else
{
cout<<"Enter an element";
cin>>num;
if(front==-1)
rear=front=0;
else
rear=(rear+1)%max;
cq[rear]=num;
cout<<num<<"isinserted...";
}
}
template<classT>
voidCircularQ<T>::deleteQ()
{
intnum;
if(front==-1)
cout<<"Queueisempty";
else
{
num=cq[front];
cout<<"Deleted item is "<< num;
if(front==rear)
front=rear=-1;
else
front=(front+1)%max;
}
}

template<classT>
voidCircularQ<T>::displayQ()
{
inti;
if(front==-1)
cout<<"Queueisempty";
else
{ cout<<"Queueelementsare\n";
for(i=front;i<=rear;i++)
cout<<cq[i]<<"\t";
}
if(front>rear)
{
for(i=front;i<max;i++)
cout<<cq[i]<<"\t";
for(i=0;i<=rear;i++)
cout<<cq[i]<<"\t";
}
}
intmain()
{
CircularQ<int>obj;
int choice;
while(1)
{ cout<<"\n***CircularQueueOperations***\n";

50
 cout<<"\[Link] Element into CircularQ"; cout<<"\
[Link] Element from CircularQ"; cout<<"\
[Link] Elements in CircularQ"; cout<<"\[Link] ";
cout<<"\nEnter Choice:";
cin>>choice;
switch(choice)
{ case 1: [Link]();
break;
case2:[Link]();
break;
case 3: [Link]();
break;
case4:exit(0);
}
}
}

51
 UNIT-III

Priority Queue
DEFINITION:
Apriorityqueueisacollectionofzeroormore [Link] hasapriorityorvalue.
Unlike thequeues,whichareFIFOstructures,the orderofdeleting from apriorityqueue isdeterminedbythe element
priority.
Elementsareremoved/deletedeither inincreasing or decreasing order ofpriorityratherthanintheorder in which
they arrived in the queue.
Therearetwotypesofpriorityqueues:
 Minpriorityqueue
 Maxpriorityqueue

Minpriorityqueue:Collectionofelements inwhichthe itemscanbe insertedarbitrarily,but onlysmallestelement can be

removed.

Maxpriorityqueue:Collectionofelements inwhichinsertion ofitemscanbe inanyorderbut onlylargestelement can be

removed.

Inpriorityqueue,the elementsarearranged inanyorderand outofwhichonlythesmallest or largestelement allowed to

delete each time.
Theimplementation ofpriorityqueuecanbedoneusingarrays orlinked [Link] heap isused to
implement the priority queue effectively.
APPLICATIONS:
1. The typical example of priority queue is scheduling the jobs in operating system. Typically OS allocates
priority to jobs. The jobs are placed in the queue and position of the job in priority queue determines their
priority. In OS there are 3 jobs- real time jobs, foreground jobs and background jobs. The OS
alwaysschedulesthe realtime jobs first. Ifthere isnorealtime jobspendingthen it schedules foreground
[Link] if no real time and foreground jobs are pending then OS schedules the background jobs.
2. Innetworkcommunication,the managelimitedbandwidthfortransmissionthepriorityqueueisused.
3. Insimulationmodelingtomanagethediscreteevents thepriorityqueue isused.
Various operations that can be performed on priority queue are-
1. Findanelement
2. Inserta new element
3. Remove ordeleteanelement
Theabstractdatatypespecificationforamaxpriorityqueue [Link] minpriority queue
isthesameas ordinaryqueue exceptwhiledeletion, find and removetheelementwithminimumpriority

ABSTRACTDATATYPE(ADT):
AbstractdatatypemaxPriorityQueue
{
Instances
Finitecollectionofelements,eachhasapriorityOperations empty():return
true iff the queue is empty
size():returnnumberofelementsinthequeue
top() :return element with maximum priority
del():removetheelementwithlargestpriorityfromthequeue

52
insert(x): insert the element x into the queue

53
}

HEAPS
Heapisatreedatastructuredenotedbyeitheramaxheaporaminheap.
Amaxheap isatreeinwhichvalueofeachnode isgreaterthanor equaltovalueofitschildrennodes. Amin heap is a tree
in which value ofeach node is less than or equalto value of its children nodes.

18 4

12 4 12 14

11 10 18 20

Maxheap Minheap

InsertionofelementintheHeap:

Consideramaxheapasgivenbelow:

Nowifwewant [Link] cannot insert7 as left child [Link] isbecause themax heap hasapropertythat value of
any node is always greater than the parent nodes. Hence 7 will bubble up 4 willbe left child of 7.
Note:Whenanew nodeistobeinserted incompletebinarytreewestartfrombottomand fromleftchild onthe current level.
The heap is always a complete binary tree.

54
 18

12 7 inserted!

11 10 4

Ifwewanttoinsertnode25,thenas25 isgreatestelement itshouldbetheroot.Hence25willbubbleup and18 will move

down.

25 inserted!

12 18

11 10 4

The insertionstrategyjustoutlined makesasinglebubbling pass froma [Link] eachlevelwe do (1)

work, so we should be able to implement the strategyto have complexityO(height) = O(log n).

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

Deletionofelementfromtheheap:

55
 Fordeletionoperationalwaysthemaximumelementisdeleted from heap. InMaxheapthemaximum element is
always present at root. And if root element is deleted then we need to reheapify the tree.

ConsideraMaxheap

25

12 18

11 10 4

Deleterootelement:25,Nowwecannotputeither12 or18as root nodeandthatshouldbegreaterthanall its children

elements.
18

12 4

11 10

Nowwecannotput4at therootas itwill notsatisfytheheapproperty.Hencewewillbubbleup18andplace18at root, and 4 at

position of 18.

If18getsdeletedthen12becomesroot and11becomesparentnode of10.

56
[Link](logn).
1. Removethemaximumelementwhich ispresentattheroot. Thenaholeiscreatedattheroot.
2. [Link] [Link] isfoundthen place it
at root. Ensure that the tree issatisfying the heap property or not.
3. Repeatthestep1and 2ifanymoreelements aretobedeleted.

voidheap::delet(int item)
{
intitem,temp;
if(size==0)
cout<<”Heapisempty\n”; else
{
//removethelastelemntandreheapify
item=H[size--];
//itemisplacedatroottemp=1; child=2;
while(child<=size)
{
if(child<size&&H[child]<H[child+1])child++;
if(item>=H[child])
break;
H[temp]=H[child];
temp=child;
child=child*2;
}
//pl;acethelargestitematroot
H[temp]=item;
}

ApplicationsOfHeap:

1. [Link].

57
 2. Inpriorityqueueimplementationtheheapisused.

HEAPSORT

Heapsort isamethod inwhichabinarytree isused. Inthismethod firstthe heap iscreatedusingbinarytreeandthen heap is sorted
using priority queue.

Eg:

25 57 48 38 10 91 84 33

Intheheapsortmethodwefirsttakealltheseelementsinthearray“A”

A[0] A[1]
25 57

Nowstartbuilding theheapstructure. Informingtheheap thekeypointisbuild heap insuchawaythatthe highest

value in the array will always be a root.

Insert25

58
59
The nextelement is84,which91>84>57themiddle element.So84willbetheparent [Link] complete
binary tree 57 will be attached as right of 84.

60
Now the heap is formed. Let us sort it. For sorting the heap remember two main things the first thing is that the
binarytree form ofthe heap should [Link] completesorting binarytreeshouldberemained. And
the second thing is that we will start sorting the higher elements at the end of array in sorted manner i.e..
A[7]=91,A[6]=84andsoon..
Step1:- ExchangeA[0]withA[7]

61
62
63
64
Step5:-ExchaneA[0]withA[2]

65
Writeaprogramtoimplement heapsort
#include<iostream.h>voi
dswap(int*a,int*b)
{
intt;
t=*a;
*a=*b;
*b=t;
}
voidheapify(intarr[],intn,inti)
{
intlargest=i;//Initializelargestasroot int l =
2*i + 1; // left = 2*i + 1
intr=2*i+2;//right=2*i+2

// Ifleft child islargerthanroot

if(l<n&&(arr[l]>arr[largest]))
largest=l;

//Ifrightchildislargerthanlargestsofar if (r
< n &&( arr[r] > arr[largest]))
largest=r;

66
 //Iflargestisnotroot if
(largest != i)
{
swap(&arr[i],&arr[largest]);

//Recursivelyheapifytheaffectedsub-tree
heapify(arr, n, largest);
}
}

// function to do heap sort

voidheapSort(intarr[],intn)
{inti;
//Buildheap(rearrangearray) for
( i = n / 2 - 1; i >= 0; i--)
heapify(arr,n,i);

//Onebyoneextractanelementfromheap for
( i=n-1; i>=0; i--)
{
//Movecurrentroottoend
swap(&arr[0], &arr[i]);

//callmaxheapifyonthereduced heap
heapify(arr, i, 0);
}
}
/*Autilityfunctiontoprintarrayofsizen*/ void
printArray(int arr[], int n)
{
for(int i=0;i<n;++i)
cout<<arr[i]<<"";
cout <<"\n";
}
intmain()
{
intn,i;
intlist[30];
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"numbers";
for(i=0;i<n;i++)
cin>>list[i];
heapSort(list,n);
cout<<"Sortedarrayis\n";
printArray(list, n);
return0;
}

67
ALGORITHMS
Definition: An Algorithm is a method of representing the step-by-step procedure for solving a
problem. It is a method of finding the right answer to a problem orto a different problem by breaking
the problem into simple cases.

Itmustpossessthefollowingproperties:

1. Finiteness: Analgorithmshouldterminateinafinitenumberofsteps.

2. Definiteness:Eachstepofthealgorithmmustbeprecisely(clearly)stated.

3. Effectiveness:Eachstepmustbeeffective.i.e;it shouldbeeasilyconvertibleinto
program statement and can be performed exactly in a finite amount of time.

4. Generality: Algorithmshouldbecompleteinitself, sothat itcanbeusedtosolveall

problems of given type for any inputdata.

5. Input/Output:Eachalgorithmmusttakezero, one or morequantitiesasinputdata and

gives one of more outputvalues.
AnalgorithmcanbewritteninEnglishlikesentences or inanystandard
representations. The algorithm written in English language is called Pseudo code.

Example:Tofindtheaverageof3numbers,thealgorithmisasshownbelow.
Step1: Read the numbers a, b, c, and d.
Step2: Compute the sum of a, b, and c.
Step3: Divide the sum by 3.
Step4: Store the result in variable of d.
Step5: End the program.

Searching:Searchingisthetechniqueoffindingdesireddataitemsthathasbeenstored
within some data structure. Data structures can include linked lists, arrays,searchtrees,hash
tables,orvarious otherstorage [Link] appropriate search algorithm often dependson the data
structure being searched.
Searchalgorithmscanbeclassifiedbasedontheirmechanismofsearching. Theyare
 Linearsearching
 Binarysearching
Linear or Sequential searching:Linear Search is the mostnatural searchingmethod and
Itisvery simplebutvery poorin [Link] thismethod,thesearchingbeginswith

68
searching every element ofthelist tilltherequiredrecordis [Link] inthelistmaybe in any
order. i.e. sorted or unsorted.
We begin search by comparing the first element of the list with the target element. If it
matches, the search ends and position of the element is returned. Otherwise, we will move to next
element and compare. In this way, the target elementis compared with all the elementsuntil a match
occurs. If the match do not occur and there are no more elements to be compared, weconclude that
target element is absent in the list by returning position as -1.

Forexampleconsiderthefollowinglistof elements.
5595758511256545
Suppose we want to search for element 11(i.e. Target element = 11). We first compare the
target element with first element in list i.e. 55. Since both are not matching we move on the next
elements in the list and compare. Finally we will find the match after 5 comparisons at position 4
starting from position 0.
Linearsearchcanbeimplementedintwoways.i)Nonrecursiveii)recursive

AlgorithmforLinearsearch

Linear_Search(A[],N,val,pos)
Step 1 : Set pos = -1 and k = 0
Step 2 : Repeat while k <N
Begin
Step3 :ifA[k]= val
Setpos=k
print pos
Gotostep5
Endwhile
Step4:print“Valueisnot present”
Step5 :Exit

NonrecursiveC++programforLinearsearch

#include<iostream>usi
ngnamespacestd;
intLsearch(intlist[],intn,intkey); int
main()
{
int n,i,key,list[25],pos;
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"elements";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"enterkeytosearch";
cin>>key;
pos=Lsearch(list,n,key);
if(pos==-1)
cout<<"\nelementnotfound";
else

69
 cout<<"\nelementfoundatindex"<<pos;
}
/*functionforlinearsearch*/
intLsearch(intlist[],intn,int key)
{
inti,pos=-1;
for(i=0;i<n;i++)
if(key==list[i])
{
pos=i;
break;
}
return pos;
}

Run1:
enternoofelements5
enter5elements9988724
enter key to search 7
element found at index2

Run2:
enternoofelements5
enter5elements9988724
enter key to search 88
element not found

RecursiveC++programforLinearsearch

#include<iostream>usi
ngnamespacestd;
intRec_Lsearch(intlist[],intn,intkey); int
main()
{
int n,i,key,list[25],pos;
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"elements";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"enter key to search";
cin>>key;
pos=Rec_Lsearch(list,n-1,key);
if(pos==-1)
cout<<"\nelementnotfound";
else
cout<<"\nelementfoundatindex"<<pos;
}

70
/*recursivefunctionforlinearsearch*/
intRec_Lsearch(intlist[],intn,intkey)
{
if(n<0)
return -1;
if(list[n]==key)
returnn;
else
returnRec_Lsearch(list,n-1,key);
}

RUN1:
enternoofelements5
enter5elements555-4997
enter key tosearch-4 element
found at index2

RUN2:
enternoofelements5
enter5elements555-4997
enter key tosearch77 element
not found

BINARYSEARCHING

Binary search is a fast search algorithm with run-time complexity ofΟ(log n). This searchalgorithm
works onthe principle ofdivide and conquer. Binary search looks fora particularitem by comparing
the middle most item of the collection. If a match occurs, then the index of item is [Link]
middle item isgreaterthan the item,then the itemissearchedinthe 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
[Link]-array aswelluntilthe size ofthe subarray reduces to zero.
Beforeapplyingbinarysearching,thelistofitemsshouldbesortedinascendingor descending order.
BestcasetimecomplexityisO(1) Worst
case time complexity isO(logn)

71
Algorithm:
Binary_Search(A[],U_bound,VAL)
Step1:setBEG=0, END=U_bound, POS =-1 Step 2 :
Repeat while (BEG <= END)
Step3: setMID=(BEG+END)/2
Step4: ifA[MID]==VALthen
POS=MID
printVAL“isavailableat“,POS GoTo
Step 6
Endif
ifA[MID]>VALthen set
END = MID – 1
Else
setBEG= MID+ 1
Endif
Endwhile
Step 5 :ifPOS=-1 then
printVAL“isnotpresent“ End
if
Step6 :EXIT

NonrecursiveC++programforbinarysearch

#include<iostream>usi
ngnamespacestd;
intbinary_search(intlist[],intkey,intlow,inthigh); int
main()
{
int n,i,key,list[25],pos;
cout<<"enternoofelements\n";

72
 cin>>n;
cout<<"enter"<<n<<"elementsinascendingorder";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"enter key to search" ;
cin>>key;
pos=binary_search(list,key,0,n-1);
if(pos==-1)
cout<<"elementnotfound";
else
cout<<"elementfoundatindex"<<pos;
}
/*functionforbinarysearch*/
intbinary_search(intlist[],intkey,intlow,inthigh)
{
intmid,pos=-1;
while(low<=high)
{
mid=(low+high)/2;
if(key==list[mid])
{
pos=mid;
break;

}
elseif(key<list[mid])
high=mid-1;
else
low=mid+1;
}
return pos;
}
Run1:
enter noofelements5
enter5elements inascendingorder1122334455 enter
key to search33
elementfoundatindex2
Run2:
enter noofelements5
enter5elements inascendingorder1122334455 enter
key to search21
elementNot found

RecursiveC++programforbinarysearch
#include<iostream>usi
ngnamespacestd;
intrbinary_search(intlist[],intkey,intlow,inthigh); int
main()
{

73
int n,i,key,list[25],pos;
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"elementsinascendingorder";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"enter key to search" ;
cin>>key;
pos=rbinary_search(list,key,0,n-1);
if(pos==-1)
cout<<"elementnotfound";
else
cout<<"elementfoundatindex"<<pos;
}
/*recursivefunctionforbinarysearch*/
intrbinary_search(intlist[],intkey,intlow,inthigh)
{
intmid,pos=-1;
if(low<=high)
{
mid=(low+high)/2;
if(key==list[mid])
{
pos=mid;
returnpos;
}
elseif(key<list[mid])
returnrbinary_search(list,key,low,mid-1);
else
returnrbinary_search(list,key,mid+1,high);
}
return pos;
}

RUN1:
enternoof elements5
enter 5elementsinascendingorder 1122334466 enter
key to search33
elementfoundatindex2
RUN 2:
enternoofelements5
enter 5elementsinascendingorder 1122334466 enter
key to search77
elementnot found

SORTING

Arrangingtheelementsinalist [Link]
algorithms are
 Bubblesort

74
  selectionsort
 Insertionsort
 Quicksort
 Mergesort
 Heapsort

Bubblesort

The bubble sort is an example ofexchange sort. In thismethod,repetitivecomparisonis performed among

elements and essential swapping of elements is done. Bubble sort is commonly used in sorting
[Link] number of comparisons to sort a
list . In this type, two successive elements are compared and swapping is done. Thus, step-by-step
entire array elements are checked. It is different from the selection [Link] of searching the
minimum elementand thenapplyingswapping,two records are swapped instantly upon noticing that
they are not inorder.

ALGORITHM:
Bubble_Sort(A [],N )
Step1:Start
Step2:Takeanarrayofnelements Step 3:
for i=0,..............................n-2
Step4:forj=i+1,…….n-1
Step 5: ifarr[j]>arr[j+1] then
Interchangearr[j]andarr[j+1]
End of if
Step6:Printthesortedarrayarr Step
7:Stop
#include<iostream>usingn
amespacestd;
voidbubble_sort(intlist[30],intn); int
main()
{
intn,i;
intlist[30];
cout<<"enternoofelements\n"; cin>>n;
cout<<"enter"<<n<<"numbers"; for(i=0;i<n;i++)
cin>>list[i];
bubble_sort(list,n);
cout<<"aftersorting\n"; for(i=0;i<n;i+
+) cout<<list[i]<<endl;
return0;
}

voidbubble_sort(intlist[30],intn)

75
{
inttemp;
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n-1;j++)
if(list[j]>list[j+1])
{
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
}
}

RUN1:
enternoofelements
5
enter 5numbers54321
after sorting1 2 34 5..

Selectionsort

selectionsort:-Selectionsort(SelectthesmallestandExchange ):
The first item is compared with the remaining n-1 items, and whichever ofall is lowest, is
putin the [Link] the second item from the list is taken and compared withthe remaining
(n-2) items, if an item with a valueless than that of the seconditemisfoundon the (n- 2) items, it
isswapped (Interchanged) with the second item of the list andsoon.

Algorithm:Selection_Sort
(A[],N) Step 1 :start
Step2:RepeatFor K=0toN –2
Begin
Step3: Set POS=K

76
 Step 4 : Repeatfor J=K+1toN –1
Begin
IfA[J]< A[POS]
SetPOS=J
EndFor
Step 5 : SwapA[K]withA[POS ] End
For
Step6 :stop

#include<iostream>usi
ngnamespacestd;
voidselection_sort(intlist[],intn);
int main()
{
intn,i;
intlist[30];
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"numbers"; for(i=0;i<n;i+
+)
cin>>list[i];
selection_sort (list,n);
cout<<"aftersorting\n";
for(i=0;i<n;i++)
cout<<list[i]<<endl;
return0;
}
voidselection_sort(intlist[],intn)
{
int min,temp,i,j;
for(i=0;i<n;i++)
{
min=i; for(j=i+1;j<n;j+
+)
{
if(list[j]<list[min])
min=j;
}
temp=list[i];
list[i]=list[min];
list[min]=temp;
}
}

RUN 1:
enternoofelements 5
enter5numbers54321
aftersorting12345

77
 INSERTIONSORT
Insertion sort: It iterates, consuming one input element each repetition, and growing a sorted
[Link],insertionsortremovesoneelementfromtheinputdata, finds the
locationitbelongswithinthesortedlist,[Link] remain.

ALGORITHM:
Step1:start
Step2:
fori←1tolength(A) Step
3: j←i
Step 4: whilej>0andA[j-1]>A[j]
Step 5: swap A[j] and A[j-1]
Step 6: j ← j - 1
Step 7:

endwhile Step
8: end for
Step9: stop

programtoimplementinsertionsort
#include<iostream>usi
ngnamespacestd;
voidinsertion_sort(inta[],intn)
{
inti,t,pos;
for(i=0;i<n;i++)
{

78
 t=a[i];
pos=i;
while(pos>0&&a[pos-1]>t)
{
a[pos]=a[pos-1];
pos--;
}
a[pos]=t;
}
}
intmain()
{
intn,i;
intlist[30];
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"numbers"; for(i=0;i<n;i+
+)
cin>>list[i];
insertion_sort(list,n);
cout<<"aftersorting\n";
for(i=0;i<n;i++)
cout<<list[i]<<endl;
return0;
}

RUN1:
enternoofelements5
enter 5numbers55443322 11

after sorting11 22 334455

Quicksort

Quick sort: It is a divide and conquer algorithm. Developed by Tony Hoare in1959. Quick sort
first divides a large array into two smaller sub-arrays: the low elements and thehigh elements. Quick
sort can then recursively sort the sub-arrays.
ALGORITHM:

Step1:Pickanelement,calledapivot,fromthearray.
Step 2: Partitioning: reorder the array so that all elements with values less than the pivot come
beforethepivot, whileallelementswithvaluesgreater thanthepivotcomeafter it(equal values
cango either way). After this partitioning, thepivot is inits finalposition. This is called the
partition operation.
Step3:Recursivelyapplytheabovestepstothesub-arrayof elements withsmaller valuesand separately
to the sub-array of elements with greater values.

79
80
81
programtoimplementQuicksort
#include<iostream.h>
intpartition(intx[],intlow,inthigh)
{
int down,up,pivot,t;
if(low<high)
{
down=low;
up=high;
pivot=down;
while(down<up)
{
while((x[down]<=x[pivot])&&(down<high))down++;
while(x[up]>x[pivot])up--;
if(down<up)
{
t=x[down];
x[down]=x[up];
x[up]=t;
}/*endif*/
}
t=x[pivot];
x[pivot]=x[up];
x[up]=t;
}
return up;
}
voidquicksort(intx[],intlow,inthigh)
{
intp;
if(low<high)
{
p=partition(x,low,high);
quicksort(x,low,p-1);
quicksort(x,p+1,high);
}
}
int main()
{
intn,i;
int list[30];
cout<<"enternoofelements\n";

82
 cin>>n;
cout<<"enter"<<n<<"numbers";
for(i=0;i<n;i++)
cin>>list[i];
quicksort(list,0,n-1);
cout<<"aftersorting\n";
for(i=0;i<n;i++)
cout<<list[i]<<endl;
return 0;
}

enternoofelements 5
enter5numbers54321
aftersorting12345
Mergesort

Merge sort is a sorting technique based on divide and conquer technique. In mergesortthe unsorted
list is divided into N sublists, each having one element, because a list of one element is considered
sorted. Then, it repeatedly merge these sublists, to produce new sorted sublists, and at lasts one
sortedlist is [Link] Sortis quite fast, and has a time complexity of O(n log n).

Conceptually,mergesortworksasfollows:
1. Dividetheunsortedlistintotwosublistsofabouthalf thesize.
2. Divideeachofthetwosub listsrecursivelyuntilwehavelistsizes of length1,inwhichcasethe list itself
is returned.
3. Mergethetwosublists backinto onesortedlist.

#include<iostream>usi
ngnamespacestd;
voidmerge(inta[],intlow,int mid,int high)
{
inttemp[100];

83
inti,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<=a[j])
{
temp[k]=a[i];
++i;
}
else
{
temp[k]=a[j];
++j;
}
++k;
}
if(i>mid)
{
while(j<=high)
{
temp[k]=a[j];
++j;
++k;
}
}
else
{
while(i<=mid)
{
temp[k]=a[i];
++i;
++k;
}
}
for(inti=low;i<=high;i++)
a[i]=temp[i];
}

voidmergesort(inta[],intlow,inthigh)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
}

84
intmain()
{
intn,i;
intlist[30];
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"numbers"; for(i=0;i<n;i+
+)
cin>>list[i];mergesort
(list,0,n-1);
cout<<"aftersorting\n";
for(i=0;i<n;i++) cout<<list[i]<<”\
t”;
return0;
}

RUN1:

enternoofelements5
enter5 numbers44335511-1
after sorting-1 113344 55

Heapsort

It is a completely binary tree with the property that a parent is always greaterthan orequal to
either ofits children (if they exist). first the heap (max ormin) is created using binary tree and then
heap is sorted using priorityqueue.

StepsFollowed:

a) [Link].
b) Insertnextelementsandmakethisheap.
c) Repeatstepb,untilallelementsareincludedintheheap. Steps
of Sorting:
a) Exchangetherootandlastelementintheheap.
b) Makethisheap again,butthistimedonotincludethelastnode.
c) Repeatstepsaandbuntilthereisnoelementleft.

C++programforimplementationofHeap Sort

#include <iostream>
usingnamespacestd;
//Toheapifyasubtreerootedwithnodeiwhichis
//anindex inarr[].nissizeofheap void
heapify(int arr[], int n, int i)
{
intlargest=i;//Initializelargestasroot int
L= 2*i + 1; // left = 2*i +1
int R=2*i+2;//right =2*i+ 2

85
 //Ifleftchildislargerthanroot
if(L<n&&arr[L]>arr[largest]) largest =
L;
//Ifrightchildislargerthanlargestsofar if (R
< n && arr[R] > arr[largest])
largest=R;
//Iflargestisnotroot if
(largest !=i)
{
swap(arr[i],arr[largest]);
//Recursivelyheapifytheaffectedsub-tree
heapify(arr, n, largest);
}
}

voidheapSort(intarr[],intn)
{inti;
//Buildheap(rearrangearray)
for ( i = n / 2 - 1; i >= 0; i--)
heapify(arr,n,i);

//Onebyoneextractanelementfromheap for (
i=n-1; i>=0; i--)
{
//Movecurrentroottoend swap(arr[0],
arr[i]);

//callmaxheapifyonthereducedheap heapify(arr,
i, 0);
}
}

/*Autilityfunctiontoprintarrayofsizen*/ void
printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout<<arr[i]<<"";
cout<<"\n";
}
intmain()
{
intn,i;
intlist[30];
cout<<"enternoofelements\n";
cin>>n;
cout<<"enter"<<n<<"numbers"; for(i=0;i<n;i+
+)
cin>>list[i];
heapSort(list,n);
cout<<"Sortedarrayis\n"; printArray(list,
n);

86
 return0;
}
RUN1:
enternoofelements5
enter5numbers1199221011
Sorted array is
1 112299101

Timecomplexities:

Algorithm Worstcase Averagecase Bestcase

2 2
Bubblesort O(n ) O(n ) O(n2)
selectionsort O(n2) O(n2) O(n2)
Insertionsort O(n2) O(n2) O(n2)
Quicksort O(nlog n) O(nlog n) O(n2)
Mergesort O(nlog n) O(nlog n) O(nlog n)
Heapsort O(nlog n) O(nlog n) O(nlog n)
Linear search O(n) O(n) O(1)
Binarysearch O(logn) O(logn) O(1)

87
 UNIT-IV

DICTIONARIES:
Dictionaryisacollectionofpairsofkeyandvaluewhere everyvalueisassociatedwiththe corresponding
key.
Basicoperationsthatcanbeperformedondictionaryare:
1. Insertionofvalueinthedictionary
2. Deletionofparticularvaluefromdictionary
3. Searchingofaspecificvaluewiththehelpofkey

LinearListRepresentation
The dictionary can berepresentedas a linear list. The linear list is a collection of pair and value.
There are twomethod of representing linear list.
1. SortedArray-Anarraydatastructureisusedtoimplementthedictionary.
2. SortedChain-Alinkedlistdatastructureisusedtoimplementthedictionary

Structureoflinearlistfordictionary:

classdictionary
{

private:
intk,data;
structnode
{
public:intkey; int
value;
structnode*next;
}*head;

public:
dictionary();void
insert_d( ); void
delete_d( );
voiddisplay_d();
void length();
};

Insertionofnewnodeinthedictionary:
Consider that initially dictionary is empty then
head = NULL
Wewillcreateanewnodewithsomekeyandvaluecontainedinit.

88
Now as head is NULL, thisnew node becomes head. Hence the dictionary containsonly one record.
this node will be ‘curr’ and ‘prev’ as well. The ‘cuur’ node will always point to current visiting node
and ‘prev’will always pointto thenode previous to ‘curr’ [Link] now thereis only one node inthe
list mark as ‘curr’ node as ‘prev’node.

New/head/curr/prev

1 10 NULL

Insertarecord,key=4andvalue=20,

New

4 20 NULL

Compare the key value of ‘curr’and ‘New’[Link] New->key > Curr->key then attach New node to
‘curr’ node.

prev/head New curr->next=New

prev=curr
1 10 4 20 NULL

Addanewnode<7,80>then

head/prev curr New

1 10 4 20 7 80 NULL

Ifweinsert<3,15>thenwehavetosearchfor itproper positionbycomparingkeyvalue. (curr-

>key < New->key) is false. Hence else part will get executed.

1 10 4 20 7 80 NULL

3 15

voiddictionary::insert_d()
{
node *p,*curr,*prev;
cout<<"Enterankeyandvaluetobeinserted:"; cin>>k;
cin>>data;

89
 p=newnode;
p->key=k;
p->value=data;
p->next=NULL;
if(head==NULL)
head=p;
else
{
curr=head;
while((curr->key<p->key)&&(curr->next!=NULL))
{
prev=curr;
curr=curr->next;
}
if(curr->next==NULL)
{
if(curr->key<p->key)
{
curr->next=p;
prev=curr;
}
else
{
p->next=prev->next;
prev->next=p;
}
}
else
{
p->next=prev->next;
prev->next=p;
}
cout<<"\nInsertedintodictionarySucesfully.........\n";
}
}

Thedeleteoperation:

Case 1:Initially assign ‘head’node as‘curr’[Link] askforakeyvalueofthenodewhichis to be

deleted. Then starting from head node key value of each jode is cked and compared with the desired
node’s key value. We will get node which isto be deletedinvariable ‘curr’. Thenode given by
variable ‘prev’ keeps track of previous node of ‘cuu’ node. For eg, delete node with key value 4 then

cur

1 10 3 15 4 20 7 80 ULL

90
Case2:

Ifthenodetobedeletedisheadnode i.e..
if(curr==head)

Then, simply make‘head’nodeasnext nodeanddelete‘curr’

curr head
1 10 3 15 4 20 7 80 ULL

Hencethelist becomes

head
3 15 4 20 7 80 ULL

voiddictionary::delete_d()
{
node*curr,*prev;
cout<<"Enterkeyvaluethatyouwanttodelete...";
cin>>k;
if(head==NULL)
cout<<"\ndictionaryisUnderflow";
else
{ curr=head;
while(curr!=NULL)
{
if(curr->key==k)
break;
prev=curr;
curr=curr->next;
}
}
if(curr==NULL)
cout<<"Nodenotfound...";
else
{
if(curr==head)

91
 head=curr->next;
else
prev->next=curr->next;
deletecurr;
cout<<"Itemdeletedfromdictionary...";
}
}

The length operation:

intdictionary::length()
{
structnode*curr;
int count;
count=0;
curr=head;
if(curr==NULL)
{
cout<<”Thelistisempty”;
return 0;
}
while(curr!=NULL)
{
count++;
cur=curr->next;
}
returncount;
}

SKIPLISTREPRESENTATION
Skip list isa variant list for thelinked [Link] lists aremadeup of a series
of nodes connected one after the other. Each node contains a key and value pair as well as one or
more references, or pointers, tonodes further along in the list. The number of references
[Link] liststheir probabilisticnature, andthe
number of references a node contains is called its nodelevel.
Therearetwospecialnodes intheskip list oneis headnodewhichis thestartingnodeofthelist and tail
node is the last node of the list

1 2 3 4 5 6 7
head tail
node node
Theskiplistisanefficient implementationofdictionaryusingsortedchain. Thisisbecausein skip list
each node consists of forward references of more than one node at a time.

92
Eg:

null

Nowtosearchany nodefromabove givensortedchainwe havetosearchthesortedchainfrom head

node by visiting each node. But this searching timecan bereduced if weadd onelevel in
everyalternatenode. This extralevelcontainstheforwardpointer of somenode. Thatmeansin sorted
chain come nodes can holds pointers to morethan onenode.

NULL

Ifwewant tosearchnode40 fromabovechaintherewewillrequire comparativelyless time. This search

again can be made efficient if we add few more pointers forwardreferences.

NULL

skip list

Nodestructureofskiplist:

template<classK,classE> struct
skipnode
{
typedefpair<constK,E>pair_type;
pair_type element;
skipnode<K,E>**next;
skipnode(constpair_type&New_pair,intMAX):element(New_pair)
{
next=newskipnode<K,E>*[MAX];
}
};

93
 Theindividualnodelookslikethis:

Key value arrayof pointer

Element *next
Searching:
Thedesirednodeissearchedwiththehelpofakeyvalue.

template<classK,classE>
skipnode<K,E>*skipLst<K,E>::search(K&Key_val)
{
skipnode<K,E>*Forward_Node=header; for(int i=level;i>=0;i--)
{
while(Forward_Node->next[i]->[Link]<key_val) Forward_Node = Forward_Node->next[i];
last[i]=Forward_Node;
}
returnForward_Node->next[0];
}

Searching for a key within a skip list begins with starting at header at the overall list level and
moving forward in the list comparing node keys to the key_val. If the node key is less than the
key_val,the search continuesmoving forward at [Link] o the otherhand,thenode key is equal
to or greater than the key_val, the search drops one level and continues forward. This
processcontinuesuntil the desired key_valhasbeen foundif it ispresentin the [Link] itis not, the
search will either continue at the end of the list oruntil the first key with avaluegreater than the
search key is found.
Insertion:
Therearetwotasks thatshouldbedonebeforeinsertionoperation:
1. Before insertion of any node the place for this new node in the skip list is searched. Hence
before any insertion to take place the search routine executes. The last[] array in the search
routine is used to keep track ofthe references to the nodes wherethe search,drops down one
level.
2. Thelevelforthenewnodeisretrievedbytheroutinerandomelevel()

template<classK,classE>
voidskipLst<K,E>::insert(pair<K,E>&New_pair)
{
if(New_pair.key>= tailkey)
{
cout<<”Keyistoolarge”;
}

skipNode<K,E>*temp=search(New_pair.key);
if(temp->[Link] == New_pair.key)

94
 {
temp->[Link]=New_pair.value;
return;
}

if*New_Level>levels)
{
New_Level = ++levels;
last[New_Level]=header;
}

skipNode<K,E>*newNode=newskipNode<K,E>(New_pair,New_Level+1);

for(int i=0;i<=New_Level;i++)
{
newNode->next[i]=last[i]->next[i];
last[i]->next[i] = newNode;
}
len++;
return;
}

Determiningthe levelofeach node:

template<classK,class E>
int skipLst<K,E>::randomlevel()
{
intlvl=0;
while(rand()<=Lvl_No) lvl=lvl+1; if(lvl<=MaxLvl)
returnlvl; else
returnMaxLvl;
}

Deletion:
First ofall,thedeletionmakesuseofsearchalgorithmandsearchesthenodethatistobedeleted. If the key
to be deleted is found, the node containing the key isremoved.

template<classK,classE>
voidskipLst<K,E>::delet(K&Key_val)
{
if(key_val>=tailKey)
return;
skipNode<K,E>*temp=search(Key_val);
if(temp->[Link] != Key_val)
return;

for(inti=0;i<=levels;i++)

95
{
if(last[i]->next[i] == temp)
last[i]=>next[i]=temp->next[i];
}

while(level>0&&header->next[level]==tail)
levels--;
deletetemp;
len--;
}

HASHTABLEREPRESENTATION
 Hash table is a data structure used for storing and retrieving data very quickly. Insertion of
data in the hash table is based on the key value. Hence every entry in the hash table is
associated with some key.
 Using the hash key the required piece of data can be searched in the hash table by few or
more key comparisons. The searching time is then dependent upon the size ofthe hashtable.
 The effective representation of dictionary can be done using hash table. We can place the
dictionary entries in the hash table using hash function.
HASHFUNCTION
 Hash function is afunction which is used to put the datain the hash [Link] one can use
the same hash function to retrieve the data from the hash table. Thus hash function is used to
implement the hashtable.
 Theintegerreturnedbythehashfunctioniscalledhashkey.

For example: Consider that we want place some employee records in the hash table The record of
employee is placed with the help of key: employee ID. The employee ID is a 7 digit number for
placing the record in the hash [Link] place the record 7digitnumberis converted into3 digits by
taking only last three digits of the key.

Ifthekey is 496700 itcanbestoredat [Link] key8421002,therecordofthose key is

placed at 2nd position in the array.
Hencethehashfunctionwillbe-H(key)= key%1000
Wherekey%1000isahashfunctionandkeyobtainedbyhashfunctioniscalledhash key.

 Bucket and Home bucket: The hash function H(key) is used to map several dictionary
entries in the hash table. Eachposition of thehash table is called bucket.

ThefunctionH(key)ishomebucket forthedictionarywithpairwhosevalueiskey.

TYPES OFHASH FUNCTION

Therearevarious types ofhashfunctionsthatareusedtoplacetherecordinthehashtable-

1. DivisionMethod:Thehashfunctiondependsupontheremainder of division.
Typically the divisor is table length.
Foreg;Iftherecord54,72,89,37is placedinthehashtableandifthetablesizeis 10 then

96
h(key)= record%table size 0
1
54%10=4 2 72
72%10=2 3
89%10=9 4 54
37%10=7 5
6
7 37
8
9 89
2. MidSquare:
Inthemidsquaremethod, thekeyis squaredandthemiddleor midpartoftheresult is usedasthe index. If
the key is a string, it has to be preprocessed to produce a number.
Considerthatifwewanttoplacearecord3111then

31112=9678321
for the hash table of size 1000
H(3111)=783(themiddle3digits)

3. Multiplicativehashfunction:
Thegivenrecord ismultipliedby [Link] forcomputingthehash key is-

H(key)=floor(p *(fractionalpartofkey*A)) wherepisinteger constantandAisconstantreal number.

DonaldKnuthsuggestedtouseconstantA= 0.61803398987

Ifkey107 andp=50then

H(key)=floor(50*(107*0.61803398987))
=floor(3306.4818458045)
=3306
At3306 locationinthehashtabletherecord107 will beplaced.

4. DigitFolding:
Thekeyis dividedintoseparatepartsandusingsomesimpleoperationthesepartsare combined to
produce the hash key.
For eg;consider arecord12365412thenitisdividedintoseparatepartsas12365412andthese are added
together

H(key)=123+654+12
=789
Therecordwillbeplacedatlocation789

5. DigitAnalysis:
The digit analysis is used in a situation when all the identifiers are known in advance. We
first transform the identifiers into numbers using some radix, r. Then examine the digits of each
identifier. Some digits having most skewed distributions are deleted. This deleting of digits is
continued until the numberofremaining digits is small enough to givean addressin the range of the
hash table. Then these digits are used tocalculate the hash address.

97
COLLISION
the hash functionis afunction that returns thekey value using which the recordcan be placedin the
hash table. Thus this function helps us in placing the record in the hash table at appropriate position
and due tothis wecan retrieve the recorddirectly fromthat [Link] need to be designed
very carefully and it should not return the same hash key address for two different records. This is an
undesirable situation in hashing.

Definition: Thesituationin whichthehashfunctionreturns thesame hash key(homebucket)for more than one record is ca

Similarly when there is no room for a new pair in the hash table then such a situation is
called overflow. Sometimeswhen we handle collision it maylead tooverflowconditions. Collision
and overflow show the poor hashfunctions.

Forexample, 0
1 131
Considerahashfunction. 2
3 43
H(key)=recordkey%10havingthehashtablesizeof10 4 44
5
Therecordkeystobeplacedare 6 36
7 57
131, 44,43,78, 19, 36,57and 77 8 78
131%10=1 9 19
44%10=4
43%10=3
78%10=8
19%10=9
36%10=6
57%10=7
77%10=7

Now ifwe try to place 77in the hash table then we get the hash key to be 7 and at index 7 already the
record key 57 is placed. This situation is called collision. From the index 7 if we look for next
vacant position at subsequent indices 8.9 then we find that there is no room to place 77 in the hash
table. This situation is called overflow.

COLLISIONRESOLUTIONTECHNIQUES
Ifcollisionoccursthen itshouldbe handledby [Link] technique
is called collision handlingtechnique.
1. Chaining
2. Openaddressing(linearprobing)
3. Quadraticprobing
4. Double hashing
5. Double hashing
6. Rehashing

98
 CHAINING
Incollisionhandlingmethodchainingisaconceptwhichintroducesanadditionalfieldwithdata
i.e. chain. Aseparatechaintableis maintainedfor [Link] linked
list(chain) is maintained at the homebucket.

Foreg;

Consider thekeystobeplacedintheir homebucketsare 131, 3, 4,

21, 61, 7, 97, 8, 9

thenwewillapplya hashfunctionasH(key)=key%D Where D

is thesize of table. The hash table will be- Here D = 10

0
1 131 21 61
NULL

3
NULL

61 NULL
131

97 NULL
7

Achain is maintained for colliding elements. for instance131 hasa homebucket(key)1.

similarlykey21 and61 demand for homebucket 1. Hence a chainis maintained at index 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 the second record
linearly down whenever the empty bucket is found. When use linear probing (open
addressing),thehash table isrepresentedasaone-dimensional array with indicesthatrange from 0 to the
desired table [Link] inserting anyelements into this table,wemust initialize the table to
represent the situation where all slots are empty. This allows us to detect overflows and collisions
when we inset elements into the table. Then using some suitable hash functiontheelement can be
inserted into the hashtable.

Forexample:

Consider thatfollowingkeys aretobeinsertedinthehashtable 131, 4, 8,

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

99
Initially,wewillputthefollowingkeysinthehashtable.
[Link] areplacedusingtheformula

H(key)=key%tablesize
H(key) = key % 10

Forinstancetheelement131canbeplacedat H(key)

= 131 % 10
=1

Index 1 willbethehomebucket for [Link] fashionwewillplace4, 8,7. Now

the next key to be inserted is 21. According to the hash function

H(key)=21%10
H(key)=1

But the index 1 location is already occupied by 131 [Link] occurs. Toresolve this collision
wewilllinearly movedownand at the nextempty location wewillprobthe [Link] 21will
beplaced at the [Link] the nextelementis5then wegetthe home bucketfor5 as index 5 and this
bucket is empty so we will put theelement 5 at index 5.

Index
Key Key Key

NULL NULL NULL

0
131 131 131
1
NULL 21 21
2
NULL NULL 31
3
4 4 4
4
NULL 5 5
5
NULL NULL 61
6
7 7 7
7
8 8 8
8
NULL NULL NULL
9

afterplacingkeys31,61

100
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 [Link] the next final record key 29and ithashes akey [Link] home
bucket9is [Link] table sizeislimited to index 9. The
overflow occurs. To handle it we move back to bucket 0 and is the location over there is empty 29
will be placed at 0thindex.
Problemwithlinearprobing:
One major problem with linear probing is primary clustering. Primary clustering is a process in
which a block of data is formed in the hash table when collision is resolved.
Key

19%10=9 clusterisformed 39
18%10=8 29
39%10=9 8
29%10=9
8%10=8

restofthetableisempty

this cluster problem can be solved by quadratic probing.

18

QUADRATICPROBING: 19

Quadraticprobingoperatesbytakingtheoriginalhashvalueandaddingsuccessivevalues ofan arbitrary

quadratic polynomial to the starting value. This method uses following formula.

H(key)=(Hash(key)+i2)%m)

where mcanbetablesizeoranyprime number.

for eg;Ifwehavetoinsertfollowingelementsinthe hashtablewithtablesize10:

37,90,55,22,17,49,87 0 90
1 11
37% 10=7 2 22
90% 10=0 3
55% 10=5 4
22% 10=2 5 55
11%10=1 6
7 37
Nowifwewant toplace17acollisionwilloccuras 17%10= 7and 8
bucket7hasalreadyanelement37. Hencewewill apply 9
quadraticprobingtoinsert thisrecordinthehashtable.

Hi(key)=(Hash(key)+i2)%m

Consideri=0then
(17 +02)%10=7

101
(17 + 12)%10=8,wheni=1

Thebucket8is emptyhencewewill placetheelementatindex8. 0 90

Thencomes49whichwillbeplacedatindex 9. 1 11
2 22
49% 10=9 3
4
5 55
6
7 37
8 49
9
Nowtoplace87wewillusequadraticprobing.
0
90
(87+0)%10=7 1 11
(87 + 1)%10=8…
2
butalreadyoccupied 2 22
(87 + 22 )%10=1..alreadyoccupied 3
(87 +3 )%10=6
Itisobservedthatifwewantplaceallthenecessaryelements 45
in
thehashtablethesizeofdivisor(m)shouldbetwiceaslarge 6 55
as
totalnumberof 7 87
elements. 37
8 49
DOUBLE 9
HASHING
Double hashingis technique in which asecond hash functionis applied to thekeywhena collision
[Link] applying the second hash function we will getthenumberof positions from the point of
collision to insert.
Therearetwoimportant rules tobefollowedforthesecondfunction:
 itmustneverevaluatetozero.
 mustmakesurethatallcellscanbeprobed.
Theformulatobeusedfordoublehashingis

whereMisaprimenumbersmallerthanthesizeofthetable.
H1(key)=keymodtablesize
Key
Consider thefollowingelementstobeplacedinthehash
H2(key)=M –(keymodM) tableofsize10 37, 90,
90
45, 22, 17, 49, 55
InitiallyinserttheelementsusingtheformulaforH1(key). Insert
37, 90, 45, 22 22

H1(37)=37%10=7
H1(90)= 90%10=0
H1(45)=45%10=5 45

H1(22)=22%10=2
H1(49)=49%10=9
37

49

102
Nowif17tobeinsertedthen H1(17)
Key
= 17 % 10 = 7
90
H2(key)=M –(key%M)
17

HereMisprimenumber smaller [Link] 22

smaller than table size 10 is 7

Hence M
45
=7H2(17)=7-(17%7)
=7–3=4
37
Thatmeanswehavetoinsert theelement 17at 4places from37. Inshort wehav jumps. etotake
Therefore the 17 will be placed at index 1.
49

Nowtoinsertnumber 55

H1(55) = 55 %10 =5 Collision Key

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

Thatmeans wehavetotakeonejump fromindex 5 toplace55. Finally the

hash table will be -
45

55

37

49
ComparisonofQuadraticProbing&DoubleHashing

Thedoublehashingrequiresanother hashfunctionwhoseprobingefficiencyissame as some

another hash function required when handling randomcollision.
Thedoublehashingis [Link] probing
is fast technique than double hashing.

REHASHING

Rehashingis atechniquein which the tableis resized,i.e.,the size of table isdoubledbycreating anew
[Link] preferable isthe total size oftableis aprime [Link] are situationsin which the
rehashing is required.

 Whentableiscompletelyfull
 Withquadraticprobingwhenthetableisfilledhalf.
 Wheninsertions failduetooverflow.

103
Insuchsituations, wehavetotransfer entries fromoldtabletothe newtableby recomputing their
positions using hash functions.

Consider wehavetoinsert theelements37, 90,55,22,17, 49,and87. thetablesizeis10andwill use hash

function.,

H(key)=keymodtablesize

37% 10=7
90% 10=0
55% 10=5
22% 10=2
17%10=7Collisionsolvedby linear probing 49 % 10
=9

Now this table is almost full and if we try to insert more elements collisions will occur and eventually
furtherinsertionswill fail. Hence we will rehashbydoubling the table size. Theold table size is10 then
we should double this size fornew table,that becomes [Link] 20 isnota prime number,we will
preferto make the table size as 23. And new hash function will be

H(key)keymod 23 0 90
1 11
37% 23=14 2 22
90% 23=21 3
55% 23=9 4
22% 23=22 5 55
17% 23=17 6 87
49% 23=3 7 37
87% 23=18 8 49
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Nowthehashtableissufficientlylargetoaccommodatenewinsertions.

Advantages:

104
 1. Thistechniqueprovidestheprogrammeraflexibilitytoenlargethetablesizeifrequired.
2. Onlythespacegetsdoubledwithsimplehashfunctionwhichavoidsoccurrence of
collisions.

EXTENSIBLEHASHING

 Extensiblehashing isa techniquewhichhandlesa largeamount of [Link]

placed in the hash table is by extracting certain number ofbits.
 Extensiblehashinggrowandshrinksimilar toB-trees.
 Inextensiblehashingreferringthesizeofdirectory theelementsaretobeplacedin buckets.
The levels are indicated in parenthesis.

Foreg: Directory

0 1

Levels
(0) (1)
001 111
010 data to be
placedinbucket

 Thebucket canholdthedata ofitsglobal depth. Ifdata inbucket ismorethanglobal depth

then, split the bucket and double thedirectory.

Consider wehavetoinsert 1,4, 5, 7,8,10.Assumeeachpagecanhold2dataentries(2isthe depth).

Step1: Insert1,4
0 1=001

4=100
(0)
001 We will examine last bit
010 ofdataandinsertthedata in
bucket.

[Link]. Hencedoublethedirectory.

105
 1=001
0 1

4=100
(0) (1)
100 001 5=101
010
Basedonlastbitthedata is
inserted.

Step2:Insert 7
7=111
Butasdepthisfullwecannotinsert7here. Thendoublethedirectoryand splitthebucket. After
insertion of 7. Now consider last two bits.

00 (1) 01 (2) 11 (2)

10

100 001 111

010

Step3:Insert 8i.e.1000

00 01 (2) 11
10
(1)
001 111
100
010
1000
Step4:Insert 0

106
Thusthedata isinsertedusingextensiblehashing.

DeletionOperation:

Ifwewantot delete10then,simply makethebucket of10 empty.

00 01 10 11

(1) (2) (2)

100 001 111
1000 101

Delete7.

00 01 10 11
(1) (1)

100 001 Notethat thelevel was increased

1000 101 whenweinsert [Link]
of7, thelevelshouldget decremented.

[Link] 00.

00 00
(1) (1) 10 11

100 001
101

Applicationsofhashing:

107
1. Incompilerstokeeptrackofdeclaredvariables.
2. Foronlinespellingcheckingthehashingfunctions areused.
3. HashinghelpsinGameplayingprogramstostorethemovesmade.
4. Forbrowserprogramwhilecachingthewebpages,hashingisused.
5. Constructamessageauthenticationcode(MAC)
6. Digitalsignature.
7. Time stamping
8. Keyupdating:keyishashedatspecificintervalsresultinginnewkey

108
UUU

UNIT-IV

TREES
ATreeisadatastructure inwhicheachelementisattachedtooneormoreelementsdirectlybeneathit.

Level0
A

B 1
C D

E F G
H I J
2
K L 3

Terminology
 Theconnectionsbetweenelementsarecalledbranches.
 Atree hasasingleroot,called rootnode,whichisshownatthetop ofthetree. [Link] isalways at the
highest level 0.
 Eachnodehasexactlyone nodeaboveit,[Link]:Aistheparent ofB,CandD.
 Thenodes justbelowanodearecalled [Link] parent
node.
 [Link]:E,F,K,L,H,IandMare
l ea v .
 N o d e s withatleastonechildarecallednonterminalorinternalnodes.
 Thechildnodesofsameparentaresaidtobesiblings.
 Apathinatree isalistofdistinctnodes inwhichsuccessivenodesareconnectedbybranches in the tree.
 Thelengthofaparticularpath isthenumberofbranches inthat [Link] node of a
tree is the number of children of that node.
 Themaximum number of children a nodecan have isoftenreferred to as the order ofa
[Link] heightordepthofa tree isthe lengthofthe longestpathfromroot toanyleaf.

1. Root:Thisistheunique [Link]:A
Degreeofthe node:The totalnumber ofsub-treesattachedtothe node iscalledthedegree ofthe [Link]: For
node A degree is 3. For node K degree is 0

3. Leaves:[Link] nodeswithdegree0arealwaysthe leafnodes. Eg: E, F,

K, L,H, I, J

109
 4. Internalnodes:Thenodesotherthantherootnodeandthe leavesarecalledthe internalnodes. Eg: B, C,
D, G
5. Parent nodes:Thenodewhichishavingfurthersub-trees(branches) iscalledtheparent nodeof those
sub-trees. Eg: B isthe parent node of E and F.
6. Predecessor:Whiledisplayingthetree, ifsomeparticularnodeoccurspreviousto someothernode then
that node iscalled the predecessor ofthe other node. Eg: E isthe predecessor ofthe node B.
7. Successor:Thenodewhichoccursnextto someothernode [Link]:Bisthe
successor of E and F.
8. Levelof the tree: The root node isalways considered at level0, then its adjacent children are
supposedto beat level1andsoon. Eg:A isat level0, B,C,Dareatlevel1, E,F,G,H,I,Jare atlevel2, K,L are
at level 3.
9. Height ofthetree:The maximumlevel istheheightofthe [Link] is3. The height
if the tree is also called depth of the tree.
10. Degreeoftree: The maximumdegreeofthenodeiscalledthedegree ofthetree.
BINARYTREES

Binarytree isa tree inwhicheachnode hasatmosttwochildren, a leftchild [Link] order of

binary tree is 2.

Abinarytreeiseitheremptyorconsists of a) a
node called the root
b) leftandrightsubtreesarethemselvesbinarytrees.

Abinarytreeisafinitesetof nodeswhichiseitherempty orconsistsofarootandtwodisjoint trees

called left sub-tree and right sub-tree.
Inbinarytreeeachnodewillhave onedata field and twopointerfields forrepresentingthe sub-
branches. The degree of each node in the binary tree will be at the most two.

TypesOfBinaryTrees:
Thereare3types ofbinarytrees:

1. Leftskewedbinarytree: Iftherightsub-tree ismissing ineverynode ofatreewe callitas left skewed

tree.
A

110
 2. Rightskewedbinarytree: Ifthe leftsub-treeismissing ineverynodeofatreewecallit isright sub-tree.

C
3. Completebinarytree:
Thetree inwhichdegree ofeach node isatthemost two iscalled acompletebinarytree. In a
complete binarytree there isexactly one node at level 0, two nodes at level 1 and four nodes at level2
l
and soon. Sowe can say that a complete binary tree depth d will contain exactly 2 nodesat each level l,
where l is from 0 to d.

B C

D E F G
Note:
n
1. Abinarytreeofdepth nwillhavemaximum2 -1nodes.
2. Acompletebinarytreeoflevel lwill havemaximum 2lnodesateachlevel,wherelstartsfrom0.
3. Anybinarytreewithnnodeswillhaveatthemostn+1nullbranches.
4. Thetotalnumberofedgesinacompletebinarytree withnterminalnodesare2(n-1).

BinaryTreeRepresentation
Abinarytreecanberepresented mainlyin2 ways:

a) SequentialRepresentation
b) LinkedRepresentation

a) SequentialRepresentation
Thesimplestwaytorepresentbinarytrees inmemoryisthesequentialrepresentationthatusesone- dimensional
array.
1) Therootofbinarytreeisstored inthe1stlocationofarray
th
2) Ifanodeisinthej locationofarray,thenitsleftchildisinthelocation2J+1anditsright
childinthelocation2J+2
d+1
Themaximumsizethatis requiredforanarraytostoreatreeis2 -1,wheredis thedepthofthetree.

111
Advantagesofsequentialrepresentation:
The onlyadvantagewiththistypeofrepresentationisthatthe
directaccesstoanynodecanbepossibleand finding theparent orleftchildrenofanyparticularnode is fast
because of the random access.

Disadvantagesofsequentialrepresentation:
1. The major disadvantage with this type of representation is wastage of memory. For example in
the skewed tree half of the array is unutilized.
2. In this type of representation the maximum depth of the tree has to be fixed. Because we have
decide the array size. If we choose the array size quite larger than the depth of the tree, then it
willbe wastage ofthe memory. And ifwe coose arraysize lesser thanthe depth ofthe tree then we
will be unable to represent some part of thetree.
3. The insertions and deletion of any node in the tree will be costlier as other nodes has to be
adjusted at appropriate positions so that the meaning of binary tree can bepreserved.
As these drawbacks are there with this sequential type of representation, we will search for more
flexible representation. So instead of array we will make use of linked list to represent the tree.
b) LinkedRepresentation
Linked representation of trees in memory is implemented using pointers. Since each node in a
binarytree canhavemaximum twochildren, a node ina linkedrepresentationhastwopointers for both left
and right child, and one information field. If a node does not have any child, the corresponding pointer
field is made NULL pointer.

Inlinked listeachnodewill look like this:

LeftChild Data RightChild

Advantagesoflinkedrepresentation:
1. This representation is superior to our array representation as there is no wastage of
memory. And so there is no need to have prior knowledge of depth of the [Link]
dynamic memory concept one can create as much memory(nodes) as required. By
chance if some nodes are unutilized one can delete the nodes by making the address
free.

2. Insertionsanddeletions whicharethemostcommonoperations canbedonewithout

moving the nodes.

112
Disadvantagesoflinkedrepresentation:

1. Thisrepresentationdoesnotprovidedirectaccesstoanodeandspecialalgorithmsare
required.
2. Thisrepresentationneedsadditionalspaceineachnodeforstoringtheleftandrightsub- trees.

TRAVERSINGABINARYTREE

Traversingatreemeansthat processing it sothat [Link] tree can

be
[Link]

 In-order
 Pre-order and
 Post-order

Pre-order [Link] Root|Left|Right

2. Traversetheleftsubtreeinpre-order
3. Traversetherightsubtreeinpre-order.
In-order 1. Traversethe leftsubtree inin-order Left|Root|Right
2. Visitthe root
3. Traversetherightsubtree inin-order.
Post-order [Link]-order Left |Right|Root
2. Traversetherightsubtreeinpost-order.
3. Visitthe root

B C

D E F G

H I J

K
Thepre-order traversal is:ABDEHCFGIKJ The
in-order traversal is : DBHEAFCKIGJ
Thepost-ordertraversalis:DHEBFKIJGCA

113
 InorderTraversal:
rd
Print3
A

Print nd th
2 Print4
B D

C Print this
at the last
Print st E
1

C-B-A-D-Eisthe inordertraversali.e. firstwegotowardstheleftmost [Link] that node

C. Then go back to the node B and print B. Then root node A then move towards the right sub-treeprint D
and finally E. Thus we are following the tracing sequence of Left|Root|Right. This type of traversal
iscalled inorder traversal. Thebasicprinciple istotraverse leftsub-treethenrootand thenthe right sub-tree.

PseudoCode:

template<classT>
voidinorder(bintree<T>*temp)
{
if(temp!=NULL)
{
inorder(temp->left);
cout<<”temp->data”;
inorder(temp->right);
}
}

isthepreordertraversalof theabove fig. Weare followingRoot|Left|Right pathi.e. dataatthe root node

willbeprinted first thenwe moveonthe leftsub-treeand goonprinting thedatatill wereachto the left
most [Link] the dataatthat node and then move tothe right sub- tree. Follow the same
principle at each sub-tree and go on printing the data accordingly.

template<class T>
voidpreorder(bintree<T>*temp)

114
{
if(temp!=NULL)
{
cout<<”temp->data”; preorder(temp->left);
preorder(temp->right);
}
}

From figure the postorder traversal is C-D-B-E-A. In the postorder traversal we are following the
Left|Right|Root principle i.e. move to the leftmost node, ifright sub-tree is there or not if not then
print the leftmost node, if right sub-tree is there move towards the right most node. The key idea
here is that at each sub-tree we are following the Left|Right|Root principle and print the data
accordingly.
PseudoCode:

template<class T>
voidpostorder(bintree<T>*temp)
{
if(temp!=NULL)
{
postorder(temp->left);
postorder(temp->right);
cout<<”temp->data”;
}
}

BINARYSEARCHTREE
In the simple binarytree the nodes are arranged in any fashion. Depending on user’s desire
the new nodescanbeattached asa leftorright childofanydesired node. Insucha case finding for any
node is a long cut procedure, because in that case we have to search the entire tree. And thus the
searching time complexity will get increased unnecessarily. So to make thesearching algorithm
faster in a binary tree we will go for building the binary search tree. The binary search tree is based
on the binary search algorithm. While creating the binary search tree the data is systematically
arranged. That means values at left sub-tree < root node value < right sub-tree values.

115
OperationsOnBinarySearchTree:
Thebasic operationswhichcanbeperformedonbinarysearchtree are.
1. Insertionofanodeinbinarysearchtree.
2. Deletionofanodefrombinarysearchtree.
3. Searchingforaparticularnodeinbinarysearchtree.
Insertionofanodeinbinarysearchtree.
While insertinganynode inbinarysearchtree, lookfor itsappropriateposition inthe binarysearch tree.
Westart comparing this new nodewitheach [Link] is to be
inserted is greater than the value of the current node we move on to the right sub-branch otherwise
we move on to the left sub-branch. As soon as the appropriate position is found weattach this new
node as left or right childappropriately.

BeforeInsertion

In theabovefig,ifwewantoinsert23.Thenwewillstartcomparing23withvalueofrootnode
i.e. 10. As23 isgreater than 10, we will move on right sub-tree. Now we willcompare 23 with 20
andmoveright,compare23with22andmoveright.Nowcompare23with24butitislessthan
24. Wewillmoveon leftbranchof 24. Butasthere isnodeas leftchildof 24, wecanattach23as left
child of 24.

116
Deletionofanodefrombinarysearchtree.
Fordeletionofanynodefrombinarysearchtreetherearethree whicharepossible.
i. Deletionofleaf node.
ii. Deletionofa node havingonechild.
iii. Deletionofanode havingtwochildren.

Deletionofleafnode.

Thisisthesimplestdeletion,inwhichwesettheleft orrightpointerofparent nodeasNULL.

10

7 15

Beforedeletion

5 9 12 18

Fromthe above fig,wewanttodelete the node havingvalue5thenwewillset leftpointer ofitsparent node as

NULL. That is left pointer of node having value 7 is set to NULL.

Deletionofanodehavingonechild.

117
Toexplainthiskindofdeletion,consideratreeasgivenbelow.

If we want to delete the node 15, then we

will simply copy node 18 at place of 16
and then set the node free

Deletionofanodehavingtwochildren.
Considera treeasgivenbelow.

118
[Link] outtheinordersuccessor of node 7.
We will then find out the inorder successor of node 7. The inorder successor will be simply copied at
location of node 7.
Thatmeanscopy8atthepositionwhere value ofnode [Link] leftpointer [Link] completes the
deletion procedure.

Searchingforanodeinbinarysearchtree.
Insearching, the nodewhichwewanttosearch is called a key node. The key nodewillbe compared with
each node starting from root node if value of key node is greater than current node then we searchfor
it onrightsubbranchotherwise onleftsubbranch. Ifwereachtoleafnodeandstillwedo not get the value of
key node then we declare “node is not present in the tree”.

119
Inthe abovetree, ifwewanttosearchfor value9.Thenwewillcompare9withroot node10.As9 is less than
10 we will search on left sub branch. Now compare 9 with 5, but 9 is greater than 5. So we will move
onright sub tree. Now compare 9 with8 but 9 is greater than8 we will move onright sub branch. As
the node we willget holds the value 9. Thus the desired node can be searched.

AVLTREES
Adelsion Velski and Lendis in 1962 introduced binary tree structure thatis balanced with
[Link]
ofanynodecanbedoneinΟ(log n)times,wherenistotalnumber [Link] name of
these scientists the tree is called AVL tree.

Definition:

Anemptytree is heightbalanced ifT is a nonemptybinarytreewithTLandTR as its left

and right sub trees. The T is height balanced if and only if
i. TLandTR areheightbalanced.
ii. hL-hR <=1wherehLandhRare heightsofTLandTR.
Theidea ofbalancing atreeisobtainedbycalculatingthebalancefactorofatree.

DefinitionofBalanceFactor:

Thebalance factorBF(T) ofa node inbinarytree is definedtobe hL-hRwhere hLand hR are

heights of left and right sub trees of T.

ForanynodeinAVLtreethebalance [Link](T)is-1,0or+1.

120
HeightofAVLTree:
Theorem:The height ofAVLtreewithnelements(nodes)isO(logn).

Proof: Let anAVLtree withnnodes in it. Nhbethe minimumnumber ofnodes inanAVL treeof height
h.

Inworstcase, onesubtreemayhave height h-1 and othersubtreemayhave height [Link] sub

trees are AVL trees. Since for every node in AVL treethe height of left and right sub trees differby at
most 1.

Hence

Nh=Nh-1+Nh-2+1

WhereNhdenotestheminimumnumberofnodes inanAVLtreeofheight h. N0=0

N1=2

121
Wecanalsowrite itas
N>Nh=Nh-1+Nh-2+1

>2Nh-2

>4Nh-4
.
.
>2iNh-2i

Ifvalueofhiseven, let i=h/2-1 Then

equation becomes

N> 2h/2-1N2

=N > 2(h-1)/2x4(N2 =4)

=O(logN)

Ifvalueofhisodd, letI=(h-1)/2thenequationbecomes N >

2(h-1)/2 N1
N >2(h-1)/2x1
H=O(log N)

Thisprovesthat heightofAVLtree isalwaysO(logN).Hencesearch, insertionanddeletioncan be

carried out in logarithmic time.

RepresentationofAVLTree

The AVL tree follows the property of binary search tree. In fact AVL trees are
basically binary search trees with balance factors as -1, 0, or+1.
Afterinsertion of any nodein an AVL treeif the balancefactorof anynode becomes other
than -1, 0, or +1 then it is said that AVL property is violated. Then we have to
restore the destroyed balance condition. Thebalance factor isdenoted at right top
corner inside the node.

122
 After insertion of a new node if balance condition gets destroyed, then the nodes on thatpath(new
node insertion point to root) needs to be readjusted. That means onlythe affected sub tree is to
be rebalanced.
TherebalancingshouldbesuchthatentiretreeshouldsatisfyAVLproperty.
Inabovegivenexample-

123
Insertionofanode.

Therearefourdifferentcaseswhenrebalancingisrequiredafterinsertionofnewnode.

1. Aninsertionofnew nodeintoleftsubtreeofleftchild.(LL).
2. Aninsertionofnew nodeintorightsubtreeofleftchild.(LR).
3. Aninsertionofnewnodeintoleftsubtreeofrightchild.(RL).
4. Aninsertionofnewnodeintorightsubtreeofrightchild.(RR).

SomemodificationsdoneonAVLtreein orderto rebalanceitiscalledrotationsofAVLtree

Therearetwotypesof rotations:

Singlerotation Doublerotation
Left-Left(LLrotation) Left-Right(LRrotation)

Right-Right(RRrotation) Right-Left(RLrotation)

InsertionAlgorithm:
1. Insertanewnodeasnewleafjustasanordinarybinarysearchtree.
2. Nowtracethepathfrominsertionpoint(new nodeinsertedasleaf) [Link] ‘n’
encountered, check ifheights of left (n) and right (n) differ byat most1.
a) Ifyes,movetowardsparent(n).
b) Otherwiserestructurebydoing eitherasinglerotationor adouble rotation.
Thusonceweperformarotationat node‘n’wedonot requiretoperformanyrotationat any ancestor on
‘n’.

124
Whennode‘1’getsinsertedasaleft childofnode‘C’thenAVLpropertygetsdestroyed i.e. node A has
balance factor +2.
The LLrotationhastobe appliedtorebalancethenodes.

[Link]:

Whennode‘4’getsattachedasright child ofnode‘C’thennode‘A’[Link] which

needs to be applied is RR rotation as shown in fig.

125
Whennode‘3’ is attachedasarightchild ofnode‘C’thenunbalancingoccursbecauseofLR. Hence LR
rotation needs to be applied.

Whennode‘2’ is attachedasaleftchildofnode‘C’thennode‘A’getsunbalanced as itsbalance factor

becomes -2. Then RL rotation needs to be applied to rebalance the AVL tree.
Example:

Insert1,25,28,12inthe followingAVLtree.

126
Insert 1

Toinsert node‘1’wehavetoattachit asaleft childof‘2’. Thiswillunbalancethetreeasfollows. We will

apply LL rotation to preserve AVL property of it.

Insert25

Wewillattach25asaright childof18. Nobalancing isrequiredasentiretreepreservestheAVL property

127
Insert28
Thenode‘28’isattachedasaright [Link].

128
Insert12

TorebalancethetreewehavetoapplyLRrotation.

129
Deletion:

Evenafterdeletionofanyparticular node from AVL tree,the tree hastoberestructured inorder to preserve

AVL property. And thereby various rotations need to be applied.

Algorithmfordeletion:

Thedeletionalgorithmismorecomplex thaninsertionalgorithm.
1. Searchthe nodewhichistobedeleted.
2. a)IfthenodetobedeletedisaleafnodethensimplymakeitNULLtoremove.
b) If the node to be deleted is not a leaf node i.e. node may have one or two children, then the
node must be swapped with its inorder successor. Once the node is swapped, we can remove
this node.
3. Now we have to traverse back up the path towards root, checking the
[Link] in
some sub tree
then balance that sub tree using appropriate single or double
[Link](logn)timetodeleteanynode.

130
Thetreebecomes

131
Searching:

Thesearching ofa node inanAVLtree is [Link] isbasicallybinarysearchtree, the

algorithm used for searching a node from binary search tree is the same one is used to search a node
from AVL tree.

Thesearchingofa node fromAVLtreetakesO(logn)time.

BTREES
 Multi-way trees are tree data structures with more than two branches at a node. The data
structures of m-way search trees, B trees and Tries belong to this category of treestructures.
 AVL search trees are height balanced versions of binary search trees, provide efficient
retrievals and storageoperations. The complexity of insert, delete and searchoperations on
AVL search trees id O(log n).
 Applications such as File indexing where the entries in an index may be very large,
maintainingthe indexas m-waysearchtreesprovidesabetteroptionthanAVL searchtrees which
are but only balanced binary search trees.
 While binarysearchtreesare two-waysearchtrees, m-waysearchtreesare extended binary
search trees and hence provide efficient retrievals.
 B trees are height balanced versions of m-way search trees and they do not recommend
representation of keys with varying sizes.
 Triesaretreebaseddatastructuresthatsupportkeyswithvaryingsizes.

132
 UNIT-5

Definition:

ABtree oforderm is anm-waysearchtreeand hencemaybeempty. Ifnonempty, thenthe following properties are

satisfied on its extended tree representation:
i. Theroot nodemusthaveatleasttwochildnodesandatmostmchildnodes.
ii. Allinternalnodesotherthantheroot nodemust have at least |m/2 |nonemptychild nodesandatmost m non
empty child nodes.
iii. Thenumberofkeys ineachinternalnode isonelessthanitsnumberofchildnodesandthesekeys partition
the keys of the tree into sub trees.
iv. Allexternalnodesareatthesamelevel. v.

Example:
F K O Btreeoforder4

Level1

G M N
C D P Q W

S T X Y Z
Insertion Level 3
ForexampleconstructaB-treeoforder5usingfollowing numbers.3,14,7,1,8,5,11,17,13,6,23,12,
20,26, 4, 16,18, 24, 25, 19
Theorder5meansatthe most [Link] internalnodeshould haveat least 3nonempty children
and each leaf node must contain at least 2 keys.

Step1:Insert3,14,7,1

1 3 7 14

133
 UNIT-5

Step2:Insert8,Sincethenode isfullsplitthe nodeatmedium1,3,7,8,14

Step3:Insert5, 11,171whichcanbeeasilyinsertedinaB-tree.
3 8 14

1 3 5 8 11 14 17
Step4:Nowinsert [Link] ifwe insert 13thentheleafnodewillhave5keyswhichisnot allowed. Hence 8,
11,13, 14, 17issplitandmediumnode13is movedup.

7 13

1 3 5 8 11 14
17

134
 UNIT-5

Step5:Nowinsert6,23,12,20withoutany split.

7 13

1 3 5 6 8 11 12 14 17 20 23
Step6:The26 is inserted totherightmost leafnode. Hence14,17,20,23,26the node issplitand20willbe moved up.

7 13 20

1 3 5 6 8 11 12 14 17 23 26

135
 UNIT-5
Step7:Insertionofnode4causesleftmostnodetosplit.The1,3,4,5,6causeskey4tomoveup.
Theninsert16,18,24, 25.

4 7 13 20

Step8:Finallyinsert19.Then4,7,13,19,[Link] median13willbemovedup to from a root

1
node. 3 5 6 8 11 12 14 16 17 18 23 24 25 26
Thetreethenwillbe-
13

4 7 17 20
ThustheB treeis constructed. 13
Deletion
ConsideraB-tree

8 11 12 14 16 17 20
1 3 54 6 7 18 19 23 24 25 26

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

136
 UNIT-5

Delete8,thenit isverysimple.
13

4 7 17 20

Nowwewilldelete20,the20 is not ina leafnodesowewillfind its successorwhichis23,Hence23 will be

moved up to replace 20.

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

4 7 17 23

Next1 we will
3 delete 18.
5 Deletion
6 of 1811 12 corresponding
from the 1 4 node16causes18 24 one25
19 with only
the node 26
key,whichis notdesired(asperrule4) inB-tree [Link] nodetoimmediateright has an extra
key. In such a case we can borrow a key from parent and move spare key of sibling up.

137
 UNIT-5

13

4 7 17 24

Now1delete3 5. But deletionof5isnot

5 6 11
[Link] 12 thingis5 isfromleaf
first 14 16node. 19 23
Secondlythis 25node 26
leaf has
no extra keysnor siblings to immediate left or right. In such a situation we can combine this
13
[Link] meansremove 5andcombine6withthenode1, [Link] balanced
we have to moveparent’skeydown. Hence we will move 4 downas4 isbetween1, 3,and 6. The tree will
be-
7

17 24

1 3 4 6 11 12 14 16 19 23 25 26
Butagain internalnode of7 contains only one keywhich notallowed in B-tree. Wethenwilltrytoborrow
akeyfromsibling.Butsibling17,24has nospare [Link] that,combine7with13and17,
[Link]-treewillbe

138
 UNIT-5

7 13 1724

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

Searching

The search operation on B-tree is similar to a search to a search on binary search tree. Instead of choosing
between a left and right child as in binary tree, B-tree makes an m-way choice. Consider a B-tree as given
below.

13

4 7
17
20

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

Ifwewanttosearch11then

i. 11<13;Hencesearchleft node

ii. 11>7;Hencerightmostnode

iii. 11>8;moveinsecondblock

iv. node11 isfound

139
 UNIT-5

Therunningtime ofsearchoperationdependsuponthe height ofthe [Link] isO(logn).

HeightofB-tree

The maximum height ofB-treegivesanupperbound onnumber [Link] number of keys in a

B-tree of order 2m and depth h is
1+2m+2m(m+1)+2m(m+1)2 h-1
+...+2m(m+1)
h
=1+ i-1
∑2m(m+1)
i=1
The maximum heightofB-treewithnkeys

logm+1n =O(logn)
2m

140
 B+Trees

 MostimplementationsusetheB-treevariation,theB+-tree.
 In the B-tree, every value of the search field appears once at some
level in the tree,alongwiththedatapointertothe record,orblockwhere the
record isstored.
 In a B+ tree, data pointers are stored only at the leaf nodes, therefore
the structureof theleafnodesvaryfromthestructureof
theinternal(nonleaf)nodes.
 If the searchfield isa keyfield,the leaf nodeshave
avalueforeveryvalueof the search field, along with the data pointer to
the record or block.
 If the search field is a non key field, the pointer points to a block
containing pointerstothedatafilerecords,creatinganextralevelof
indirection(similarto option 3 for the secondary indexes)
 The leaf nodes of the B+ Trees are linked to provide ordered access
on the searchfield to [Link] levelissimilarto
thebaselevelof an index.
 Somesearchfieldvaluesintheleafnodesarerepeatedintheinternalnodes
of the B+ trees, in order to guide the search.

B+TreeExample
5

3 7 8

13 5 67 8 912

B+TreeInternalNodeStructure
1. Each internalnode isof theform<P1,K1,P2, K2,…., Pq-1, Kq-
1,Pq>,whereq<=p and each Piis a tree pointer.
2. Withineach internalnode,K1<K2<….<Kq-1.
3. ForallsearchfieldvaluesXinthesubtreepointedatbyPi,wehave:
 Ki-1<X<=Kifor1<i<q;
 X<=Kfori=1;
 andKi-1<Xfori =q.
4. Eachinternalnodehasatmost,ptreepointers.
5. Eachinternalnode,excepttheroot,hasatleast
p/2[Link] node has at least two tree pointers if it is
an internal node.
6. Aninternalnodewithqpointers,q<=p, hasq-1 searchfieldvalues.

141
B+TreeLeafNode Structure
1. Each leaf nodeisof theform, <<K1,Pr1>, <K2,Pr2>,…,<Kq-1,Prq-
1>,Pnext>where q<=p, each Priis a data pointer, and P next points to the
next leaf node of the B+ tree.
2. Withineach leaf node, K1<K2<…<Kq-1,q<=p
3. EachPriisadatapointerthatpointstotherecordwhosesearchfieldvalueisKi,
ortoafileblock containingthe record(or ablockof pointers if the
searchfield is not a key field)
4. Eachleafnodehasatleastp/2values.
5. Allleafnodesareatthesamelevel.

B+TreeInformation
 By starting at the leftmost block, it is possible to traverse leaf nodes
as a linked list using
[Link] recordson the
indexing field.
 Entries in internalnodes ofa B+ tree include search values and tree
pointers,
withoutanydatapointers,moreentriescanbestoredintoaninternalnodeo
fa B+ tree, than for a B-tree.
 Thereforetheorderp willbe largerfora B+ tree,which leads
tofewerB+ tree levels, improving the search time.
 Theorderp canbedifferentforthe internaland leaf nodes,becauseof
the structural differences of the nodes.

Example6fromText
To calculate theorderp of aB+Tree. suppose thesearch keyfield isV=9bytes
long, the block size is B = 512 bytes, a record pointer is Pr = 7 bytes and
a block pointer is P = 6 [Link] internal node of the B+trees can have
up to p tree pointers and p – 1 search field values, which must fit into a
single block.

Calculatethevalueofpforaninternalnode:

5 6bytes
9bytes

p*P+(p-1)*V<=512
p*6 + (p-1)*9 <=
512 6p + 9p –9
<= 512
15p <=522
p= 34 which meansthateachinternalnode canholdupto34treepointers,and33
search key values.

Calculatethevalueofpforaleafnode:

1 3 6bytes
9bytes
7 bytes
(pleaf)*((Pr+V))+P<=512
16pleaf+ 6 <= 512
pleaf<=506/16

142
pleaf =31 whichmeanseach leaf node canhold uptop leaf=31 value/datapointer
combinations, assuming data pointers are record pointers.

Example7fromText

Suppose that we construct a B+ tree on the field of Example [Link]

calculate the approximate number of entries of the B+ tree we assume
that each node is 69 percent [Link] average, each internalnode will have
34 *0.69 or approximately 23
pointers,[Link],ontheaveragewillhold0.69*pleaf
= 0.69*31 or approximately 21 data record pointers.A B+ tree will have
the following average number of entries at each level.

Root: 1node 22entries 23pointers

Level1: 23nodes 506 entries 529 pointers
Level2: 529 nodes 11,638entries 12,167pointer
s
LeafLevel: 12,167nodes255,507recordpointers

WhenwecomparethisresultwiththepreviousB-
treeexample(Example5),wecan see thatthe B+ tree can hold up to
255,507 record pointers, whereas a corresponding B-tree can only hold
65,535 entries.

InsertionandDeletionwithB+-trees.

Thefollowingexamplehasp=3,and pleaf=2

Points to Note:
 Everykeyvaluemustexistattheleaflevel,becausealldatapointersareatth
e leaf level,
 Everyvalueappearinginaninternalnode,alsoappearsastherightmostvalu
ein the leaf level of the subtree pointed at by the treepointer to the
left of the value.
 When a leaf node is full, and a new entry is inserted there, the node
overflows and must be [Link] j = (pleaf+1)/2 entries (in the
example 2 entries) in the originalnode are keptthere,andthe
remainingentries aremovedto thenew leaf [Link]
jiscopied/replicatedand moved to theparentnode.
 When an internal node is full, and a new entry is to be inserted, the
node overflowsandmustbe splitinto [Link] entryatposition jis
movedtothe parent [Link] first j-1 entries are kept in the original
node, and the last j+1 entries are moved to the new node.

TopracticeB+Treeinsertion,completeExercise14.15inChapter14ofthecourse
text.

143