ADS LAB MANUAL

WEEK-1

Write a program to perform the following operations:

a) Insert an element into a binary search tree.

b) Delete an element from a binary search tree.
c) Search for a key element in a binary search tree.

Source Code:

A)

#include<iostream>

using namespace std;

template<class t>

class bst

struct NODE

t data;

NODE* left, *right;

};

public:

NODE* createnewnode(t data)

NODE* createnewnode=new NODE();

createnewnode->data=data;

createnewnode->left=createnewnode->right=NULL;

return createnewnode;

NODE* Insert(NODE* root, t data)

if(root==NULL)

root=createnewnode(data);

}
 else if(data<=root->data)

root->left=Insert(root->left,data);

else

root->right=Insert(root->right,data);

return root;

void inorder(NODE* root)

if(root!=NULL)

inorder(root->left);

cout<<root->data<<"";

inorder(root->right);

bst()

NODE* root=NULL;

t a,b,c,d,e,f;

cout<<endl<<"Enter the data"<<endl;

cin>>a;

cin>>b;

cin>>c;

cin>>d;

cin>>e;

cin>>f;

root=Insert(root,a);
 root=Insert(root,b);

root=Insert(root,c);

root=Insert(root,d);

root=Insert(root,e);

root=Insert(root,f);

cout<<"The binary search tree"<<endl;

cout<<"inorder:";

inorder(root);

cout<<endl;

insertion(root);

NODE* insertion(NODE* root)

t n;

cout<<"Enter the element to be insertion in the BST"<<endl;

cin>>n;

root=Insert(root,n);

cout<<"The binary search tree 2"<<endl;

cout<<"inorder:";

inorder(root);

};

int main()

bst<int>a;

cout<<endl<<"-----------------"<<endl;

bst<char>b;

return 0;

Output:-
b)

#include <bits/stdc++.h>

using namespace std;

struct Node

int data;

Node *left, *right;

};

Node* newNode(int data)

Node* temp = new Node();

temp->data = data;

temp->left = temp->right = NULL;

return temp;

Node* Tree(Node* root, int data)

Node *temp = newNode(data);

Node *temp1 = new Node;

temp1 = root;

if(root == NULL)
 root = temp;

else

while(temp1 != NULL)

if(temp1->data < data )

if(temp1->right == NULL)

temp1->right = temp;

break;

temp1 = temp1->right;

else if(temp1->data > data)

if(temp1->left == NULL)

temp1->left = temp;

break;

temp1 = temp1->left;

return root;
}

void display(struct Node* root)

if (root != NULL)

display(root->left);

cout<<root->data<<" ";

display(root->right);

void Search(Node *root, int data)

int pos = 0;

Node *temp = new Node;

temp = root;

while(temp != NULL)

pos++;

if(temp->data == data)

cout<<"\nData found at position: "<<pos;

return;

else if(temp->data > data)

 temp = temp->left;

else

temp = temp->right;

cout<<"\n Data not found";

return;

Node* Min(Node*root)

while(root->left!=NULL)

root=root->left;

return root;

Node* Delete( Node* root,int value)

if(root==NULL)

return root;

else if(value< root->data)

root->left= Delete(root->left,value);

else if(value> root->data)

{

root->right= Delete(root->right,value);

else

if(root->left==NULL&&root->right==NULL)

delete root;

root=NULL;

return root;

else if(root->left==NULL)

struct Node* temp=root;

root=root->right;

delete temp;

return root;

else if(root->right==NULL)

struct Node* temp=root;

root=root->left;

delete temp;

return root;

else
 {

struct Node*temp=Min(root->right);

root->data=temp->data;

root->right=Delete(root->right,temp->data);

return root;

int main()

char ch;

int n, arr[20],size;

Node *root = new Node;

root = NULL;

cout<<"Enter the size of array : ";

cin>>size;

cout<<"Enter the elements in array : ";

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

cin>>arr[i];

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

root = Tree(root, arr[i]);

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

 cin>>n;

Search(root, n);

Delete(root,n);

cout<<"\nElement Deleted"<<endl;

cout<<"\nAfter Deletion: "<<endl;

cout<<"Elements are: ";

display(root);

cout<<endl;

return 0;

Output:-

c)

#include<iostream>

using namespace std;

struct node {
 int d;

node *left;

node *right;

};

node* CreateNode(int d) {

node *newnode = new node;

newnode->d = d;

newnode->left = NULL;

newnode->right = NULL;

return newnode;

node* InsertIntoTree(node* root, int d) {

node *temp = CreateNode(d);

node *t = new node;

t = root;

if(root == NULL)

root = temp;

else {

while(t != NULL) {

if(t->d < d) {

if(t->right == NULL) {

t->right = temp;

break;

t = t->right;

} else if(t->d > d) {

if(t->left == NULL) {

t->left = temp;

break;

t = t->left;
 }

return root;

void Search(node *root, int d) {

int depth = 0;

node *temp = new node;

temp = root;

while(temp != NULL) {

depth++;

if(temp->d == d) {

cout<<"\nitem found at depth: "<<depth;

return;

} else if(temp->d > d)

temp = temp->left;

else

temp = temp->right;

cout<<"\n item not found";

return;

int main() {

char ch;

int n,c, i, a[10] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76};

node *root = new node;

root = NULL;

for (i = 0; i < 10; i++){

root = InsertIntoTree(root, a[i]);

up:
 cout<<"\nEnter the Element to be searched: ";

cin>>n;

Search(root, n);

cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";

cin>>ch;

if(c == 'y' || c == 'Y')

goto up;

return 0;

Output:-

WEEK-2

Write a program for implementing the following sorting methods:

a) Merge sort
b) Heap sort
c) Quick sort

SOURCE CODE:

a)

#include<iostream>

using namespace std;

void merge(int array[], int left, int mid, int right)

int subArrayOne = mid-left+1;

int subArrayTwo = right-mid;

int *leftArray=new int[subArrayOne];

 int *rightArray=new int[subArrayTwo];

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

leftArray[i]=array[left+i];

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

rightArray[j]=array[mid+1+j];

int indexOfSubArrayOne=0;

int indexOfSubArrayTwo=0;

int indexOfMergedArray=left;

while(indexOfSubArrayOne<subArrayOne && indexOfSubArrayTwo<subArrayTwo)

if(leftArray[indexOfSubArrayOne]<=rightArray[indexOfSubArrayTwo])

array[indexOfSubArrayOne]= rightArray[indexOfSubArrayTwo];

indexOfSubArrayOne++;

else

array[indexOfMergedArray]=rightArray[indexOfSubArrayOne];

indexOfSubArrayOne++;

indexOfMergedArray++;

while(indexOfSubArrayOne<subArrayOne)

array[indexOfMergedArray]=leftArray[indexOfSubArrayOne];

indexOfSubArrayOne++;

indexOfMergedArray++;
 }

while(indexOfSubArrayTwo<subArrayTwo)

array[indexOfMergedArray]=rightArray[indexOfSubArrayTwo];

indexOfSubArrayTwo++;

indexOfMergedArray++;

delete[] leftArray;

delete[] rightArray;

void mergeSort(int array[], int left, int right)

if(left<right)

int mid=left+(right-left)/2;

mergeSort(array,left,mid);

mergeSort(array,mid+1,right);

merge(array,left,mid,right);

void printArray(int array[],int size)

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

cout<<array[i]<<"";

cout<<endl;

int main()

int array[]={38,27,43,3,9,82,10};
 int size=sizeof(array) / sizeof(array[0]);

cout<<"Original array:";

printArray(array,size);

mergeSort(array,0,size-1);

cout<<"Sorted array:";

printArray(array,size);

return 0;

OUTPUT:-

Original Array:- 38,27,43,3,9,82,10

Sorted Array: 3,9,10,27,38,43,82

b)

#include<iostream>

using namespace std;

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

int largest=i;

int l=2*i+1;

int r=2*i+2;

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

largest=l;

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

largest=r;

if(largest!=i)

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

heapify(arr, n, largest);
 }

void heapSort(int arr[], int n)

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

heapify(arr, n ,i);

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

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

heapify(arr, i, 0);

void printArray(int arr[], int n)

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

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

cout<<endl;

int main()

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

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

cout<<"Original array:";

printArray(arr, size);

heapSort(arr, size);

cout<<"Sorted array:";

printArray(arr,size);
 return 0;

OUTPUT:-

c)

#include <iostream>

using namespace std;

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

int pivot = arr[start];

int count = 0;

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

if (arr[i] <= pivot)

count++;

int pivotIndex = start + count;

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

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) {

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

return pivotIndex;

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

if (start >= end)

return;

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

quickSort(arr, start, p - 1);

quickSort(arr, p + 1, end);
}

int main()

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

int n = 6;

quickSort(arr, 0, n - 1);

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

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

return 0;

OUTPUT:-

WEEK-3

Write a 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.

SOURCE CODE:

a)

