TEEGALA KRISHNA REDDY ENGINEERING COLLEGE

(UGC-Autonomous)
Approved by AICTE, Affiliated to JNTUH, Accredited by NAAC- ‘A’ Grade
Medbowli, Meerpet, Balapur, Hyderabad, Telangana- 500097
Mob: 9393959597. Email: info@tkrec.ac.in, deanacademics@tkrec.ac.in
ADVANCED DATA STRUCTURES LAB MANUAL
Write a C++ program to perform the following operations:
1.insert an element into a Binary search tree.
2.Delete an element from a Binary search tree.
3.Search for a key element in a Binary search tree

#include<iostream>

#include<conio.h>

#include<stdlib.h>

using namespace std;

void insert(int,int );

void delte(int);
EC
void display(int);

int search(int);

int search1(int,int);

int tree[40],t=1,s,x,i;
R
int main()
TK

int ch,y;

for(i=1; i<40; i++)

tree[i]=-1;

while(1)

cout
<<"1.INSERT\n2.DELETE\n3.DISPLAY\n4.SEARCH\n5.EXIT\nEnter your
Choice:";

cin >> ch;

switch(ch)

{
case 1:

cout <<"Enter the element to Insert";

cin >> ch;

insert(1,ch);

break;

case 2:

cout <<"Enter the element to Delete";

cin >>x;

y=search(1);

if(y!=-1) delte(y);
EC
else cout<<"No Such Element Found in Tree";

break;

case 3:
R
display(1);

cout<<"\n";
TK

for(int i=0; i<=32; i++)

cout <<i;

cout <<"\n";

break;

case 4:

cout <<"Enter the Element to Search:";

cin >> x;

y=search(1);

if(y == -1) cout <<"No such Element Found in Tree";

else cout <<x << "is in" << y <<"Position";

 break;

case 5:

exit(0);

} return 0;

void insert(int s,int ch )

int x;

if(t==1)EC
{

tree[t++]=ch;

return;
R
}

x=search1(s,ch);
TK

if(tree[x]>ch)

tree[2*x]=ch;

else

tree[2*x+1]=ch;

t++;

void delte(int x)

if( tree[2*x]==-1 && tree[2*x+1]==-1)

tree[x]=-1;
 else if(tree[2*x]==-1)

tree[x]=tree[2*x+1];

tree[2*x+1]=-1;

else if(tree[2*x+1]==-1)

tree[x]=tree[2*x];

tree[2*x]=-1;

} EC
else

tree[x]=tree[2*x];
R
delte(2*x);

}
TK

t--;

int search(int s)

if(t==1)

cout <<"No element in tree";

return -1;

if(tree[s]==-1)
 return tree[s];

if(tree[s]>x)

search(2*s);

else if(tree[s]<x)

search(2*s+1);

else

return s;

void display(int s)

{ EC
if(t==1)

cout <<"No element in tree:";

R
return;

}
TK

for(int i=1; i<40; i++)

if(tree[i]==-1)

cout <<" ";

else cout <<tree[i];

return ;

int search1(int s,int ch)

if(t==1)

{
 cout <<"No element in tree";

return -1;

if(tree[s]==-1)

return s/2;

if(tree[s] > ch)

search1(2*s,ch);

else search1(2*s+1,ch);

OUTPUT: EC
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your Choice:1
Enter the element to Insert33
R
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
TK

5.EXIT
Enter your Choice:3
33
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your Choice:4
Enter the Element to Search:33
33is in1Position
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your Choice:5
Write a C++ program to perform the following sorting methods:
1.Merge sort 2.Heap sort 3. Quick sort.
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
 int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
//size of left and right sub-arrays
nl = m-l+1; nr = r-m;
EC
int larr[nl], rarr[nr];
//fill left and right sub-arrays
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
R
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
TK

//marge temp arrays to real array

while(i < nl && j<nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j++;
}
k++;
}
while(i<nl) { //extra element in left array
array[k] = larr[i];
i++; k++;
}
 while(j<nr) { //extra element in right array
array[k] = rarr[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
// Sort first and second arrays
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}
}
int main() {
EC
int n;
cout << "Enter the number of elements: ";
cin >> n;
R
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
TK

for(int i = 0; i<n; i++) {

cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
mergeSort(arr, 0, n-1); //(n-1) for last index
cout << "Array after Sorting: ";
display(arr, n);
}

Output
Enter the number of elements: 6
Enter elements:
14 20 78 98 20 45
Array before Sorting: 14 20 78 98 20 45
Array after Sorting: 14 20 20 45 78 98

// C++ program for implementation of Heap Sort

#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

int largest = i; // Initialize largest as root Since we are using 0 based

EC
indexing

int l = 2 * i + 1; // left = 2*i + 1

int r = 2 * i + 2; // right = 2*i + 2

R
// If left child is larger than root

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

TK

largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])

largest = r;

// If largest is not root

if (largest != i) {

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

// Recursively heapify the affected sub-tree

 heapify(arr, n, largest);

// main function to do heap sort

void heapSort(int arr[], int n)

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);
EC
// One by one extract an element from heap