#include <iostream>

using namespace std;

class Node {

int *keys;
 int t;

Node **C;

int n;

bool leaf;

public:

Node(int _t, bool _leaf);

void insertNonFull(int k);

void splitChild(int i, Node *y);

void traverse();

friend class BTree;

};

class BTree {

Node *root;

int t;

public:

BTree(int _t) {

root = NULL;

t = _t;

void traverse() {

if (root != NULL)

root->traverse();

void insert(int k);

};

Node::Node(int t1, bool leaf1) {

t = t1;

leaf = leaf1;

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

C = new Node *[2 * t];

n = 0;

void Node::traverse() {

int i;

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

if (leaf == false)

C[i]->traverse();

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

if (leaf == false)

C[i]->traverse();

void BTree::insert(int k) {

if (root == NULL) {

root = new Node(t, true);

root->keys[0] = k;

root->n = 1;

} else {

if (root->n == 2 * t - 1) {
 Node *s = new Node(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);

void Node::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;

} else {

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

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

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

if (keys[i + 1] < k)

i++;

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

void Node::splitChild(int i, Node *y) {

Node *z = new Node(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;

int main() {

BTree t(3);

t.insert(8);

t.insert(9);

t.insert(10);

t.insert(11);

t.insert(15);

t.insert(16);

t.insert(17);

t.insert(18);

t.insert(20);

t.insert(23);

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

t.traverse();

OUTPUT:-

b)

#include <iostream>

using namespace std;

class BTreeNode {

int *keys;
 int t;

BTreeNode **C;

int n;

bool leaf;

public:

BTreeNode(int _t, bool _leaf);

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

};

BTreeNode::BTreeNode(int t1, bool leaf1) {

t = t1;

leaf = leaf1;

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

C = new BTreeNode *[2 * t];

n = 0;

int BTreeNode::findKey(int k) {

int idx = 0;

while (idx < n && keys[idx] < k)

++idx;

return idx;

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

void BTreeNode::removeFromLeaf(int idx) {

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

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

return;

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)

cur = cur->C[0];

return cur->keys[0];

void BTreeNode::fill(int idx) {

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

borrowFromPrev(idx);

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

borrowFromNext(idx);

else {

if (idx != n)

merge(idx);

else

merge(idx - 1);

return;

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;

void BTreeNode::borrowFromNext(int idx) {

BTreeNode *child = C[idx];

BTreeNode *sibling = C[idx + 1];

child->keys[(child->n)] = keys[idx];

if (!(child->leaf))

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;

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)

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

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

n--;

delete (sibling);

return;

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

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;

} else {

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

i--;

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

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

if (keys[i + 1] < k)

i++;

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

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

void BTreeNode::traverse() {

int i;

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

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

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

if (leaf == false)

C[i]->traverse();

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();

t.deletion(20);

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

t.traverse();

OUTPUT:-

c)

#include <iostream>

using namespace std;

const int t = 3;

class BTreeNode {

public:

int* keys; // Array of keys

int t; // Minimum degree (defines the range for the number of keys)
 BTreeNode** C; // Array of child pointers

int n; // Current number of keys

bool leaf; // True if the node is a leaf

BTreeNode(bool leaf);

void traverse();

BTreeNode* search(int k);

friend class BTree;

};

class BTree {

BTreeNode* root; // Pointer to the root node

int t; // Minimum degree

public:

BTree() {

root = NULL;

this->t = ::t;

void traverse() {

if (root != NULL)

root->traverse();

}
 BTreeNode* search(int k) {

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

void insert(int k);

};

BTreeNode::BTreeNode(bool leaf) {

this->leaf = leaf;

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

C = new BTreeNode*[2 * t];

n = 0;

void BTreeNode::traverse() {

int i;

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

if (!leaf)

C[i]->traverse();

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

if (!leaf)

C[i]->traverse();

BTreeNode* BTreeNode::search(int k) {

int i = 0;

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

i++;
 if (keys[i] == k)

return this;

if (leaf)

return NULL;

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

void BTree::insert(int k) {

if (root == NULL) {

root = new BTreeNode(true);

root->keys[0] = k;

root->n = 1;

} else {

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

BTreeNode* s = new BTreeNode(false);

s->C[0] = root;

for (int j = t; j <= 2 * t - 2; j++)

s->keys[j - t] = root->keys[j];

s->n = t - 1;

root = s;

BTreeNode* cur = root;

while (!cur->leaf) {

int idx = cur->n;

while (idx > 0 && cur->keys[idx - 1] > k)

 idx--;

cur = cur->C[idx];

cur->keys[cur->n] = k;

cur->n++;

int main() {

BTree t;

t.insert(10);

t.insert(20);

t.insert(5);

t.insert(6);

t.insert(12);

t.insert(30);

t.insert(7);

t.insert(17);

cout << "Traversal of the constructed B-Tree: ";

t.traverse();

cout << endl;

int key = 6;

if (t.search(key) != NULL)

cout << "Key " << key << " found in the B-Tree.\n";

else

cout << "Key " << key << " not found in the B-Tree.\n";
 key = 15;

if (t.search(key) != NULL)

cout << "Key " << key << " found in the B-Tree.\n";

else

cout << "Key " << key << " not found in the B-Tree.\n";

return 0;

OUTPUT:-

WEEK-4:

Write a program to perform the following operations:

a) Insert an element into a Min-Max heap

b) Delete an element from a Min-Max heap
c) Search for a key element in a Min-Max heap

SOURCE CODE:

a)

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

class MinMaxHeap {

private:

vector<int> heap;

bool isMinLevel(int index) {

return (int(log2(index + 1)) % 2 == 0);

}

void bubbleUp(int index) {

if (index == 0) return;

int parent = (index - 1) / 2;

if (isMinLevel(index)) {

if (heap[index] > heap[parent]) {

swap(heap[index], heap[parent]);

bubbleUpMax(parent);

} else {

bubbleUpMin(index);

} else {

if (heap[index] < heap[parent]) {

swap(heap[index], heap[parent]);

bubbleUpMin(parent);

} else {

bubbleUpMax(index);

void bubbleUpMin(int index) {

if (index <= 2) return; // No grandparent for indices <= 2

int grandparent = (index - 3) / 4;

if (heap[index] < heap[grandparent]) {

swap(heap[index], heap[grandparent]);

bubbleUpMin(grandparent);
 }

void bubbleUpMax(int index) {

if (index <= 2) return; // No grandparent for indices <= 2

int grandparent = (index - 3) / 4;

if (heap[index] > heap[grandparent]) {

swap(heap[index], heap[grandparent]);

bubbleUpMax(grandparent);

public:

// Insert a new element into the heap

void insert(int value) {

heap.push_back(value);

bubbleUp(heap.size() - 1);

void printHeap() {

for (size_t i = 0; i < heap.size(); i++) {

cout << heap[i] << " ";

cout << endl;

};

int main() {

MinMaxHeap heap;
 heap.insert(10);

heap.insert(20);

heap.insert(5);

heap.insert(30);

heap.insert(15);

heap.insert(40);

heap.insert(1);

// Print the heap

cout << "Elements in Min-Max Heap: ";

heap.printHeap();

return 0;

OUTPUT:-

b)

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

class MinMaxHeap {

private:

vector<int> heap;

bool isMinLevel(int index) {

return (int(log2(index + 1)) % 2 == 0);

}
void trickleDownMin(int index) {

int smallest = index;

for (int i = 2 * index + 1; i <= 2 * index + 2; i++) { // Children

if (i < heap.size() && heap[i] < heap[smallest])

smallest = i;

for (int i = 4 * index + 3; i <= 4 * index + 6; i++) { // Grandchildren

if (i < heap.size() && heap[i] < heap[smallest])

smallest = i;

if (smallest != index) {

if (smallest >= 4 * index + 3) { // Grandchild

swap(heap[smallest], heap[index]);

int parent = (smallest - 1) / 2;

if (heap[smallest] > heap[parent]) {

swap(heap[smallest], heap[parent]);

trickleDownMin(smallest);

} else { // Child

swap(heap[smallest], heap[index]);

void trickleDownMax(int index) {

int largest = index;

for (int i = 2 * index + 1; i <= 2 * index + 2; i++) { // Children

if (i < heap.size() && heap[i] > heap[largest])

 largest = i;

for (int i = 4 * index + 3; i <= 4 * index + 6; i++) { // Grandchildren

if (i < heap.size() && heap[i] > heap[largest])

largest = i;

if (largest != index) {

if (largest >= 4 * index + 3) { // Grandchild

swap(heap[largest], heap[index]);

int parent = (largest - 1) / 2;

if (heap[largest] < heap[parent]) {

swap(heap[largest], heap[parent]);

trickleDownMax(largest);

} else { // Child

swap(heap[largest], heap[index]);

void trickleDown(int index) {

if (isMinLevel(index))

trickleDownMin(index);

else

trickleDownMax(index);

public:

// Insert a new element into the heap

void insert(int value) {

 heap.push_back(value);

bubbleUp(heap.size() - 1);

void bubbleUp(int index) {

if (index == 0) return;

int parent = (index - 1) / 2;

if (isMinLevel(index)) {

if (heap[index] > heap[parent]) {

swap(heap[index], heap[parent]);

bubbleUpMax(parent);

} else {

bubbleUpMin(index);

} else {

if (heap[index] < heap[parent]) {

swap(heap[index], heap[parent]);

bubbleUpMin(parent);

} else {

bubbleUpMax(index);

void bubbleUpMin(int index) {

if (index <= 2) return; // No grandparent for indices <= 2

int grandparent = (index - 3) / 4;

if (heap[index] < heap[grandparent]) {

 swap(heap[index], heap[grandparent]);

bubbleUpMin(grandparent);

void bubbleUpMax(int index) {

if (index <= 2) return; // No grandparent for indices <= 2

int grandparent = (index - 3) / 4;

if (heap[index] > heap[grandparent]) {

swap(heap[index], heap[grandparent]);

bubbleUpMax(grandparent);

void deleteElement(int value) {

// Find the element's index

int index = -1;

for (size_t i = 0; i < heap.size(); i++) {

if (heap[i] == value) {

index = i;

break;

if (index == -1) {

cout << "Element " << value << " not found in the heap.\n";

return;

heap[index] = heap.back();
 heap.pop_back();

if (index < heap.size()) {

trickleDown(index);

void printHeap() {

for (size_t i = 0; i < heap.size(); i++) {

cout << heap[i] << " ";

cout << endl;

};

int main() {

MinMaxHeap heap;

heap.insert(10);

heap.insert(20);

heap.insert(5);

heap.insert(30);

heap.insert(15);

heap.insert(40);

heap.insert(1);

cout << "Initial Min-Max Heap: ";

heap.printHeap();

cout << "Deleting element 15...\n";

heap.deleteElement(15);
 cout << "Heap after deletion: ";

heap.printHeap();

cout << "Deleting element 1...\n";

heap.deleteElement(1);

cout << "Heap after deletion: ";

heap.printHeap();

cout << "Deleting element 100 (non-existent)...\n";

heap.deleteElement(100);

return 0;

OUTPUT:-

c)

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

class MinMaxHeap {

private:

vector<int> heap;
bool isMinLevel(int index) {

return (int(log2(index + 1)) % 2 == 0);

void bubbleUp(int index) {

if (index == 0) return;

int parent = (index - 1) / 2;

if (isMinLevel(index)) {

if (heap[index] > heap[parent]) {

swap(heap[index], heap[parent]);

bubbleUpMax(parent);

} else {

bubbleUpMin(index);

} else {

if (heap[index] < heap[parent]) {

swap(heap[index], heap[parent]);

bubbleUpMin(parent);

} else {

bubbleUpMax(index);

void bubbleUpMin(int index) {

if (index <= 2) return; // No grandparent for indices <= 2

int grandparent = (index - 3) / 4;

 if (heap[index] < heap[grandparent]) {

swap(heap[index], heap[grandparent]);

bubbleUpMin(grandparent);

void bubbleUpMax(int index) {

if (index <= 2) return; // No grandparent for indices <= 2

int grandparent = (index - 3) / 4;

if (heap[index] > heap[grandparent]) {

swap(heap[index], heap[grandparent]);

bubbleUpMax(grandparent);

public:

void insert(int value) {

heap.push_back(value);

bubbleUp(heap.size() - 1);

bool searchElement(int value) {

for (int i = 0; i < heap.size(); i++) {

if (heap[i] == value) {

return true;

return false;

}
 void printHeap() {

for (size_t i = 0; i < heap.size(); i++) {

cout << heap[i] << " ";

cout << endl;

};

int main() {

MinMaxHeap heap;

heap.insert(10);

heap.insert(20);

heap.insert(5);

heap.insert(30);

heap.insert(15);

heap.insert(40);

heap.insert(1);

cout << "Heap elements: ";

heap.printHeap();

int search1 = 15;

cout << "Searching for " << search1 << ": ";

if (heap.searchElement(search1)) {

cout << "Found\n";

} else {

cout << "Not Found\n";

int search2 = 100;

 cout << "Searching for " << search2 << ": ";

if (heap.searchElement(search2)) {

cout << "Found\n";

} else {

cout << "Not Found\n";

return 0;

OUTPUT:-

WEEK-5

Write a program to perform the following operations:

a) Insert an element into a leftist tree

b) Delete an element from a leftist tree
c) Search for a key element in a leftist tree.

SOURCE CODE:-

a)

#include <iostream>

using namespace std;

struct Node {

int key;

int rank; // Null-path length (NPL)

Node* left;

Node* right;

Node(int value) : key(value), rank(1), left(NULL), right(NULL) {}

};
class LeftistTree {

private:

Node* root;

Node* merge(Node* h1, Node* h2) {

if (!h1) return h2;

if (!h2) return h1;

if (h2->key < h1->key) swap(h1, h2);

h1->right = merge(h1->right, h2);

if (!h1->left || (h1->right && h1->left->rank < h1->right->rank)) {

swap(h1->left, h1->right);

h1->rank = (h1->right ? h1->right->rank : 0) + 1;

return h1;

public:

LeftistTree() : root(NULL) {}

void insert(int key) {

Node* newNode = new Node(key);

root = merge(root, newNode);

void inOrder(Node* node) {

 if (!node) return;

inOrder(node->left);

cout << node->key << " ";

inOrder(node->right);

void printTree() {

cout << "In-order traversal of Leftist Tree: ";

inOrder(root);

cout << endl;

Node* getRoot() {

return root;

};

int main() {

LeftistTree tree;

tree.insert(10);

tree.insert(20);

tree.insert(5);

tree.insert(30);

tree.insert(15);

tree.printTree();

return 0;

OUTPUT:-
 b)

#include <iostream>

using namespace std;

struct Node {

int key;

int rank; // Null-path length (NPL)

Node* left;

Node* right;

Node(int value) : key(value), rank(1), left(NULL), right(NULL) {}

};

class LeftistTree {

private:

Node* root;

Node* merge(Node* h1, Node* h2) {

if (!h1) return h2;

if (!h2) return h1;

if (h2->key < h1->key) swap(h1, h2);

h1->right = merge(h1->right, h2);

if (!h1->left || (h1->right && h1->left->rank < h1->right->rank)) {

swap(h1->left, h1->right);

}
 h1->rank = (h1->right ? h1->right->rank : 0) + 1;

return h1;

public:

LeftistTree() : root(NULL) {}

void insert(int key) {

Node* newNode = new Node(key);

root = merge(root, newNode);

void deleteMin() {

if (!root) {

cout << "The tree is empty. Cannot delete.\n";

return;

Node* oldRoot = root;

root = merge(root->left, root->right);

delete oldRoot;

void inOrder(Node* node) {

if (!node) return;

inOrder(node->left);

cout << node->key << " ";

inOrder(node->right);

}
 void printTree() {

if (!root) {

cout << "The tree is empty.\n";

return;

cout << "In-order traversal of Leftist Tree: ";

inOrder(root);

cout << endl;

};

int main() {

LeftistTree tree;

tree.insert(10);

tree.insert(20);

tree.insert(5);

tree.insert(30);

tree.insert(15);

tree.printTree();

cout << "Deleting the minimum element...\n";

tree.deleteMin();

tree.printTree();

cout << "Deleting another minimum element...\n";

tree.deleteMin();

tree.printTree();
 return 0;

OUTPUT:-

c)

#include <iostream>

using namespace std;

struct Node {

int key;

int rank; // Null-path length (NPL)

Node* left;

Node* right;

Node(int value) : key(value), rank(1), left(NULL), right(NULL) {}

};

class LeftistTree {

private:

Node* root;

Node* merge(Node* h1, Node* h2) {

if (!h1) return h2;

if (!h2) return h1;

if (h2->key < h1->key) swap(h1, h2);

 h1->right = merge(h1->right, h2);

if (!h1->left || (h1->right && h1->left->rank < h1->right->rank)) {

swap(h1->left, h1->right);

h1->rank = (h1->right ? h1->right->rank : 0) + 1;

return h1;

bool search(Node* node, int key) {

if (!node) return false; // Reached a null node

if (node->key == key) return true; // Found the key

return search(node->left, key) || search(node->right, key);

public:

LeftistTree() : root(NULL) {}

void insert(int key) {

Node* newNode = new Node(key);

root = merge(root, newNode);

bool searchKey(int key) {

return search(root, key);

}
 void inOrder(Node* node) {

if (!node) return;

inOrder(node->left);

cout << node->key << " ";

inOrder(node->right);

void printTree() {

if (!root) {

cout << "The tree is empty.\n";

return;

cout << "In-order traversal of Leftist Tree: ";

inOrder(root);

cout << endl;

};

int main() {

LeftistTree tree;

tree.insert(10);

tree.insert(20);

tree.insert(5);

tree.insert(30);

tree.insert(15);

tree.printTree();
 int keyToSearch = 15;

cout << "Searching for key " << keyToSearch << ": ";

if (tree.searchKey(keyToSearch)) {

cout << "Found\n";

} else {

cout << "Not Found\n";

keyToSearch = 25;

cout << "Searching for key " << keyToSearch << ": ";

if (tree.searchKey(keyToSearch)) {

cout << "Found\n";

} else {

cout << "Not Found\n";

return 0;

OUTPUT:-

WEEK-6

Write a program to perform the following operations:

a) Insert an element into a binomial heap.

b) Delete an element from a binomial heap.
c) Search for a key element in a binomial heap.

SOURCE CODE:-

a)

#include <iostream>
#include <climits>

using namespace std;

struct BinomialNode {

int key;

int degree;

BinomialNode* parent;

BinomialNode* child;

BinomialNode* sibling;

BinomialNode(int value) {

key = value;

degree = 0;

parent = child = sibling = NULL;

};

BinomialNode* mergeTrees(BinomialNode* tree1, BinomialNode* tree2) {

if (tree1->key > tree2->key)

swap(tree1, tree2);

tree2->parent = tree1;

tree2->sibling = tree1->child;

tree1->child = tree2;

tree1->degree++;

return tree1;

BinomialNode* mergeHeaps(BinomialNode* heap1, BinomialNode* heap2) {

if (!heap1) return heap2;

if (!heap2) return heap1;

BinomialNode* head;

if (heap1->degree <= heap2->degree) {

head = heap1;
 heap1 = heap1->sibling;

} else {

head = heap2;

heap2 = heap2->sibling;

BinomialNode* tail = head;

while (heap1 && heap2) {

if (heap1->degree <= heap2->degree) {

tail->sibling = heap1;

heap1 = heap1->sibling;

} else {

tail->sibling = heap2;

heap2 = heap2->sibling;

tail = tail->sibling;

tail->sibling = heap1 ? heap1 : heap2;

return head;

BinomialNode* unifyHeaps(BinomialNode* head) {

if (!head || !head->sibling)

return head;

BinomialNode* prev = NULL;

BinomialNode* curr = head;

BinomialNode* next = head->sibling;

while (next) {
 if ((curr->degree != next->degree) ||

(next->sibling && next->sibling->degree == curr->degree)) {

prev = curr;

curr = next;

} else {

if (curr->key <= next->key) {

curr->sibling = next->sibling;

curr = mergeTrees(curr, next);

} else {

if (prev)

prev->sibling = next;

else

head = next;

curr = mergeTrees(next, curr);

next = curr->sibling;

return head;

BinomialNode* insert(BinomialNode* head, int key) {

BinomialNode* newNode = new BinomialNode(key);

return unifyHeaps(mergeHeaps(head, newNode));

void printHeap(BinomialNode* node) {

if (!node) return;

while (node) {

cout << "B" << node->degree << ": ";

cout << endl;

 node = node->sibling;

void printTree(BinomialNode* node) {

if (!node) return;

cout << node->key << " ";

printTree(node->child);

printTree(node->sibling);

int main() {

BinomialNode* heap = NULL;

heap = insert(heap, 10);

heap = insert(heap, 20);

heap = insert(heap, 30);

heap = insert(heap, 40);

heap = insert(heap, 50);

cout << "Binomial Heap after insertions:" << endl;

printHeap(heap);

return 0;

OUTPUT:-

b)

#include <iostream>
#include <climits>

using namespace std;

struct BinomialNode {

int key;

int degree;

BinomialNode* parent;

BinomialNode* child;

BinomialNode* sibling;

BinomialNode(int value) {

key = value;

degree = 0;

parent = NULL;

child = NULL;

sibling = NULL;

};

BinomialNode* mergeTrees(BinomialNode* b1, BinomialNode* b2) {

if (b1->key > b2->key)

swap(b1, b2);

b2->parent = b1;

b2->sibling = b1->child;

b1->child = b2;

b1->degree++;

return b1;

BinomialNode* mergeHeaps(BinomialNode* h1, BinomialNode* h2) {

if (!h1) return h2;

if (!h2) return h1;

 BinomialNode* head = NULL;

BinomialNode* tail = NULL;

if (h1->degree <= h2->degree) {

head = tail = h1;

h1 = h1->sibling;

} else {

head = tail = h2;

h2 = h2->sibling;

while (h1 && h2) {

if (h1->degree <= h2->degree) {

tail->sibling = h1;

h1 = h1->sibling;

} else {

tail->sibling = h2;

h2 = h2->sibling;

tail = tail->sibling;

if (h1) tail->sibling = h1;

if (h2) tail->sibling = h2;

return head;

BinomialNode* unionHeaps(BinomialNode* h1, BinomialNode* h2) {

if (!h1 && !h2) return NULL;

 BinomialNode* merged = mergeHeaps(h1, h2);

if (!merged) return NULL;

BinomialNode* prev = NULL;

BinomialNode* curr = merged;

BinomialNode* next = curr->sibling;

while (next) {

if (curr->degree != next->degree ||

(next->sibling && next->sibling->degree == curr->degree)) {

prev = curr;

curr = next;

} else {

if (curr->key <= next->key) {

curr->sibling = next->sibling;

curr = mergeTrees(curr, next);

} else {

if (!prev) merged = next;

else prev->sibling = next;

curr = mergeTrees(next, curr);

next = curr->sibling;

return merged;

BinomialNode* reverseHeap(BinomialNode* node) {

BinomialNode* prev = NULL;

BinomialNode* curr = node;

BinomialNode* next;
 while (curr) {

next = curr->sibling;

curr->sibling = prev;

prev = curr;

curr = next;

return prev;

BinomialNode* extractMin(BinomialNode*& head) {

if (!head) return NULL;

BinomialNode* prevMin = NULL;

BinomialNode* minNode = head;

BinomialNode* prev = NULL;

BinomialNode* curr = head;

while (curr->sibling) {

if (curr->sibling->key < minNode->key) {

prevMin = curr;

minNode = curr->sibling;

curr = curr->sibling;

if (prevMin)

prevMin->sibling = minNode->sibling;

else

head = minNode->sibling;
 BinomialNode* child = reverseHeap(minNode->child);

head = unionHeaps(head, child);

return minNode;

void decreaseKey(BinomialNode* node, int newKey) {

if (!node || newKey > node->key) return;

node->key = newKey;

BinomialNode* curr = node;

BinomialNode* parent = curr->parent;

while (parent && curr->key < parent->key) {

swap(curr->key, parent->key);

curr = parent;

parent = curr->parent;

void deleteNode(BinomialNode*& head, BinomialNode* node) {

if (!node) return;

decreaseKey(node, INT_MIN);

BinomialNode* minNode = extractMin(head);

delete minNode;

BinomialNode* findNode(BinomialNode* head, int key) {

if (!head) return NULL;

if (head->key == key) return head;

 BinomialNode* childResult = findNode(head->child, key);

if (childResult) return childResult;

return findNode(head->sibling, key);

BinomialNode* insert(BinomialNode* head, int key) {

BinomialNode* newNode = new BinomialNode(key);

return unionHeaps(head, newNode);

void printHeap(BinomialNode* head) {

if (!head) return;

cout << "B" << head->degree << ": ";

BinomialNode* curr = head;

while (curr) {

cout << curr->key << " ";

curr = curr->child;

cout << endl;

printHeap(head->sibling);

int main() {

BinomialNode* heap = NULL;

heap = insert(heap, 10);

heap = insert(heap, 20);

heap = insert(heap, 30);

heap = insert(heap, 40);

heap = insert(heap, 50);

 cout << "Initial Binomial Heap:" << endl;

printHeap(heap);

BinomialNode* nodeToDelete = findNode(heap, 30);

deleteNode(heap, nodeToDelete);

cout << "\nBinomial Heap after deleting 30:" << endl;

printHeap(heap);

return 0;

OUTPUT:-

c)

#include <iostream>

#include <climits>

using namespace std;

struct BinomialNode {

int key;

int degree;

BinomialNode* parent;

BinomialNode* child;

BinomialNode* sibling;

BinomialNode(int value) : key(value), degree(0), parent(NULL), child(NULL), sibling(NULL) {}

};

BinomialNode* mergeBinomialTrees(BinomialNode* b1, BinomialNode* b2) {

if (b1->key > b2->key) {

swap(b1, b2);

b2->parent = b1;

b2->sibling = b1->child;

b1->child = b2;

b1->degree++;

return b1;

BinomialNode* mergeBinomialHeaps(BinomialNode* h1, BinomialNode* h2) {

if (!h1) return h2;

if (!h2) return h1;

BinomialNode* res;

if (h1->degree <= h2->degree) {

res = h1;

h1 = h1->sibling;

} else {

res = h2;

h2 = h2->sibling;

BinomialNode* tail = res;

while (h1 && h2) {

if (h1->degree <= h2->degree) {

tail->sibling = h1;

h1 = h1->sibling;

} else {

tail->sibling = h2;
 h2 = h2->sibling;

tail = tail->sibling;

if (h1) tail->sibling = h1;

if (h2) tail->sibling = h2;

return res;

BinomialNode* unionBinomialHeaps(BinomialNode* h1, BinomialNode* h2) {

if (!h1 && !h2) return NULL;

BinomialNode* merged = mergeBinomialHeaps(h1, h2);

if (!merged) return NULL;

BinomialNode* prev = NULL;

BinomialNode* curr = merged;

BinomialNode* next = merged->sibling;

while (next) {

if ((curr->degree != next->degree) ||

(next->sibling && next->sibling->degree == curr->degree)) {

prev = curr;

curr = next;

} else {

if (curr->key <= next->key) {

curr->sibling = next->sibling;

curr = mergeBinomialTrees(curr, next);

} else {

if (prev) prev->sibling = next;

 else merged = next;

curr = mergeBinomialTrees(next, curr);

next = curr->sibling;

return merged;

BinomialNode* insertBinomialHeap(BinomialNode* head, int key) {

BinomialNode* newNode = new BinomialNode(key);

return unionBinomialHeaps(head, newNode);

bool searchInBinomialHeap(BinomialNode* head, int key) {

if (!head) return false;

if (head->key == key) return true;

return searchInBinomialHeap(head->child, key) || searchInBinomialHeap(head->sibling, key);

void printBinomialHeap(BinomialNode* head) {

while (head) {

cout << "B" << head->degree << " ";

BinomialNode* temp = head->child;

cout << "(Root: " << head->key << ") ";

while (temp) {

cout << temp->key << " ";

temp = temp->sibling;

cout << endl;

head = head->sibling;

}
int main() {

BinomialNode* head = NULL;

head = insertBinomialHeap(head, 10);

head = insertBinomialHeap(head, 20);

head = insertBinomialHeap(head, 30);

head = insertBinomialHeap(head, 40);

head = insertBinomialHeap(head, 50);

cout << "Binomial Heap:\n";

printBinomialHeap(head);

int key = 30;

if (searchInBinomialHeap(head, key)) {

cout << "Element " << key << " found in the heap.\n";

} else {

cout << "Element " << key << " not found in the heap.\n";

return 0;

OUTPUT:-

WEEK-7

Write a program to perform the following operations:

a) Insert an element into a AVL tree

b) Delete an element from a AVL search tree.
c) Search for a key element in a AVL search tree.

SOURCE CODE:-

a)
#include <iostream>

using namespace std;

struct AVLNode {

int key;

int height;

AVLNode* left;

AVLNode* right;

AVLNode(int value) : key(value), height(1), left(NULL), right(NULL) {}

};

int height(AVLNode* node) {

return node ? node->height : 0;

int getBalanceFactor(AVLNode* node) {

return node ? height(node->left) - height(node->right) : 0;

AVLNode* rightRotate(AVLNode* y) {

AVLNode* x = y->left;

AVLNode* T2 = x->right;

x->right = y;

y->left = T2;

y->height = max(height(y->left), height(y->right)) + 1;

x->height = max(height(x->left), height(x->right)) + 1;

return x;

AVLNode* leftRotate(AVLNode* x) {

AVLNode* y = x->right;

AVLNode* T2 = y->left;

y->left = x;

x->right = T2;
 x->height = max(height(x->left), height(x->right)) + 1;

y->height = max(height(y->left), height(y->right)) + 1;

return y;

AVLNode* insert(AVLNode* node, int key) {

if (!node) return new AVLNode(key);

if (key < node->key)

node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

else

return node;

node->height = 1 + max(height(node->left), height(node->right));

int balance = getBalanceFactor(node);

if (balance > 1 && key < node->left->key)

return rightRotate(node);

if (balance < -1 && key > node->right->key)

return leftRotate(node);

if (balance > 1 && key > node->left->key) {

node->left = leftRotate(node->left);

return rightRotate(node);

if (balance < -1 && key < node->right->key) {

node->right = rightRotate(node->right);

return leftRotate(node);

return node;

}
void inorder(AVLNode* root) {

if (root) {

inorder(root->left);

cout << root->key << " ";

inorder(root->right);

int main() {

AVLNode* root = NULL;

root = insert(root, 10);

root = insert(root, 20);

root = insert(root, 30);

root = insert(root, 40);

root = insert(root, 50);

root = insert(root, 25);

cout << "Inorder traversal of the AVL tree: ";

inorder(root);

cout << endl;

return 0;

OUTPUT:-

b)

#include <iostream>

using namespace std;

struct Node {

int key;

Node* left;
 Node* right;

int height;

Node(int value) : key(value), left(NULL), right(NULL), height(1) {}

};

int getHeight(Node* node) {

return node ? node->height : 0;

int getBalanceFactor(Node* node) {

if (!node) return 0;

return getHeight(node->left) - getHeight(node->right);

void updateHeight(Node* node) {

if (node) {

node->height = 1 + max(getHeight(node->left), getHeight(node->right));

Node* rotateRight(Node* y) {

Node* x = y->left;

Node* T2 = x->right;

x->right = y;

y->left = T2;

updateHeight(y);

updateHeight(x);

return x;

Node* rotateLeft(Node* x) {

Node* y = x->right;
 Node* T2 = y->left;

y->left = x;

x->right = T2;

updateHeight(x);

updateHeight(y);

return y;

Node* balanceNode(Node* node) {

int balance = getBalanceFactor(node);

if (balance > 1) {

if (getBalanceFactor(node->left) < 0) {

node->left = rotateLeft(node->left);

return rotateRight(node);

if (balance < -1) {

if (getBalanceFactor(node->right) > 0) {

node->right = rotateRight(node->right);

return rotateLeft(node);

return node;

Node* findMinNode(Node* node) {

Node* current = node;

while (current->left) {

current = current->left;
 }

return current;

Node* deleteNode(Node* root, int key) {

if (!root) {

return root;

if (key < root->key) {

root->left = deleteNode(root->left, key);

} else if (key > root->key) {

root->right = deleteNode(root->right, key);

} else {

if (!root->left || !root->right) {

Node* temp = root->left ? root->left : root->right;

delete root;

return temp;

Node* temp = findMinNode(root->right);

root->key = temp->key;

root->right = deleteNode(root->right, temp->key);

updateHeight(root);

return balanceNode(root);

Node* insertNode(Node* root, int key) {

if (!root) {

return new Node(key);

if (key < root->key) {

root->left = insertNode(root->left, key);

 } else if (key > root->key) {

root->right = insertNode(root->right, key);

} else {

return root;

updateHeight(root);

return balanceNode(root);

void inOrderTraversal(Node* root) {

if (root) {

inOrderTraversal(root->left);

cout << root->key << " ";

inOrderTraversal(root->right);

int main() {

Node* root = NULL;

root = insertNode(root, 10);

root = insertNode(root, 20);

root = insertNode(root, 30);

root = insertNode(root, 40);

root = insertNode(root, 50);

root = insertNode(root, 25);

cout << "In-order traversal of the AVL tree:\n";

inOrderTraversal(root);

cout << endl;

int keyToDelete = 20;

cout << "\nDeleting " << keyToDelete << "...\n";

root = deleteNode(root, keyToDelete);

cout << "In-order traversal after deletion:\n";

 inOrderTraversal(root);

cout << endl;

return 0;

OUTPUT:-

c)

#include <iostream>

using namespace std;

struct AVLNode {

int key;

AVLNode* left;

AVLNode* right;

int height;

AVLNode(int value) : key(value), left(NULL), right(NULL), height(1) {}

};

int getHeight(AVLNode* node) {

return node ? node->height : 0;

int getBalanceFactor(AVLNode* node) {

if (!node) return 0;

return getHeight(node->left) - getHeight(node->right);

AVLNode* rightRotate(AVLNode* y) {

AVLNode* x = y->left;
 AVLNode* T2 = x->right;

x->right = y;

y->left = T2;

y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

return x;

AVLNode* leftRotate(AVLNode* x) {

AVLNode* y = x->right;

AVLNode* T2 = y->left;

y->left = x;

x->right = T2;

x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

return y;

AVLNode* insert(AVLNode* node, int key) {

if (!node) return new AVLNode(key);

if (key < node->key) {

node->left = insert(node->left, key);

} else if (key > node->key) {

node->right = insert(node->right, key);

} else {

return node;

node->height = max(getHeight(node->left), getHeight(node->right)) + 1;

int balance = getBalanceFactor(node);

if (balance > 1 && key < node->left->key) {

 return rightRotate(node);

if (balance < -1 && key > node->right->key) {

return leftRotate(node);

if (balance > 1 && key > node->left->key) {

node->left = leftRotate(node->left);

return rightRotate(node);

if (balance < -1 && key < node->right->key) {

node->right = rightRotate(node->right);

return leftRotate(node);

return node;

bool search(AVLNode* root, int key) {

if (!root) return false;

if (key == root->key) {

return true;

} else if (key < root->key) {

return search(root->left, key);

} else {

return search(root->right, key);

void inorderTraversal(AVLNode* root) {

if (root) {

inorderTraversal(root->left);

cout << root->key << " ";

 inorderTraversal(root->right);

int main() {

AVLNode* root = NULL;

root = insert(root, 10);

root = insert(root, 20);

root = insert(root, 30);

root = insert(root, 40);

root = insert(root, 50);

root = insert(root, 25);

cout << "Inorder Traversal of the AVL Tree: ";

inorderTraversal(root);

cout << endl;

int keyToSearch = 25;

if (search(root, keyToSearch)) {

cout << "Element " << keyToSearch << " is found in the AVL tree.\n";

} else {

cout << "Element " << keyToSearch << " is not found in the AVL tree.\n";

keyToSearch = 15;

if (search(root, keyToSearch)) {

cout << "Element " << keyToSearch << " is found in the AVL tree.\n";

} else {

cout << "Element " << keyToSearch << " is not found in the AVL tree.\n";

return 0;

OUTPUT:-
WEEK-8

Write a program to perform the following operations:

a) Insert an element into a Red-Black tree

b) Delete an element from a Red-Black tree
c) Search for a key element in a Red-Black tree.

SOURCE CODE:-

a)

#include <iostream>

using namespace std;

enum Color { RED, BLACK };

struct Node {

int data;

bool color;

Node* left;

Node* right;

Node* parent;

Node(int data) : data(data), color(RED), left(NULL), right(NULL), parent(NULL) {}

};

class RedBlackTree {

private:

Node* root;

void rotateLeft(Node*& root, Node*& node) {

Node* nodeRight = node->right;

node->right = nodeRight->left;

if (nodeRight->left != NULL) {
 nodeRight->left->parent = node;

nodeRight->parent = node->parent;

if (node->parent == NULL) {

root = nodeRight;

} else if (node == node->parent->left) {

node->parent->left = nodeRight;

} else {

node->parent->right = nodeRight;

nodeRight->left = node;

node->parent = nodeRight;

void rotateRight(Node*& root, Node*& node) {

Node* nodeLeft = node->left;

node->left = nodeLeft->right;

if (nodeLeft->right != NULL) {

nodeLeft->right->parent = node;

nodeLeft->parent = node->parent;

if (node->parent == NULL) {

root = nodeLeft;

} else if (node == node->parent->left) {

node->parent->left = nodeLeft;

} else {
 node->parent->right = nodeLeft;

nodeLeft->right = node;

node->parent = nodeLeft;

void fixViolation(Node*& root, Node*& node) {

Node* parent = NULL;

Node* grandparent = NULL;

while ((node != root) && (node->color != BLACK) && (node->parent->color == RED)) {

parent = node->parent;

grandparent = parent->parent;

if (parent == grandparent->left) {

Node* uncle = grandparent->right;

if (uncle != NULL && uncle->color == RED) {

grandparent->color = RED;

parent->color = BLACK;

uncle->color = BLACK;

node = grandparent;

} else {

if (node == parent->right) {

rotateLeft(root, parent);

node = parent;

parent = node->parent;

rotateRight(root, grandparent);

swap(parent->color, grandparent->color);

node = parent;

}
 else {

Node* uncle = grandparent->left;

if (uncle != NULL && uncle->color == RED) {

grandparent->color = RED;

parent->color = BLACK;

uncle->color = BLACK;

node = grandparent;

} else {

if (node == parent->left) {

rotateRight(root, parent);

node = parent;

parent = node->parent;

rotateLeft(root, grandparent);

swap(parent->color, grandparent->color);

node = parent;

root->color = BLACK;

Node* insertBST(Node* root, Node* node) {

if (root == NULL) {

return node;

if (node->data < root->data) {

root->left = insertBST(root->left, node);

root->left->parent = root;

} else if (node->data > root->data) {

 root->right = insertBST(root->right, node);

root->right->parent = root;

return root;

void inorderHelper(Node* root) {

if (root == NULL) {

return;

inorderHelper(root->left);

cout << root->data << (root->color == RED ? " (R) " : " (B) ") << " ";

inorderHelper(root->right);

public:

RedBlackTree() : root(NULL) {}

void insert(const int& data) {

Node* node = new Node(data);

root = insertBST(root, node);

fixViolation(root, node);

void inorder() {

inorderHelper(root);

cout << endl;

};

int main() {

RedBlackTree tree;

tree.insert(10);
 tree.insert(20);

tree.insert(30);

tree.insert(15);

tree.insert(25);

cout << "Inorder Traversal of the Red-Black Tree:\n";

tree.inorder();

return 0;

OUTPUT:-

b)

#include <iostream>

using namespace std;

enum Color { RED, BLACK };

struct Node {

int data;

Color color;

Node* left, * right, * parent;

Node(int data) : data(data), color(RED), left(NULL), right(NULL), parent(NULL) {}

};

class RedBlackTree {

private:

Node* root;
Node* TNULL; // Sentinel node to represent null leaves

void initializeTNULL() {

TNULL = new Node(0);

TNULL->color = BLACK;

TNULL->left = NULL;

TNULL->right = NULL;

void leftRotate(Node* x) {

Node* y = x->right;

x->right = y->left;

if (y->left != TNULL)

y->left->parent = x;

y->parent = x->parent;

if (x->parent == NULL)

root = y;

else if (x == x->parent->left)

x->parent->left = y;

else

x->parent->right = y;

y->left = x;

x->parent = y;

void rightRotate(Node* x) {

Node* y = x->left;

x->left = y->right;

if (y->right != TNULL)

y->right->parent = x;

y->parent = x->parent;
 if (x->parent == NULL)

root = y;

else if (x == x->parent->right)

x->parent->right = y;

else

x->parent->left = y;

y->right = x;

x->parent = y;

void fixDelete(Node* x) {

Node* s;

while (x != root && x->color == BLACK) {

if (x == x->parent->left) {

s = x->parent->right;

if (s->color == RED) {

s->color = BLACK;

x->parent->color = RED;

leftRotate(x->parent);

s = x->parent->right;

if (s->left->color == BLACK && s->right->color == BLACK) {

s->color = RED;

x = x->parent;

} else {

if (s->right->color == BLACK) {

s->left->color = BLACK;

s->color = RED;

rightRotate(s);

s = x->parent->right;

}
 s->color = x->parent->color;

x->parent->color = BLACK;

s->right->color = BLACK;

leftRotate(x->parent);

x = root;

} else {

s = x->parent->left;

if (s->color == RED) {

s->color = BLACK;

x->parent->color = RED;

rightRotate(x->parent);

s = x->parent->left;

if (s->left->color == BLACK && s->right->color == BLACK) {

s->color = RED;

x = x->parent;

} else {

if (s->left->color == BLACK) {

s->right->color = BLACK;

s->color = RED;

leftRotate(s);

s = x->parent->left;

s->color = x->parent->color;

x->parent->color = BLACK;

s->left->color = BLACK;

rightRotate(x->parent);

x = root;

}
 }

x->color = BLACK;

void rbTransplant(Node* u, Node* v) {

if (u->parent == NULL)

root = v;

else if (u == u->parent->left)

u->parent->left = v;

else

u->parent->right = v;

v->parent = u->parent;

Node* minimum(Node* node) {

while (node->left != TNULL)

node = node->left;

return node;

void deleteNodeHelper(Node* node, int key) {

Node* z = TNULL;

Node* x, * y;

while (node != TNULL) {

if (node->data == key)

z = node;

if (node->data <= key)

node = node->right;

else

node = node->left;

}
if (z == TNULL) {

cout << "Key not found in the tree\n";

return;

y = z;

Color y_original_color = y->color;

if (z->left == TNULL) {

x = z->right;

rbTransplant(z, z->right);

} else if (z->right == TNULL) {

x = z->left;

rbTransplant(z, z->left);

} else {

y = minimum(z->right);

y_original_color = y->color;

x = y->right;

if (y->parent == z)

x->parent = y;

else {

rbTransplant(y, y->right);

y->right = z->right;

y->right->parent = y;

rbTransplant(z, y);

y->left = z->left;

y->left->parent = y;

y->color = z->color;

delete z;

if (y_original_color == BLACK)
 fixDelete(x);

void printHelper(Node* root, string indent, bool last) {

if (root != TNULL) {

cout << indent;

if (last) {

cout << "R----";

indent += " ";

} else {

cout << "L----";

indent += "| ";

string sColor = root->color == RED ? "RED" : "BLACK";

cout << root->data << "(" << sColor << ")" << endl;

printHelper(root->left, indent, false);

printHelper(root->right, indent, true);

public:

RedBlackTree() {

initializeTNULL();

root = TNULL;

void deleteNode(int data) {

deleteNodeHelper(root, data);

void insert(int key) {

Node* node = new Node(key);

node->parent = NULL;

node->data = key;

node->left = TNULL;

node->right = TNULL;

node->color = RED;

Node* y = NULL;

Node* x = root;

while (x != TNULL) {

y = x;

if (node->data < x->data)

x = x->left;

else

x = x->right;

node->parent = y;

if (y == NULL)

root = node;

else if (node->data < y->data)

y->left = node;

else

y->right = node;

if (node->parent == NULL) {

node->color = BLACK;

return;

if (node->parent->parent == NULL)
 return;

fixInsert(node);

void printTree() {

if (root) printHelper(root, "", true);

void fixInsert(Node* k) {

Node* u;

while (k->parent->color == RED) {

if (k->parent == k->parent->parent->right) {

u = k->parent->parent->left;

if (u->color == RED) {

u->color = BLACK;

k->parent->color = BLACK;

k->parent->parent->color = RED;

k = k->parent->parent;

} else {

if (k == k->parent->left) {

k = k->parent;

rightRotate(k);

k->parent->color = BLACK;

k->parent->parent->color = RED;

leftRotate(k->parent->parent);

} else {

u = k->parent->parent->right;
 if (u->color == RED) {

u->color = BLACK;

k->parent->color = BLACK;

k->parent->parent->color = RED;

k = k->parent->parent;

} else {

if (k == k->parent->right) {

k = k->parent;

leftRotate(k);

k->parent->color = BLACK;

k->parent->parent->color = RED;

rightRotate(k->parent->parent);

if (k == root) break;

root->color = BLACK;

};

int main() {

RedBlackTree rbt;

rbt.insert(10);

rbt.insert(20);

rbt.insert(30);

rbt.insert(40);

rbt.insert(50);

cout << "Red-Black Tree after insertion:\n";

rbt.printTree();
 cout << "\nDeleting 30...\n";

rbt.deleteNode(30);

rbt.printTree();

cout << "\nDeleting 10...\n";

rbt.deleteNode(10);

rbt.printTree();

return 0;

OUTPUT:-

c)

#include <iostream>

using namespace std;

enum Color { RED, BLACK };

struct RBTreeNode {
 int key;

Color color;

RBTreeNode* left;

RBTreeNode* right;

RBTreeNode* parent;

RBTreeNode(int val) : key(val), color(RED), left(NULL), right(NULL), parent(NULL) {}

};

class RBTree {

private:

RBTreeNode* root;

RBTreeNode* TNULL;

void fixInsert(RBTreeNode* k);

void leftRotate(RBTreeNode* x);

void rightRotate(RBTreeNode* x);

public:

RBTree();

~RBTree();

void insert(int key);

bool search(int key);

void inOrderTraversal(RBTreeNode* node);

RBTreeNode* getRoot() { return root; }

};

RBTree::RBTree() {

TNULL = new RBTreeNode(0);

TNULL->color = BLACK;

root = TNULL;

RBTree::~RBTree() {

delete TNULL;

}
void RBTree::leftRotate(RBTreeNode* x) {

RBTreeNode* y = x->right;

x->right = y->left;

if (y->left != TNULL) {

y->left->parent = x;

y->parent = x->parent;

if (x->parent == NULL) {

root = y;

} else if (x == x->parent->left) {

x->parent->left = y;

} else {

x->parent->right = y;

y->left = x;

x->parent = y;

void RBTree::rightRotate(RBTreeNode* x) {

RBTreeNode* y = x->left;

x->left = y->right;

if (y->right != TNULL) {

y->right->parent = x;

y->parent = x->parent;

if (x->parent == NULL) {

root = y;

} else if (x == x->parent->left) {

x->parent->left = y;

} else {

x->parent->right = y;

}
 y->right = x;

x->parent = y;

void RBTree::fixInsert(RBTreeNode* k) {

RBTreeNode* u;

while (k->parent->color == RED) {

if (k->parent == k->parent->parent->right) {

u = k->parent->parent->left;

if (u->color == RED) {

u->color = BLACK;

k->parent->color = BLACK;

k->parent->parent->color = RED;

k = k->parent->parent;

} else {

if (k == k->parent->left) {

k = k->parent;

rightRotate(k);

k->parent->color = BLACK;

k->parent->parent->color = RED;

leftRotate(k->parent->parent);

} else {

u = k->parent->parent->right;

if (u->color == RED) {

u->color = BLACK;

k->parent->color = BLACK;

k->parent->parent->color = RED;

k = k->parent->parent;

} else {
 if (k == k->parent->right) {

k = k->parent;

leftRotate(k);

k->parent->color = BLACK;

k->parent->parent->color = RED;

rightRotate(k->parent->parent);

if (k == root) {

break;

root->color = BLACK;

void RBTree::insert(int key) {

RBTreeNode* node = new RBTreeNode(key);

node->parent = NULL;

node->key = key;

node->left = TNULL;

node->right = TNULL;

node->color = RED;

RBTreeNode* y = NULL;

RBTreeNode* x = root;

while (x != TNULL) {

y = x;

if (node->key < x->key) {

x = x->left;

} else {
 x = x->right;

node->parent = y;

if (y == NULL) {

root = node;

} else if (node->key < y->key) {

y->left = node;

} else {

y->right = node;

if (node->parent == NULL) {

node->color = BLACK;

return;

if (node->parent->parent == NULL) {

return;

fixInsert(node);

bool RBTree::search(int key) {

RBTreeNode* current = root;

while (current != TNULL) {

if (key == current->key) {

return true;

} else if (key < current->key) {

current = current->left;

} else {

current = current->right;

}
 }

return false;

void RBTree::inOrderTraversal(RBTreeNode* node) {

if (node != TNULL) {

inOrderTraversal(node->left);

cout << node->key << " ";

inOrderTraversal(node->right);

int main() {

RBTree tree;

tree.insert(10);

tree.insert(20);

tree.insert(30);

tree.insert(40);

tree.insert(50);

tree.insert(25);

int key = 30;

if (tree.search(key)) {

cout << "Element " << key << " found in the Red-Black Tree.\n";

} else {

cout << "Element " << key << " not found in the Red-Black Tree.\n";

cout << "In-order traversal: ";

tree.inOrderTraversal(tree.getRoot());

cout << endl;

return 0;

}
OUTPUT:-

WEEK-9

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

SOURCE CODE:-

#include <iostream>

#include <cstring>

#include <cstdlib>

using namespace std;

// Linked List node

struct Node {

char* key;

char* value;

Node* next;

};

// Hash Map structure

struct HashMap {

int numOfElements, capacity;

Node** arr;

};

// Function to initialize the hash map

void initializeHashMap(HashMap* mp) {

mp->capacity = 100;

mp->numOfElements = 0;
 mp->arr = (Node**)malloc(sizeof(Node*) * mp->capacity);

for (int i = 0; i < mp->capacity; i++) {

mp->arr[i] = NULL;

// Hash function to compute the index

int hashFunction(HashMap* mp, char* key) {

int bucketIndex;

int sum = 0, factor = 31;

for (int i = 0; i < strlen(key); i++) {

sum = ((sum % mp->capacity) + (((int)key[i]) * factor) % mp->capacity) % mp->capacity;

factor = ((factor % 32767) * (31 % 32767)) % 32767;

bucketIndex = sum;

return bucketIndex;

// Function to set values for a node

void setNode(Node* node, char* key, char* value) {

node->key = strdup(key); // Duplicate the key string

node->value = strdup(value); // Duplicate the value string

node->next = NULL;

// Function to insert a key-value pair into the hash map

void insert(HashMap* mp, char* key, char* value) {

int bucketIndex = hashFunction(mp, key);

Node* newNode = (Node*)malloc(sizeof(Node));

setNode(newNode, key, value);

 if (mp->arr[bucketIndex] == NULL) {

mp->arr[bucketIndex] = newNode;

} else {

newNode->next = mp->arr[bucketIndex];

mp->arr[bucketIndex] = newNode;

mp->numOfElements++;

// Function to delete a key from the hash map

void deleteKey(HashMap* mp, char* key) {

int bucketIndex = hashFunction(mp, key);

Node* prevNode = NULL;

Node* currNode = mp->arr[bucketIndex];

while (currNode != NULL) {

if (strcmp(currNode->key, key) == 0) {

if (prevNode == NULL) {

mp->arr[bucketIndex] = currNode->next;

} else {

prevNode->next = currNode->next;

free(currNode->key);

free(currNode->value);

free(currNode);

mp->numOfElements--;

break;

prevNode = currNode;

currNode = currNode->next;

}
}

// Function to search for a key in the hash map

char* search(HashMap* mp, char* key) {

int bucketIndex = hashFunction(mp, key);

Node* bucketHead = mp->arr[bucketIndex];

while (bucketHead != NULL) {

if (strcmp(bucketHead->key, key) == 0) {

return bucketHead->value;

bucketHead = bucketHead->next;

char* errorMsg = (char*)malloc(sizeof(char) * 25);

strcpy(errorMsg, "Oops! No data found.\n");

return errorMsg;

// Function to print all elements (for debugging purposes)

void printHashMap(HashMap* mp) {

for (int i = 0; i < mp->capacity; i++) {

Node* node = mp->arr[i];

while (node != NULL) {

cout << "Key: " << node->key << ", Value: " << node->value << endl;

node = node->next;

int main() {

HashMap* mp = (HashMap*)malloc(sizeof(HashMap));
initializeHashMap(mp);

insert(mp, "Yogaholic", "Anjali");

insert(mp, "pluto14", "Vartika");

insert(mp, "elite_Programmer", "Manish");

insert(mp, "GFG", "GeeksforGeeks");

insert(mp, "decentBoy", "Mayank");

cout << search(mp, "elite_Programmer") << endl;

cout << search(mp, "Yogaholic") << endl;

cout << search(mp, "pluto14") << endl;

cout << search(mp, "decentBoy") << endl;

cout << search(mp, "GFG") << endl;

cout << search(mp, "randomKey") << endl;

cout << "\nAfter deletion:\n";

deleteKey(mp, "decentBoy");

cout << search(mp, "decentBoy") << endl;

// Free memory allocated for hash map

for (int i = 0; i < mp->capacity; i++) {

Node* node = mp->arr[i];

while (node != NULL) {

Node* temp = node;

node = node->next;

free(temp->key);

free(temp->value);

free(temp);

}
 free(mp->arr);

free(mp);

return 0;

OUTPUT:-

Write a program for implementing Knuth-Morris-Pratt pattern matching algorithm.

SOURCE CODE:-

#include <bits/stdc++.h>

void computeLPSArray(char* pat, int M, int* lps);

// Prints occurrences of pat[] in txt[]

void KMPSearch(char* pat, char* txt)

int M = strlen(pat);

int N = strlen(txt);

// create lps[] that will hold the longest prefix suffix

// values for pattern

int lps[M];
 // Preprocess the pattern (calculate lps[] array)

computeLPSArray(pat, M, lps);

int i = 0; // index for txt[]

int j = 0; // index for pat[]

while ((N - i) >= (M - j)) {

if (pat[j] == txt[i]) {

j++;

i++;

if (j == M) {

printf("Found pattern at index %d ", i - j);

j = lps[j - 1];

// mismatch after j matches

else if (i < N && pat[j] != txt[i]) {

// Do not match lps[0..lps[j-1]] characters,

// they will match anyway

if (j != 0)

j = lps[j - 1];

else

i = i + 1;

// Fills lps[] for given pattern pat[0..M-1]

void computeLPSArray(char* pat, int M, int* lps)

{
// length of the previous longest prefix suffix

int len = 0;

lps[0] = 0; // lps[0] is always 0

// the loop calculates lps[i] for i = 1 to M-1

int i = 1;

while (i < M) {

if (pat[i] == pat[len]) {

len++;

lps[i] = len;

i++;

else // (pat[i] != pat[len])

// This is tricky. Consider the example.

// AAACAAAA and i = 7. The idea is similar

// to search step.

if (len != 0) {

len = lps[len - 1];

// Also, note that we do not increment

// i here

else // if (len == 0)

lps[i] = 0;

i++;

}
}

// Driver code

int main()

char txt[] = "ABABDABACDABABCABAB";

char pat[] = "ABABCABAB";

KMPSearch(pat, txt);

return 0;

OUTPUT:-

WEEK-10

Write a program for implementing Brute force pattern matching algorithm.

SOURCE CODE:-

#include <iostream>

#include <string>

using namespace std;

// Function to perform Brute Force pattern matching

void bruteForcePatternMatching(string text, string pattern) {

int n = text.length();

int m = pattern.length();

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

int j;

for (j = 0; j < m; j++) {

if (text[i + j] != pattern[j]) {

break;

}
 }

if (j == m) {

cout << "Pattern found at index " << i << endl;

int main() {

string text = "ABABDABACDABABCABAB";

string pattern = "ABABCABAB";

cout << "Text: " << text << endl;

cout << "Pattern: " << pattern << endl;

bruteForcePatternMatching(text, pattern);

return 0;

OUTPUT:-

Write a program for implementing Boyer pattern matching algorithm.

SOURCE CODE:-

#include <bits/stdc++.h>

using namespace std;

# define NO_OF_CHARS 256

void badCharHeuristic( string str, int size,

int badchar[NO_OF_CHARS])
{

int i;

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

badchar[i] = -1;

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

badchar[(int) str[i]] = i;

void search( string txt, string pat)

int m = pat.size();

int n = txt.size();

int badchar[NO_OF_CHARS];

badCharHeuristic(pat, m, badchar);

int s = 0;

while(s <= (n - m))

int j = m - 1;

while(j >= 0 && pat[j] == txt[s + j])

j--;

if (j < 0)

cout << "pattern occurs at shift = " << s << endl;

s += (s + m < n)? m-badchar[txt[s + m]] : 1;

else

s += max(1, j - badchar[txt[s + j]]);

}
}

int main()

string txt= "ABAAABCD";

string pat = "ABC";

search(txt, pat);

return 0;

OUTPUT:-