for (int i = n - 1; i >= 0; i--) {

// Move current root to end

R
swap(arr[0], arr[i]);
TK

// call max heapify on the reduced heap

heapify(arr, i, 0);

/* A utility function to print array of size n */

void printArray(int arr[], int n)

for (int i = 0; i < n; ++i)

cout << arr[i] << " ";

 cout << "\n";

// Driver program

int main()

int arr[] = { 60 ,20 ,40 ,70, 30, 10};

int n = sizeof(arr) / sizeof(arr[0]);

//heapify algorithm

// the loop must go reverse you will get after analyzing manually
EC
// (i=n/2 -1) because other nodes/ ele's are leaf nodes

// (i=n/2 -1) for 0 based indexing

// (i=n/2) for 1 based indexing

R
for(int i=n/2 -1;i>=0;i--){
TK

heapify(arr,n,i);

cout << "After heapifying array is \n";

printArray(arr, n);

heapSort(arr, n);

cout << "Sorted array is \n";

printArray(arr, n);

return 0;

}
 //code by Prajwal Chougale

Output
After heapifying array is
70 60 40 20 30 10
Sorted array is
10 20 30 40 60 70
Time complexity : O(N*logN)
Auxiliary space: O(1)

// C++ Implementation of the Quick Sort Algorithm.

#include <iostream>
EC
using namespace std;

int partition(int arr[], int start, int end)

{
R
int pivot = arr[start];

int count = 0;
TK

for (int i = start + 1; i <= end; i++) {

if (arr[i] <= pivot)

count++;

// Giving pivot element its correct position

int pivotIndex = start + count;

swap(arr[pivotIndex], arr[start]);

// Sorting left and right parts of the pivot element

 int i = start, j = end;

while (i < pivotIndex && j > pivotIndex) {

while (arr[i] <= pivot) {

i++;

while (arr[j] > pivot) {

j--;

if (i < pivotIndex && j > pivotIndex) {

EC
swap(arr[i++], arr[j--]);

}
R
return pivotIndex;
TK

void quickSort(int arr[], int start, int end)

// base case

if (start >= end)

return;

// partitioning the array

int p = partition(arr, start, end);

// Sorting the left part

 quickSort(arr, start, p - 1);

// Sorting the right part

quickSort(arr, p + 1, end);

int main()

int arr[] = { 9, 3, 4, 2, 1, 8 };

int n = 6;

quickSort(arr, 0, n - 1);
EC
for (int i = 0; i < n; i++) {

cout << arr[i] << " ";

}
R
return 0;
TK

Output
1 2 3 4 8 9

3. write a c++ program to perform the following operations a) insert an element

into a b tree.b) delete an element from a b tree c) search for a key element in a
b tree.

#include<iostream>

using namespace std;

// A BTree node

class BTreeNode

int *keys; // An array of keys

int t; // Minimum degree (defines the range for number of keys)

BTreeNode **C; // An array of child pointers

int n; // Current number of keys

bool leaf; // Is true when node is leaf. Otherwise false

public:
EC
BTreeNode(int _t, bool _leaf); // Constructor

// A utility function to insert a new key in the subtree rooted with

// this node. The assumption is, the node must be non-full when this
R
// function is called
TK

void insertNonFull(int k);

// A utility function to split the child y of this node. i is index of y in

// child array C[]. The Child y must be full when this function is called

void splitChild(int i, BTreeNode *y);

// A function to traverse all nodes in a subtree rooted with this node

void traverse();

// A function to search a key in the subtree rooted with this node.

BTreeNode *search(int k); // returns NULL if k is not present.

// Make BTree friend of this so that we can access private members of this
// class in BTree functions

friend class BTree;

};

// A BTree

class BTree

BTreeNode *root; // Pointer to root node

int t; // Minimum degree

public:
EC
// Constructor (Initializes tree as empty)

BTree(int _t)

{ root = NULL; t = _t; }

R
// function to traverse the tree
TK

void traverse()

{ if (root != NULL) root->traverse(); }

// function to search a key in this tree

BTreeNode* search(int k)

{ return (root == NULL)? NULL : root->search(k); }

// The main function that inserts a new key in this B-Tree

void insert(int k);

};
// Constructor for BTreeNode class

BTreeNode::BTreeNode(int t1, bool leaf1)

// Copy the given minimum degree and leaf property

t = t1;

leaf = leaf1;

// Allocate memory for maximum number of possible keys

// and child pointers

keys = new int[2*t-1];

EC
C = new BTreeNode *[2*t];

// Initialize the number of keys as 0

n = 0;
R
}
TK

// Function to traverse all nodes in a subtree rooted with this node

void BTreeNode::traverse()

// There are n keys and n+1 children, traverse through n keys

// and first n children

int i;

for (i = 0; i < n; i++)

// If this is not leaf, then before printing key[i],

 // traverse the subtree rooted with child C[i].

if (leaf == false)

C[i]->traverse();

cout << " " << keys[i];

// Print the subtree rooted with last child

if (leaf == false)

C[i]->traverse();

}
EC
// Function to search key k in subtree rooted with this node

BTreeNode *BTreeNode::search(int k)

{
R
// Find the first key greater than or equal to k
TK

int i = 0;

while (i < n && k > keys[i])

i++;

// If the found key is equal to k, return this node

if (keys[i] == k)

return this;

// If key is not found here and this is a leaf node

if (leaf == true)
 return NULL;

// Go to the appropriate child

return C[i]->search(k);

// The main function that inserts a new key in this B-Tree

void BTree::insert(int k)

// If tree is empty

if (root == NULL)

{
EC
// Allocate memory for root

root = new BTreeNode(t, true);

R
root->keys[0] = k; // Insert key
TK

root->n = 1; // Update number of keys in root

else // If tree is not empty

// If root is full, then tree grows in height

if (root->n == 2*t-1)

// Allocate memory for new root

BTreeNode *s = new BTreeNode(t, false);

 // Make old root as child of new root

s->C[0] = root;

// Split the old root and move 1 key to the new root

s->splitChild(0, root);

// New root has two children now. Decide which of the

// two children is going to have new key

int i = 0;

if (s->keys[0] < k)

i++;
EC
s->C[i]->insertNonFull(k);

// Change root

root = s;
R
}
TK

else // If root is not full, call insertNonFull for root

root->insertNonFull(k);

// A utility function to insert a new key in this node

// The assumption is, the node must be non-full when this

// function is called

void BTreeNode::insertNonFull(int k)
{

// Initialize index as index of rightmost element

int i = n-1;

// If this is a leaf node

if (leaf == true)

// The following loop does two things

// a) Finds the location of new key to be inserted

// b) Moves all greater keys to one place ahead

EC
while (i >= 0 && keys[i] > k)

keys[i+1] = keys[i];
R
i--;
TK

// Insert the new key at found location

keys[i+1] = k;

n = n+1;

else // If this node is not leaf

// Find the child which is going to have the new key

while (i >= 0 && keys[i] > k)

 i--;

// See if the found child is full

if (C[i+1]->n == 2*t-1)

// If the child is full, then split it

splitChild(i+1, C[i+1]);

// After split, the middle key of C[i] goes up and

// C[i] is splitted into two. See which of the two

// is going to have the new key

ECif (keys[i+1] < k)

i++;

}
R
C[i+1]->insertNonFull(k);
TK

// A utility function to split the child y of this node

// Note that y must be full when this function is called

void BTreeNode::splitChild(int i, BTreeNode *y)

// Create a new node which is going to store (t-1) keys

// of y

BTreeNode *z = new BTreeNode(y->t, y->leaf);

z->n = t - 1;

// Copy the last (t-1) keys of y to z

for (int j = 0; j < t-1; j++)

z->keys[j] = y->keys[j+t];

// Copy the last t children of y to z

if (y->leaf == false)

for (int j = 0; j < t; j++)

z->C[j] = y->C[j+t];

}
EC
// Reduce the number of keys in y

y->n = t - 1;
R
// Since this node is going to have a new child,
TK

// create space of new child

for (int j = n; j >= i+1; j--)

C[j+1] = C[j];

// Link the new child to this node

C[i+1] = z;

// A key of y will move to this node. Find the location of

// new key and move all greater keys one space ahead

for (int j = n-1; j >= i; j--)

keys[j+1] = keys[j];
 // Copy the middle key of y to this node

keys[i] = y->keys[t-1];

// Increment count of keys in this node

n = n + 1;

// Driver program to test above functions

int main()

BTree t(3); // A B-Tree with minimum degree 3

EC
t.insert(10);

t.insert(20);

t.insert(5);
R
t.insert(6);
TK

t.insert(12);

t.insert(30);

t.insert(7);

t.insert(17);

cout << "Traversal of the constructed tree is ";

t.traverse();

int k = 6;

(t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";

k = 15;
 (t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";

return 0;

Output:
Traversal of the constructed tree is 5 6 7 10 12 17 20 30
Present
Not Present
// Deleting a key from a B-tree in C++

#include <iostream>
using namespace std;

int *keys;
int t;
EC
class BTreeNode {

BTreeNode **C;
int n;
bool leaf;
R
public:
BTreeNode(int _t, bool _leaf);
TK

void traverse();

int findKey(int k);

void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void deletion(int k);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);
int getPredecessor(int idx);
int getSuccessor(int idx);
void fill(int idx);
void borrowFromPrev(int idx);
void borrowFromNext(int idx);
void merge(int idx);
friend class BTree;
};

class BTree {
 BTreeNode *root;
int t;

public:
BTree(int _t) {
root = NULL;
t = _t;
}

void traverse() {
if (root != NULL)
root->traverse();
}

void insertion(int k);

void deletion(int k);

}; EC
// B tree node
BTreeNode::BTreeNode(int t1, bool leaf1) {
t = t1;
leaf = leaf1;
R
keys = new int[2 * t - 1];
C = new BTreeNode *[2 * t];
TK

n = 0;
}

// Find the key

int BTreeNode::findKey(int k) {
int idx = 0;
while (idx < n && keys[idx] < k)
++idx;
return idx;
}

// Deletion operation
void BTreeNode::deletion(int k) {
int idx = findKey(k);

if (idx < n && keys[idx] == k) {

if (leaf)
removeFromLeaf(idx);
else
 removeFromNonLeaf(idx);
} else {
if (leaf) {
cout << "The key " << k << " is does not exist in the tree\n";
return;
}

bool flag = ((idx == n) ? true : false);

if (C[idx]->n < t)
fill(idx);

if (flag && idx > n)

C[idx - 1]->deletion(k);
else
C[idx]->deletion(k);
}
return; EC
}

// Remove from the leaf

void BTreeNode::removeFromLeaf(int idx) {
for (int i = idx + 1; i < n; ++i)
keys[i - 1] = keys[i];
R
n--;
TK

return;
}

// Delete from non leaf node

void BTreeNode::removeFromNonLeaf(int idx) {
int k = keys[idx];

if (C[idx]->n >= t) {
int pred = getPredecessor(idx);
keys[idx] = pred;
C[idx]->deletion(pred);
}

else if (C[idx + 1]->n >= t) {

int succ = getSuccessor(idx);
keys[idx] = succ;
C[idx + 1]->deletion(succ);
}
 else {
merge(idx);
C[idx]->deletion(k);
}
return;
}

int BTreeNode::getPredecessor(int idx) {

BTreeNode *cur = C[idx];
while (!cur->leaf)
cur = cur->C[cur->n];

return cur->keys[cur->n - 1];

}

int BTreeNode::getSuccessor(int idx) {

BTreeNode *cur = C[idx + 1];
while (!cur->leaf)
EC
cur = cur->C[0];

return cur->keys[0];
}

void BTreeNode::fill(int idx) {

R
if (idx != 0 && C[idx - 1]->n >= t)
borrowFromPrev(idx);
TK

else if (idx != n && C[idx + 1]->n >= t)

borrowFromNext(idx);

else {
if (idx != n)
merge(idx);
else
merge(idx - 1);
}
return;
}

// Borrow from previous

void BTreeNode::borrowFromPrev(int idx) {
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx - 1];

for (int i = child->n - 1; i >= 0; --i)

child->keys[i + 1] = child->keys[i];
 if (!child->leaf) {
for (int i = child->n; i >= 0; --i)
child->C[i + 1] = child->C[i];
}

child->keys[0] = keys[idx - 1];

if (!child->leaf)
child->C[0] = sibling->C[sibling->n];

keys[idx - 1] = sibling->keys[sibling->n - 1];

child->n += 1;
sibling->n -= 1;

return;
} EC
// Borrow from the next
void BTreeNode::borrowFromNext(int idx) {
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];
R
child->keys[(child->n)] = keys[idx];

if (!(child->leaf))
TK

child->C[(child->n) + 1] = sibling->C[0];

keys[idx] = sibling->keys[0];

for (int i = 1; i < sibling->n; ++i)

sibling->keys[i - 1] = sibling->keys[i];

if (!sibling->leaf) {
for (int i = 1; i <= sibling->n; ++i)
sibling->C[i - 1] = sibling->C[i];
}

child->n += 1;
sibling->n -= 1;

return;
}

// Merge
void BTreeNode::merge(int idx) {
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];

child->keys[t - 1] = keys[idx];

for (int i = 0; i < sibling->n; ++i)

child->keys[i + t] = sibling->keys[i];

if (!child->leaf) {
for (int i = 0; i <= sibling->n; ++i)
child->C[i + t] = sibling->C[i];
}

for (int i = idx + 1; i < n; ++i)

keys[i - 1] = keys[i];

for (int i = idx + 2; i <= n; ++i)

EC
C[i - 1] = C[i];

child->n += sibling->n + 1;
n--;

delete (sibling);
R
return;
}
TK

// Insertion operation
void BTree::insertion(int k) {
if (root == NULL) {
root = new BTreeNode(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
BTreeNode *s = new BTreeNode(t, false);

s->C[0] = root;

s->splitChild(0, root);

int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
 root = s;
} else
root->insertNonFull(k);
}
}

// Insertion non full

void BTreeNode::insertNonFull(int k) {
int i = n - 1;

if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}

keys[i + 1] = k;
n = n + 1;
EC
} else {
while (i >= 0 && keys[i] > k)
i--;

if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
R
if (keys[i + 1] < k)
i++;
TK

}
C[i + 1]->insertNonFull(k);
}
}

// Split child
void BTreeNode::splitChild(int i, BTreeNode *y) {
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;

for (int j = 0; j < t - 1; j++)

z->keys[j] = y->keys[j + t];

if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}

y->n = t - 1;
 for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];

C[i + 1] = z;

for (int j = n - 1; j >= i; j--)

keys[j + 1] = keys[j];

keys[i] = y->keys[t - 1];

n = n + 1;
}

// Traverse
void BTreeNode::traverse() {
int i;
for (i = 0; i < n; i++) {
EC
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}

if (leaf == false)
R
C[i]->traverse();
}
TK

// Delete Operation
void BTree::deletion(int k) {
if (!root) {
cout << "The tree is empty\n";
return;
}

root->deletion(k);

if (root->n == 0) {
BTreeNode *tmp = root;
if (root->leaf)
root = NULL;
else
root = root->C[0];

delete tmp;
}
return;
}

int main() {
BTree t(3);
t.insertion(8);
t.insertion(9);
t.insertion(10);
t.insertion(11);
t.insertion(15);
t.insertion(16);
t.insertion(17);
t.insertion(18);
t.insertion(20);
t.insertion(23);

cout << "The B-tree is: ";

t.traverse();
EC
t.deletion(20);

cout << "\nThe B-tree is: ";

t.traverse();
}
R
MIN-MAX Heap
TK

#include<iostream.h>

#include<stdio.h>

#include<string.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 4

#define MIN 2

typedef char Type[10];

typedef struct Btree

Type key;

}BT;

typedef struct treenode

int count;

EC
BT entry[MAX+1];

treenode *branch[MAX+1];

}node;
R
class B
TK

node *root;

public:

int LT(char *,char *);

int EQ(char *,char *);

node *Search(Type target,node *root,int *targetpos);

int SearchNode(Type target,node *current,int *pos);

node *Insert(BT New,node *root);

int MoveDown(BT New,node *current,BT *med,node **medright);

void InsertIn(BT med,node *medright,node *current,int pos);

void Split(BT med,node *medright,node *current,int pos,BT *newmedian,node

**newright);

void Delete(Type target,node **root);

void Del_node(Type target,node *current);

void Remove(node *current,int pos);

void Successor(node *current,int pos);

EC
void Adjust(node *current,int pos);

void MoveRight(node *current,int pos);

R
void MoveLeft(node *current,int pos);

void Combine(node *current,int pos);

TK

void InOrder(node *root);

};

int B::LT(char *a,char *b)

if((strcmp(a,b))<(0))

return 1;

else
return 0;

int B::EQ(char *a,char *b)

if((strcmp(a,b))==(0))

return 1;

else

return 0;
EC
}

node* B::Search(Type target,node *root,int *targetpos)

R
{
TK

if(root==NULL)

return NULL;

else if(SearchNode(target,root,targetpos))

return root;

else

return Search(target,root->branch[*targetpos],targetpos); }

int B::SearchNode(Type target,node *current,int *pos)

{
if(LT(target,current->entry[1].key))

{*

pos=0;

return 0;

else

EC
for(*pos=current->count;

LT(target,current->entry[*pos].key) && *pos>1;(*pos)--); return EQ(target,current-

>entry[*pos].key);
R
}

}
TK

node *B::Insert(BT newentry,node *root)

BT medentry;

node *medright;

node *New;

if(MoveDown(newentry,root, &medentry, &medright))

{
New=new node;

New->count=1;

New->entry[1]=medentry;

New->branch[0]=root;

New->branch[1]=medright;

return New;

return root;
EC
}

int B::MoveDown(BT New,node *current,BT *med,node **medright) {

R
int pos;
TK

if(current==NULL)

med=New;

medright=NULL;

return 1;

else

{
if(SearchNode(New.key,current,&pos))

cout<<"Duplicate key\n";

if(MoveDown(New,current->branch[pos],med,medright))

if(current->count<MAX)

InsertIn(*med,*medright,current,pos);

return 0;

}
EC
else

{
R
Split(*med,*medright,current,pos,med,medright);
TK

return 1;

return 0;

void B::InsertIn(BT med,node *medright,node *current,int pos)

int i;
for(i=current->count;i>pos;i--)

current->entry[i+1]=current->entry[i];

current->branch[i+1]=current->branch[i];

current->entry[pos+1]=med;

current->branch[pos+1]=medright;

EC
current->count++;

void B::Split(BT med,node *medright,node *current,int pos,BT *newmedian,node

R
**newright)

{
TK

int i;

int median;

if(pos<=MIN)

median=MIN;

Write a C++ program to perform the following operations:

1.insert an element into a Leftlist tree.
2.Delete an element from a Leftlist tree.
3.Search for a key element in a Leftlist tree.
//C++ program for leftist heap / leftist tree
#include <bits/stdc++.h>
using namespace std;
// Node Class Declaration
class LeftistNode
{
public:
int element;
LeftistNode *left;
LeftistNode *right;
int dist;
LeftistNode(int & element, LeftistNode *lt = NULL,
LeftistNode *rt = NULL, int np = 0)
{
this->element = element;
right = rt;
left = lt,
dist = np;
}
};

//Class Declaration
class LeftistHeap
{
public: EC
LeftistHeap();
LeftistHeap(LeftistHeap &rhs);
~LeftistHeap();
bool isEmpty();
bool isFull();
int &findMin();
void Insert(int &x);
void deleteMin();
R
void deleteMin(int &minItem);
void makeEmpty();
void Merge(LeftistHeap &rhs);
LeftistHeap & operator =(LeftistHeap &rhs);
TK

private:
LeftistNode *root;
LeftistNode *Merge(LeftistNode *h1,
LeftistNode *h2);
LeftistNode *Merge1(LeftistNode *h1,
LeftistNode *h2);
void swapChildren(LeftistNode * t);
void reclaimMemory(LeftistNode * t);
LeftistNode *clone(LeftistNode *t);
};

// Construct the leftist heap

LeftistHeap::LeftistHeap()
{
root = NULL;
}

// Copy constructor.
LeftistHeap::LeftistHeap(LeftistHeap &rhs)
{
root = NULL;
*this = rhs;
}

// Destruct the leftist heap

LeftistHeap::~LeftistHeap()
{
makeEmpty( );
}

/* Merge rhs into the priority queue.

rhs becomes empty. rhs must be different
from this.*/
void LeftistHeap::Merge(LeftistHeap &rhs)
{
if (this == &rhs)
return;
root = Merge(root, rhs.root);
rhs.root = NULL;
}

/* Internal method to merge two roots.

Deals with deviant cases and calls recursive Merge1.*/
LeftistNode *LeftistHeap::Merge(LeftistNode * h1,
LeftistNode * h2)
{
if (h1 == NULL)
return h2;
EC
if (h2 == NULL)
return h1;
if (h1->element < h2->element)
return Merge1(h1, h2);
else
return Merge1(h2, h1);
}
R
/* Internal method to merge two roots.
Assumes trees are not empty, and h1's root contains
smallest item.*/
LeftistNode *LeftistHeap::Merge1(LeftistNode * h1,
TK

LeftistNode * h2)
{
if (h1->left == NULL)
h1->left = h2;
else
{
h1->right = Merge(h1->right, h2);
if (h1->left->dist < h1->right->dist)
swapChildren(h1);
h1->dist = h1->right->dist + 1;
}
return h1;
}

// Swaps t's two children.

void LeftistHeap::swapChildren(LeftistNode * t)
{
LeftistNode *tmp = t->left;
t->left = t->right;
t->right = tmp;
}

/* Insert item x into the priority queue, maintaining

heap order.*/
void LeftistHeap::Insert(int &x)
{
root = Merge(new LeftistNode(x), root);
}

/* Find the smallest item in the priority queue.

Return the smallest item, or throw Underflow if empty.*/
int &LeftistHeap::findMin()
{
return root->element;
}

/* Remove the smallest item from the priority queue.

Throws Underflow if empty.*/
void LeftistHeap::deleteMin()
{
LeftistNode *oldRoot = root;
root = Merge(root->left, root->right);
delete oldRoot;
}

/* Remove the smallest item from the priority queue.

Pass back the smallest item, or throw Underflow if empty.*/
void LeftistHeap::deleteMin(int &minItem)
EC
{
if (isEmpty())
{
cout<<"Heap is Empty"<<endl;
return;
}
minItem = findMin();
deleteMin();
R
}

/* Test if the priority queue is logically empty.

Returns true if empty, false otherwise*/
TK

bool LeftistHeap::isEmpty()
{
return root == NULL;
}

/* Test if the priority queue is logically full.

Returns false in this implementation.*/
bool LeftistHeap::isFull()
{
return false;
}

// Make the priority queue logically empty

void LeftistHeap::makeEmpty()
{
reclaimMemory(root);
root = NULL;
}

// Deep copy
LeftistHeap &LeftistHeap::operator =(LeftistHeap & rhs)
{
if (this != &rhs)
{
 makeEmpty();
root = clone(rhs.root);
}
return *this;
}

// Internal method to make the tree empty.

void LeftistHeap::reclaimMemory(LeftistNode * t)
{
if (t != NULL)
{
reclaimMemory(t->left);
reclaimMemory(t->right);
delete t;
}
}

// Internal method to clone subtree.

LeftistNode *LeftistHeap::clone(LeftistNode * t)
{
if (t == NULL)
return NULL;
else EC
return new LeftistNode(t->element, clone(t->left),
clone(t->right), t->dist);
}

//Driver program
int main()
{
LeftistHeap h;
R
LeftistHeap h1;
LeftistHeap h2;
int x;
int arr[]= {1, 5, 7, 10, 15};
TK

int arr1[]= {22, 75};

h.Insert(arr[0]);
h.Insert(arr[1]);
h.Insert(arr[2]);
h.Insert(arr[3]);
h.Insert(arr[4]);
h1.Insert(arr1[0]);
h1.Insert(arr1[1]);

h.deleteMin(x);
cout<< x <<endl;

h1.deleteMin(x);
cout<< x <<endl;

h.Merge(h1);
h2 = h;

h2.deleteMin(x);
cout<< x << endl;
return 0;
}
Output
1
22
5

Write a program to perform the following operations:

1.Insert an element into a binomial heap.

2.Delete an element into a binomial heap.

3.Search for a key element In a binomial heap.

1. /*
2. * C++ Program to Implement Binomial Heap
3. */
4. #include <iostream>
5. #include <cstdlib>
6. using namespace std;
7. /* EC
8. * Node Declaration
9. */
10. struct node
11. {
12. int n;
13. int degree;
14. node* parent;
15. node* child;
R
16. node* sibling;
17. };
18. /*
19. * Class Declaration
TK

20. */
21. class BinomialHeap
22. {
23. private:
24. node *H;
25. node *Hr;
26. int count;
27. public:
28. node* Initializeheap();
29. int Binomial_link(node*, node*);
30. node* Create_node(int);
31. node* Union(node*, node*);
32. node* Insert(node*, node*);
33. node* Merge(node*, node*);
34. node* Extract_Min(node*);
35. int Revert_list(node*);
36. int Display(node*);
37. node* Search(node*, int);
38. int Decrease_key(node*, int, int);
39. int Delete(node*, int);
40. BinomialHeap()
41. {
42. H = Initializeheap();
43. Hr = Initializeheap();
44. int count = 1;
45. }
46. };
47.
48. /*
49. * Initialize Heap
50. */
51. node* BinomialHeap::Initializeheap()
52. {
53. node* np;
54. np = NULL;
55. return np;
56. }
57. /*
58. * Linking nodes in Binomial Heap
59. */
60. int BinomialHeap::Binomial_link(node* y, node* z)
61. {
62. y->parent = z;
63. y->sibling = z->child;
64. z->child = y;
65. z->degree = z->degree + 1;
66. }
67. /*
68. EC * Create Nodes in Binomial Heap
69. */
70. node* BinomialHeap::Create_node(int k)
71. {
72. node* p = new node;
73. p->n = k;
74. return p;
75. }
76. /*
R
77. * Insert Nodes in Binomial Heap
78. */
79. node* BinomialHeap::Insert(node* H, node* x)
80. {
TK

81. node* H1 = Initializeheap();

82. x->parent = NULL;
83. x->child = NULL;
84. x->sibling = NULL;
85. x->degree = 0;
86. H1 = x;
87. H = Union(H, H1);
88. return H;
89. }
90.
91. /*
92. * Union Nodes in Binomial Heap
93. */
94. node* BinomialHeap::Union(node* H1, node* H2)
95. {
96. node *H = Initializeheap();
97. H = Merge(H1, H2);
98. if (H == NULL)
99. return H;
100. node* prev_x;
101. node* next_x;
102. node* x;
103. prev_x = NULL;
104. x = H;
105. next_x = x->sibling;
106. while (next_x != NULL)
107. {
108. if ((x->degree != next_x->degree) || ((next_x-
>sibling != NULL)
109. && (next_x->sibling)->degree == x->degree))
110. {
111. prev_x = x;
112. x = next_x;
113. }
114. else
115. {
116. if (x->n <= next_x->n)
117. {
118. x->sibling = next_x->sibling;
119. Binomial_link(next_x, x);
120. }
121. else
122. {
123. if (prev_x == NULL)
124. H = next_x;
125. else
126. prev_x->sibling = next_x;
127. Binomial_link(x, next_x);
128. EC x = next_x;
129. }
130. }
131. next_x = x->sibling;
132. }
133. return H;
134. }
135. /*
136. * Merge Nodes in Binomial Heap
R
137. */
138. node* BinomialHeap::Merge(node* H1, node* H2)
139. {
140. node* H = Initializeheap();
TK

141. node* y;
142. node* z;
143. node* a;
144. node* b;
145. y = H1;
146. z = H2;
147. if (y != NULL)
148. {
149. if (z != NULL)
150. {
151. if (y->degree <= z->degree)
152. H = y;
153. else if (y->degree > z->degree)
154. H = z;
155. }
156. else
157. H = y;
158. }
159. else
160. H = z;
161. while (y != NULL && z != NULL)
162. {
163. if (y->degree < z->degree)
164. {
165. y = y->sibling;
166. }
167. else if (y->degree == z->degree)
168. {
169. a = y->sibling;
170. y->sibling = z;
171. y = a;
172. }
173. else
174. {
175. b = z->sibling;
176. z->sibling = y;
177. z = b;
178. }
179. }
180. return H;
181. }
182. /*
183. * Display Binomial Heap
184. */
185. int BinomialHeap::Display(node* H)
186. {
187. if (H == NULL)
188. {
189. EC cout<<"The Heap is empty"<<endl;
190. return 0;
191. }
192. cout<<"The root nodes are: "<<endl;
193. node* p;
194. p = H;
195. while (p != NULL)
196. {
197. cout<<p->n;
R
198. if (p->sibling != NULL)
199. cout<<"-->";
200. p = p->sibling;
201. }
TK

202. cout<<endl;
203. }
204. /*
205. * Extract Minimum
206. */
207. node* BinomialHeap::Extract_Min(node* H1)
208. {
209. Hr = NULL;
210. node* t = NULL;
211. node* x = H1;
212. if (x == NULL)
213. {
214. cout<<"Nothing to Extract"<<endl;
215. return x;
216. }
217. int min = x->n;
218. node* p = x;
219. while (p->sibling != NULL)
220. {
221. if ((p->sibling)->n < min)
222. {
223. min = (p->sibling)->n;
224. t = p;
225. x = p->sibling;
226. }
227. p = p->sibling;
228. }
229. if (t == NULL && x->sibling == NULL)
230. H1 = NULL;
231. else if (t == NULL)
232. H1 = x->sibling;
233. else if (t->sibling == NULL)
234. t = NULL;
235. else
236. t->sibling = x->sibling;
237. if (x->child != NULL)
238. {
239. Revert_list(x->child);
240. (x->child)->sibling = NULL;
241. }
242. H = Union(H1, Hr);
243. return x;
244. }
245. /*
246. * Reverse List
247. */
248. int BinomialHeap::Revert_list(node* y)
249. {
250. EC if (y->sibling != NULL)
251. {
252. Revert_list(y->sibling);
253. (y->sibling)->sibling = y;
254. }
255. else
256. {
257. Hr = y;
258. }
R
259. }
260.
261. /*
262. * Search Nodes in Binomial Heap
TK

263. */
264. node* BinomialHeap::Search(node* H, int k)
265. {
266. node* x = H;
267. node* p = NULL;
268. if (x->n == k)
269. {
270. p = x;
271. return p;
272. }
273. if (x->child != NULL && p == NULL)
274. p = Search(x->child, k);
275. if (x->sibling != NULL && p == NULL)
276. p = Search(x->sibling, k);
277. return p;
278. }
279. /*
280. * Decrease key of a node
281. */
282. int BinomialHeap::Decrease_key(node* H, int i, int k)
283. {
284. int temp;
285. node* p;
286. node* y;
287. node* z;
288. p = Search(H, i);
289. if (p == NULL)
290. {
291. cout<<"Invalid choice of key"<<endl;
292. return 0;
293. }
294. if (k > p->n)
295. {
296. cout<<"Error!! New key is greater than current
key"<<endl;
297. return 0;
298. }
299. p->n = k;
300. y = p;
301. z = p->parent;
302. while (z != NULL && y->n < z->n)
303. {
304. temp = y->n;
305. y->n = z->n;
306. z->n = temp;
307. y = z;
308. z = z->parent;
309. }
310. EC cout<<"Key reduced successfully"<<endl;
311. }
312. /*
313. * Delete Nodes in Binomial Heap
314. */
315. int BinomialHeap::Delete(node* H, int k)
316. {
317. node* np;
318. if (H == NULL)
R
319. {
320. cout<<"\nHEAP EMPTY!!!!!";
321. return 0;
322. }
TK

323. Decrease_key(H, k, -1000);

324. np = Extract_Min(H);
325. if (np != NULL)
326. cout<<"Node Deleted Successfully"<<endl;
327. }
328. /*
329. * Main Contains Menu
330. */
331. int main()
332. {
333. int n, m, l, i;
334. BinomialHeap bh;
335. node* p;
336. node *H;
337. H = bh.Initializeheap();
338. char ch;
339. while (1)
340. {
341. cout<<"----------------------------"<<endl;
342. cout<<"Operations on Binomial heap"<<endl;
343. cout<<"----------------------------"<<endl;
344. cout<<"1)Insert Element in the heap"<<endl;
345. cout<<"2)Extract Minimum key node"<<endl;
346. cout<<"3)Decrease key of a node"<<endl;
347. cout<<"4)Delete a node"<<endl;
 348. cout<<"5)Display Heap"<<endl;
349. cout<<"6)Exit"<<endl;
350. cout<<"Enter Your Choice: ";
351. cin>>l;
352. switch(l)
353. {
354. case 1:
355. cout<<"Enter the element to be inserted: ";
356. cin>>m;
357. p = bh.Create_node(m);
358. H = bh.Insert(H, p);
359. break;
360. case 2:
361. p = bh.Extract_Min(H);
362. if (p != NULL)
363. cout<<"The node with minimum key: "<<p-
>n<<endl;
364. else
365. cout<<"Heap is empty"<<endl;
366. break;
367. case 3:
368. cout<<"Enter the key to be decreased: ";
369. cin>>m;
370. EC cout<<"Enter new key value: ";
371. cin>>l;
372. bh.Decrease_key(H, m, l);
373. break;
374. case 4:
375. cout<<"Enter the key to be deleted: ";
376. cin>>m;
377. bh.Delete(H, m);
378. break;
R
379. case 5:
380. cout<<"The Heap is: "<<endl;
381. bh.Display(H);
382. break;
TK

383. case 6:
384. exit(1);
385. default:
386. cout<<"Wrong Choice";
387. }
388. }
389. return 0;
390. }
Out put:
$ g++ binomialheap.cpp
$ a.out
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 9
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 8
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 7
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
EC
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 6
----------------------------
R
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
TK

3)Decrease key of a node

4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 4
Enter the key to be deleted: 6
Key reduced successfully
Node Deleted Successfully
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display HeapEC
6)Exit
Enter Your Choice: 5
The root nodes are:
5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
R
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
TK

6)Exit
Enter Your Choice: 6

------------------
(program exited with code: 1)
Press return to continue

Write a program to perform the following operations:

1.Insert an element in to a AVL tree.

2.Delete an element from a AVL tree.

3. Search for a key element in a AVL search tree.

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
struct node *left;
int data;
int height;
struct node *right;
};

class AVL
{
private:

public:
struct node * root;
AVL(){
this->root = NULL;

int calheight(struct node *p){

if(p->left && p->right){

if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
EC
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;

int bf(struct node *n){

R
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
TK

return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}

struct node * llrotation(struct node *n){

struct node *p;
struct node *tp;
p = n;
tp = p->left;

p->left = tp->right;
tp->right = p;

return tp;
}

struct node * rrrotation(struct node *n){

struct node *p;
struct node *tp;
p = n;
tp = p->right;
 p->right = tp->left;
tp->left = p;

return tp;
}

struct node * rlrotation(struct node *n){

struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;

p -> right = tp2->left;

tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;

return tp2;
}
EC
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
R
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
TK

return tp2;
}

struct node* insert(struct node *r,int data){

if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}

r->height = calheight(r);

if(bf(r)==2 && bf(r->left)==1){

 r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}

return r;

void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
EC
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);

while(!q.empty()){
cur = q.front();
R
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
TK

q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;

if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}

}
}

struct node * deleteNode(struct node *p,int data){

if(p->left == NULL && p->right == NULL){

if(p==this->root)
this->root = NULL;
delete p;
return NULL;
 }

struct node *t;

struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}

if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }

EC
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }

return p;
R
}

struct node* inpre(struct node* p){

while(p->right!=NULL)
TK

p = p->right;
return p;
}

struct node* insuc(struct node* p){

while(p->left!=NULL)
p = p->left;

return p;
}

~AVL(){

}
};

int main(){

AVL b;
int c,x;

do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
 cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";

cin>>c;

switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;

case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;

case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
EC
case 0:
break;
}

} while(c!=0);

}
R
Output:
TK

Write a program to perform the following operations:

1.Insert an element in to a Red black tree.

2.Delete an element from a Red black tree.

3. Search for a key element in a Red black tree.

#include<iostream>

using namespace std;

struct node
{
int key;
node *parent;
char color;
node *left;
node *right;
};
class RBtree
{
node *root;
node *q;
public :
RBtree()
{
q=NULL;
EC root=NULL;
}
void insert();
void insertfix(node *);
void leftrotate(node *);
void rightrotate(node *);
void del();
node* successor(node *);
R
void delfix(node *);
void disp();
void display( node *);
void search();
TK

};
void RBtree::insert()
{
int z,i=0;
cout<<"\nEnter key of the node to be inserted: ";
cin>>z;
node *p,*q;
node *t=new node;
t->key=z;
t->left=NULL;
t->right=NULL;
t->color='r';
p=root;
q=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(p!=NULL)
{
 q=p;
if(p->key<t->key)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->key<t->key)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
void RBtree::insertfix(node *t)
{
node *u;
if(root==t)
{
t->color='b';
return;
} EC
while(t->parent!=NULL&&t->parent->color=='r')
{
node *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
{
R
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
TK

u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate(t);
}
t->parent->color='b';
g->color='r';
rightrotate(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
 {
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
t->parent->color='b';
g->color='r';
leftrotate(g);
}
}
root->color='b';
}
} EC
void RBtree::del()
{
if(root==NULL)
{
cout<<"\nEmpty Tree." ;
return ;
R
}
int x;
cout<<"\nEnter the key of the node to be deleted: ";
cin>>x;
TK

node *p;
p=root;
node *y=NULL;
node *q=NULL;
int found=0;
while(p!=NULL&&found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
{
cout<<"\nElement Not Found.";
return ;
}
else
 {
cout<<"\nDeleted Element: "<<p->key;
cout<<"\nColour: ";
if(p->color=='b')
cout<<"Black\n";
else
cout<<"Red\n";

if(p->parent!=NULL)
cout<<"\nParent: "<<p->parent->key;
else
cout<<"\nThere is no parent of the node. ";
if(p->right!=NULL)
cout<<"\nRight Child: "<<p->right->key;
else
cout<<"\nThere is no right child of the node. ";
if(p->left!=NULL)
cout<<"\nLeft Child: "<<p->left->key;
else
cout<<"\nThere is no left child of the node. ";
cout<<"\nNode Deleted.";
if(p->left==NULL||p->right==NULL)
ECy=p;
else
y=successor(p);
if(y->left!=NULL)
q=y->left;
else
{
R
if(y->right!=NULL)
q=y->right;
else
q=NULL;
TK

}
if(q!=NULL)
q->parent=y->parent;
if(y->parent==NULL)
root=q;
else
{
if(y==y->parent->left)
y->parent->left=q;
else
y->parent->right=q;
}
if(y!=p)
{
p->color=y->color;
p->key=y->key;
}
if(y->color=='b')
delfix(q);
}
}

void RBtree::delfix(node *p)

{
node *s;
while(p!=root&&p->color=='b')
{
if(p->parent->left==p)
{
s=p->parent->right;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
leftrotate(p->parent);
s=p->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
EC if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate(s);
s=p->parent->right;
}
s->color=p->parent->color;
R
p->parent->color='b';
s->right->color='b';
leftrotate(p->parent);
p=root;
TK

}
}
else
{
s=p->parent->left;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
rightrotate(p->parent);
s=p->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->left->color=='b')
{
s->right->color='b';
s->color='r';
 leftrotate(s);
s=p->parent->left;
}
s->color=p->parent->color;
p->parent->color='b';
s->left->color='b';
rightrotate(p->parent);
p=root;
}
}
p->color='b';
root->color='b';
}
}

void RBtree::leftrotate(node *p)

{
if(p->right==NULL)
return ;
else
{
node *y=p->right;
EC
if(y->left!=NULL)
{
p->right=y->left;
y->left->parent=p;
}
else
p->right=NULL;
R
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
TK

else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->left=p;
p->parent=y;
}
}
void RBtree::rightrotate(node *p)
{
if(p->left==NULL)
return ;
else
{
node *y=p->left;
if(y->right!=NULL)
{
p->left=y->right;
y->right->parent=p;
}
 else
p->left=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->right=p;
p->parent=y;
}
}

node* RBtree::successor(node *p)

{
node *y=NULL;
if(p->left!=NULL)
EC
{
y=p->left;
while(y->right!=NULL)
y=y->right;
}
else
{
R
y=p->right;
while(y->left!=NULL)
y=y->left;
}
TK

return y;
}

void RBtree::disp()
{
display(root);
}
void RBtree::display(node *p)
{
if(root==NULL)
{
cout<<"\nEmpty Tree.";
return ;
}
if(p!=NULL)
{
cout<<"\n\t NODE: ";
cout<<"\n Key: "<<p->key;
cout<<"\n Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
 if(p->parent!=NULL)
cout<<"\n Parent: "<<p->parent->key;
else
cout<<"\n There is no parent of the node. ";
if(p->right!=NULL)
cout<<"\n Right Child: "<<p->right->key;
else
cout<<"\n There is no right child of the node. ";
if(p->left!=NULL)
cout<<"\n Left Child: "<<p->left->key;
else
cout<<"\n There is no left child of the node. ";
cout<<endl;
if(p->left)
{
cout<<"\n\nLeft:\n";
display(p->left);
}
/*else
cout<<"\nNo Left Child.\n";*/
if(p->right)
{ EC
cout<<"\n\nRight:\n";
display(p->right);
}
/*else
cout<<"\nNo Right Child.\n"*/
}
}
R
void RBtree::search()
{
if(root==NULL)
{
TK

cout<<"\nEmpty Tree\n" ;
return ;
}
int x;
cout<<"\n Enter key of the node to be searched: ";
cin>>x;
node *p=root;
int found=0;
while(p!=NULL&& found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
cout<<"\nElement Not Found.";
else
 {
cout<<"\n\t FOUND NODE: ";
cout<<"\n Key: "<<p->key;
cout<<"\n Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<"\n Parent: "<<p->parent->key;
else
cout<<"\n There is no parent of the node. ";
if(p->right!=NULL)
cout<<"\n Right Child: "<<p->right->key;
else
cout<<"\n There is no right child of the node. ";
if(p->left!=NULL)
cout<<"\n Left Child: "<<p->left->key;
else
cout<<"\n There is no left child of the node. ";
cout<<endl;

}
}

int main()
EC
{
int ch,y=0;
RBtree obj;
do
R
{
cout<<"\n\t RED BLACK TREE " ;
cout<<"\n 1. Insert in the tree ";
cout<<"\n 2. Delete a node from the tree";
TK

cout<<"\n 3. Search for an element in the tree";

cout<<"\n 4. Display the tree ";
cout<<"\n 5. Exit " ;
cout<<"\nEnter Your Choice: ";
cin>>ch;
switch(ch)
{
case 1 : obj.insert();
cout<<"\nNode Inserted.\n";
break;
case 2 : obj.del();
break;
case 3 : obj.search();
break;
case 4 : obj.disp();
break;
case 5 : y=1;
break;
default : cout<<"\nEnter a Valid Choice.";
}
cout<<endl;

}while(y!=1);
 return 1;
}
Out put:

EC
R
TK

Write a program to implement all the functions of a dictionary using hashing.

#include<iostream>

#include<conio.h>

#include<stdlib.h>

using namespace std;

# define max 10

typedef struct list

int data;
 struct list *next;

} node_type;

node_type *ptr[max],*root[max],*temp[max];

class Dictionary

public:

int index;

Dictionary();

void insert(int);

void search(int);
EC
void delete_ele(int);

};

Dictionary::Dictionary()
R
{

index=-1;
TK

for(int i=0; i<max; i++)

root[i]=NULL;

ptr[i]=NULL;

temp[i]=NULL;

void Dictionary::insert(int key)

index=int(key%max);
 ptr[index]=(node_type*)malloc(sizeof(node_type));

ptr[index]->data=key;

if(root[index]==NULL)

root[index]=ptr[index];

root[index]->next=NULL;

temp[index]=ptr[index];

else

{ EC
temp[index]=root[index];

while(temp[index]->next!=NULL)

temp[index]=temp[index]->next;
R
temp[index]->next=ptr[index];

}
TK

void Dictionary::search(int key)

int flag=0;

index=int(key%max);

temp[index]=root[index];

while(temp[index]!=NULL)

if(temp[index]->data==key)

{
 cout<<"\nSearch key is found!!";

flag=1;

break;

else temp[index]=temp[index]->next;

if (flag==0)

cout<<"\nsearch key not found.......";

void Dictionary::delete_ele(int key)

EC
{

index=int(key%max);

temp[index]=root[index];
R
while(temp[index]->data!=key && temp[index]!=NULL)

{
TK

ptr[index]=temp[index];

temp[index]=temp[index]->next;

ptr[index]->next=temp[index]->next;

cout<<"\n"<<temp[index]->data<<" has been deleted.";

temp[index]->data=-1;

temp[index]=NULL;

free(temp[index]);

main()
{

int val,ch,n,num;

char c;

Dictionary d;

do

cout<<"\nMENU:\n1.Create";

cout<<"\n2.Search for a value\n3.Delete an value";

cout<<"\nEnter your choice:";

cin>>ch;
EC
switch(ch)

case 1:
R
cout<<"\nEnter the number of elements to be inserted:";

cin>>n;
TK

cout<<"\nEnter the elements to be inserted:";

for(int i=0; i<n; i++)

cin>>num;

d.insert(num);

break;

case 2:

cout<<"\nEnter the element to be searched:";

cin>>n;
 d.search(n);

case 3:

cout<<"\nEnter the element to be deleted:";

cin>>n;

d.delete_ele(n);

break;

default:

cout<<"\nInvalid Choice.";

cout<<"\nEnter y to Continue:";
EC
cin>>c;

while(c=='y');
R
getch();

}
TK

OUTPUT:
MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:1

Enter the number of elements to be inserted:3

Enter the elements to be inserted:12

23
56

Enter y to Continue:y

MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:2

Enter the element to be searched:23

Search key is found!!
Enter the element to be deleted:23

23 has been deleted.

Enter y to Continue:y

MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:

write a c++ program to implementing Knuth-Morris-Pratt pattern matching algorithm.

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
4.
5. void computeLPSArray(char *pat, int M, int *lps);
6.
7. void KMPSearch(char *pat, char *txt)
8. { EC
9. int M = strlen(pat);
10. int N = strlen(txt);
11.
12. // create lps[] that will hold the longest prefix
suffix values for pattern
13. int *lps = (int *)malloc(sizeof(int)*M);
14. int j = 0; // index for pat[]
15.
R
16. // Preprocess the pattern (calculate lps[] array)
17. computeLPSArray(pat, M, lps);
18.
19. int i = 0; // index for txt[]
TK

20. while(i < N)

21. {
22. if(pat[j] == txt[i])
23. {
24. j++;
25. i++;
26. }
27.
28. if (j == M)
29. {
30. printf("Found pattern at index %d \n", i-j);
31. j = lps[j-1];
32. }
33.
34. // mismatch after j matches
35. else if(pat[j] != txt[i])
36. {
37. // Do not match lps[0..lps[j-1]] characters,
38. // they will match anyway
39. if(j != 0)
40. j = lps[j-1];
41. else
42. i = i+1;
43. }
44. }
 45. free(lps); // to avoid memory leak
46. }
47.
48. void computeLPSArray(char *pat, int M, int *lps)
49. {
50. int len = 0; // lenght of the previous longest prefix
suffix
51. int i;
52.
53. lps[0] = 0; // lps[0] is always 0
54. i = 1;
55.
56. // the loop calculates lps[i] for i = 1 to M-1
57. while(i < M)
58. {
59. if(pat[i] == pat[len])
60. {
61. len++;
62. lps[i] = len;
63. i++;
64. }
65. else // (pat[i] != pat[len])
66. {
67. EC if( len != 0 )
68. {
69. // This is tricky. Consider the example AAACAAAA
and i = 7.
70. len = lps[len-1];
71.
72. // Also, note that we do not increment i here
73. }
74. else // if (len == 0)
R
75. {
76. lps[i] = 0;
77. i++;
78. }
TK

79. }
80. }
81. }
82.
83. // Driver program to test above function
84. int main()
85. {
86. char *txt = "ABABDABACDABABCABAB";
87. char *pat = "ABABCABAB";
88. KMPSearch(pat, txt);
89. return 0;
90. }

Output

Found pattern at index 10

write a c++ program to implementing Brute Force pattern matching algorithm

1. #include<stdio.h>
2. #include<string.h>
3. void search(char *pat, char *txt)
4. {
5. int M = strlen(pat);
 6. int N = strlen(txt);
7.
8. /* A loop to slide pat[] one by one */
9. for (int i = 0; i <= N - M; i++)
10. {
11. int j;
12.
13. /* For current index i, check for pattern match */
14. for (j = 0; j < M; j++)
15. {
16. if (txt[i + j] != pat[j])
17. break;
18. }
19. if (j == M) // if pat[0...M-1] = txt[i, i+1,
...i+M-1]
20. {
21. printf("Pattern found at index %d \n", i);
22. }
23. }
24. }
25.
26. /* Driver program to test above function */
27. int main()
28. EC {
29. char *txt = "AABAACAADAABAAABAA";
30. char *pat = "AABA";
31. search(pat, txt);
32. return 0;
33. }
Output:
R
$ g++ StringMatchingNaive.cpp
$ a.out

Pattern found at index 0

TK

Pattern found at index 9

Pattern found at index 13
------------------
(program exited with code: 0)
Press return to continue

write a c++ program to implementing Boyer pattern matching algorithm.

1. # include <limits.h>
2. # include <string.h>
3. # include <stdio.h>
4.
5. # define NO_OF_CHARS 256
6.
7. // A utility function to get maximum of two integers
8. int max(int a, int b)
9. {
10. return (a > b) ? a : b;
11. }
12.
13. // The preprocessing function for Boyer Moore's bad
character heuristic
 14. void badCharHeuristic(char *str, int size, int
badchar[NO_OF_CHARS])
15. {
16. int i;
17.
18. // Initialize all occurrences as -1
19. for (i = 0; i < NO_OF_CHARS; i++)
20. badchar[i] = -1;
21.
22. // Fill the actual value of last occurrence of a
character
23. for (i = 0; i < size; i++)
24. badchar[(int) str[i]] = i;
25. }
26.
27. void search(char *txt, char *pat)
28. {
29. int m = strlen(pat);
30. int n = strlen(txt);
31.
32. int badchar[NO_OF_CHARS];
33.
34. badCharHeuristic(pat, m, badchar);
35. EC
36. int s = 0; // s is shift of the pattern with respect to
text
37. while (s <= (n - m))
38. {
39. int j = m - 1;
40.
41. while (j >= 0 && pat[j] == txt[s + j])
42. j--;
R
43.
44. if (j < 0)
45. {
46. printf("\n pattern occurs at shift = %d", s);
TK

47.
48. s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
49.
50. }
51.
52. else
53. s += max(1, j - badchar[txt[s + j]]);
54. }
55. }
56.
57. /* Driver program to test above funtion */
58. int main()
59. {
60. char txt[] = "ABAAABCD";
61. char pat[] = "ABC";
62. search(txt, pat);
63. return 0;
64. }
Output:

$ g++ Boyer-Moore.cpp
$ a.out

pattern occurs at shift = 4

------------------
(program exited with code: 0)
Press return to continue

EC
R
TK