Advanced Data

structures Lab
(Manual)
[Link] CSE/CS I Year I sem
Prerequisites:
1. A course on Computer
Programming & Data
Structures
Course Objectives:
1. Introduces the basic
concepts of Abstract Data
Types.
2. Reviews basic data
structures such as stacks and
queues.
3. Introduces a variety of data
structures such as hash tables,
search trees, tries, heaps,
graphs,and
B-trees.
4. Introduces sorting and
pattern matching algorithms.
Course Outcomes:
1. Ability to select the data
structures that efficiently
model the information in a
problem.
2. Ability to assess
efficiency trade-offs among
different data structure
implementations or
combinations.
3. Implement and know the
application of algorithms for
sorting and pattern matching.
4. Design programs using
a variety of data
structures, including hash
tables, binary and
generaltree structures, search
trees, tries, heaps, graphs, and
B-trees.
Advanced Data structures Lab (Manual)
[Link] CSE/CS I Year I Sem(R22)
Prerequisites:
1. A course on Computer Programming & Data Structures.

Course Objectives:
1. Introduces the basic concepts of Abstract Data Types.
2. Reviews basic data structures such as stacks and queues.
3. Introduces a variety of data structures such as hash tables, search trees, tries, heaps,
graphs, and
4. B-trees.
5. Introduces sorting and pattern matching algorithms.
Course Outcomes:
1. Ability to select the data structures that efficiently model the information in a
problem.
2. Ability to assess efficiency trade-offs among different data structure
implementations or combinations.
3. Implement and know the application of algorithms for sorting and pattern matching.
4. Design programs using a variety of data structures, including hash tables,
binary and
5. General tree structures, search trees, tries, heaps, graphs, and B-trees.

List of Programs
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.
2. Write a program for implementing the following sorting methods:
a) Merge sort b) Heap sort c) Quick sort
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.
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
5. Write a program to perform the following operations:
a) Insert an element into a Lefiist tree
b) Delete an element from a Leftist tree
c) Search for a key element in a Leftist tree
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
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.

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.

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

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

11. Write a program for implementing Brute Force pattern matching algorithm.

12. Write a program for implementing Boyer pattern matching algorithm.

Experiments

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.
class Node {
int key;
Node left, right;
public Node(int item) {
 key = item;
left = right = null;
}
}
public class BinarySearchTree {
private Node root;
public BinarySearchTree() {
root = null;
}
// Insert a key into the BST
public void insert(int key) {
root = insertRec(root, key);
}
private Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < [Link]) {
[Link] = insertRec([Link], key);
} else if (key > [Link]) {
[Link] = insertRec([Link], key);
}
return root;
}
// Delete a key from the BST
public void delete(int key) {
root = deleteRec(root, key);
}
private Node deleteRec(Node root, int key) {
 if (root == null) {
return root;
}
if (key < [Link]) {
[Link] = deleteRec([Link], key);
} else if (key > [Link]) {
[Link] = deleteRec([Link], key);
} else {
// Node with only one child or no child
if ([Link] == null) {
return [Link];
} else if ([Link] == null) {
return [Link];
}
// Node with two children, get the inorder successor (smallest in the right subtree)
[Link] = minValue([Link]);
// Delete the inorder successor
[Link] = deleteRec([Link], [Link]);
}
return root;
}
private int minValue(Node root) {
int minValue = [Link];
while ([Link] != null) {
minValue = [Link];
root = [Link];
}
return minValue;
}
// Search for a key in the BST
 public boolean search(int key) {
return searchRec(root, key);
}
private boolean searchRec(Node root, int key) {
if (root == null || [Link] == key) {
return root != null;
}
if (key < [Link]) {
return searchRec([Link], key);
} else {
return searchRec([Link], key);
}
}
// Driver method to test the above functions
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Insert
[Link](50);
[Link](30);
[Link](20);
[Link](40);
[Link](70);
[Link](60);
[Link](80);
// Search
[Link]("Is 40 present in BST? " + [Link](40));
[Link]("Is 90 present in BST? " + [Link](90));
// Delete
[Link](20);
[Link]("Is 20 present in BST after deletion? " + [Link](20));
 }
}

Output:

Is 40 present in BST? true

Is 90 present in BST? false
Is 20 present in BST after deletion? False

2. Write a program for implementing the following sorting methods:

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

2a) Merge Sort

public class MergeSort {

public static void mergeSort(int[] arr) {

if (arr == null || [Link] <= 1) {
return; // Already sorted
}
 int n = [Link];
int[] temp = new int[n];
mergeSort(arr, temp, 0, n - 1);
}
private static void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
// Copy data to temporary arrays
[Link](arr, left, temp, left, right - left + 1);
int i = left;
int j = mid + 1;
int k = left;
// Merge the two halves
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
 // Copy the remaining elements of left subarray, if any
while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}
// Copy the remaining elements of right subarray, if any
while (j <= right) {
arr[k] = temp[j];
j++;
k++;
}
}
public static void printArray(int[] arr) {
for (int num : arr) {
[Link](num + " ");
}
[Link]();
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};

[Link]("Original array:");
printArray(arr);
mergeSort(arr);
[Link]("\nSorted array:");
printArray(arr);
}
}

Output:
Original array:
12 11 13 5 6 7

Sorted array:
5 6 7 11 12 13

2 b) HeapSort
public class HeapSort {
public void heapSort(int[] arr) {
int n = [Link];
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from the heap
for (int i = n - 1; i > 0; i--) {
// Move current root to the end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is an index in arr[]
private void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
 // If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
public void printArray(int[] arr) {
for (int num : arr) {
[Link](num + " ");
}
[Link]();
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
[Link]("Original array:");
new HeapSort().printArray(arr);
new HeapSort().heapSort(arr);
[Link]("\nSorted array:");
new HeapSort().printArray(arr);
 }
}

Output:
Original array:
12 11 13 5 6 7

Sorted array:
5 6 7 11 12 13

2 c) Quick sort
public class QuickSort {
public void quickSort(int[] arr) {
if (arr == null || [Link] == 0) {
return;
}
int length = [Link];
quickSort(arr, 0, length - 1);
}
private void quickSort(int[] arr, int low, int high) {
if (low < high) {
int partitionIndex = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
 // If the current element is smaller than or equal to the pivot
if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public void printArray(int[] arr) {
for (int num : arr) {
[Link](num + " ");
}
[Link]();
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
[Link]("Original array:");
new QuickSort().printArray(arr);
new QuickSort().quickSort(arr);
[Link]("\nSorted array:");
new QuickSort().printArray(arr);
}
}
Output:
Original array:
12 11 13 5 6 7

Sorted array:
5 6 7 11 12 13

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.

class BTreeNode {
int[] keys;
BTreeNode[] children;
int numKeys;
boolean isLeaf;
 public BTreeNode(int t, boolean isLeaf) {
[Link] = new int[2 * t - 1];
[Link] = new BTreeNode[2 * t];
[Link] = 0;
[Link] = isLeaf;
}
}
class BTree {
private BTreeNode root;
private int t; // Minimum degree
public BTree(int t) {
[Link] = null;
this.t = t;
}
public void insert(int key) {
if (root == null) {
root = new BTreeNode(t, true);
[Link][0] = key;
[Link] = 1;
} else {
if ([Link] == 2 * t - 1) {
BTreeNode newRoot = new BTreeNode(t, false);
[Link][0] = root;
splitChild(newRoot, 0);
insertNonFull(newRoot, key);
root = newRoot;
} else {
insertNonFull(root, key);
}
}
}
private void insertNonFull(BTreeNode x, int key) {
int i = [Link] - 1;
if ([Link]) {
while (i >= 0 && key < [Link][i]) {
[Link][i + 1] = [Link][i];
i--;
}
[Link][i + 1] = key;
[Link]++;
} else {
while (i >= 0 && key < [Link][i]) {
i--;
}
i++;
if ([Link][i].numKeys == 2 * t - 1) {
splitChild(x, i);
if (key > [Link][i]) {
i++;
}
}
insertNonFull([Link][i], key);
}
}
private void splitChild(BTreeNode x, int i) {
BTreeNode y = [Link][i];
BTreeNode z = new BTreeNode(t, [Link]);
[Link][[Link] + 1] = [Link][[Link]];
for (int j = [Link] - 1; j >= i; j--) {
[Link][j + 1] = [Link][j];
 }
[Link][i] = [Link][t - 1];
[Link]++;
for (int j = 0; j < t - 1; j++) {
[Link][j] = [Link][j + t];
}
if (![Link]) {
for (int j = 0; j < t; j++) {
[Link][j] = [Link][j + t];
}
}
[Link] = t - 1;
[Link] = t - 1;
[Link][i + 1] = z;
}
public void delete(int key) {
if (root != null) {
delete(root, key);
}
}
private void delete(BTreeNode x, int key) {
int i = 0;
while (i < [Link] && key > [Link][i]) {
i++;
}
if (i < [Link] && key == [Link][i]) {
deleteKey(x, i);
} else {
if ([Link]) {
[Link]("Key " + key + " not found in the B-tree");
 return;
}
if ([Link][i].numKeys < t) {
fill(x, i);
}
if (i < [Link] && key > [Link][i]) {
i++;
}
delete([Link][i], key);
}
}
private void deleteKey(BTreeNode x, int index) {
if ([Link]) {
for (int i = index + 1; i < [Link]; i++) {
[Link][i - 1] = [Link][i];
}
[Link]--;
} else {
BTreeNode y = [Link][index];
BTreeNode z = [Link][index + 1];
if ([Link] >= t) {
int pred = getPredecessor(y);
delete(y, pred);
[Link][index] = pred;
} else if ([Link] >= t) {
int succ = getSuccessor(z);
delete(z, succ);
[Link][index] = succ;
} else {
merge(x, index);
 delete(y, index);
}
}
}
private int getPredecessor(BTreeNode x) {
while (![Link]) {
x = [Link][[Link]];
}
return [Link][[Link] - 1];
}
private int getSuccessor(BTreeNode x) {
while (![Link]) {
x = [Link][0];
}
return [Link][0];
}
private void fill(BTreeNode x, int index) {
if (index > 0 && [Link][index - 1].numKeys >= t) {
borrowFromPrev(x, index);
} else if (index < [Link] && [Link][index + 1].numKeys >= t) {
borrowFromNext(x, index);
} else {
if (index < [Link]) {
merge(x, index);
} else {
merge(x, index - 1);
}
}
}
private void borrowFromPrev(BTreeNode x, int index) {
 BTreeNode child = [Link][index];
BTreeNode sibling = [Link][index - 1];
for (int i = [Link] - 1; i >= 0; i--) {
[Link][i + 1] = [Link][i];
}
if (![Link]) {
for (int i = [Link]; i >= 0; i--) {
[Link][i + 1] = [Link][i];
}
}
[Link][0] = [Link][index - 1];
if (![Link][index - 1].isLeaf) {
[Link][0] = [Link][[Link]];
}
[Link][index - 1] = [Link][[Link] - 1];
[Link]++;
[Link]--;
}
private void borrowFromNext(BTreeNode x, int index) {
BTreeNode child = [Link][index];
BTreeNode sibling = [Link][index + 1];
[Link][[Link]] = [Link][index];
if (![Link]) {
[Link][[Link] + 1] = [Link][0];
}
[Link][index] = [Link][0];
for (int i = 1; i < [Link]; i++) {
[Link][i - 1] = [Link][i];
}
if (![Link]) {
 for (int i = 1; i <= [Link]; i++) {
[Link][i - 1] = [Link][i];
}
}
[Link]++;
[Link]--;
}
private void merge(BTreeNode x, int index) {
BTreeNode child = [Link][index];
BTreeNode sibling = [Link][index + 1];
[Link][t - 1] = [Link][index];
for (int i = 0; i < [Link]; i++) {
[Link][i + t] = [Link][i];
}
if (![Link]) {
for (int i = 0; i <= [Link]; i++) {
[Link][i + t] = [Link][i];
}
}
for (int i = index + 1; i < [Link]; i++) {
[Link][i - 1] = [Link][i];
}
for (int i = index + 2; i <= [Link]; i++) {
[Link][i - 1] = [Link][i];
}
[Link] += [Link] + 1;
[Link]--;
// Free the memory occupied by sibling
sibling = null;
}
 public boolean search(int key) {
return search(root, key);
}
private boolean search(BTreeNode x, int key) {
int i = 0;
while (i < [Link] && key > [Link][i]) {
i++;
}
if (i < [Link] && key == [Link][i]) {
return true;
} else if ([Link]) {
return false;
} else {
return search([Link][i], key);
}
}
public static void main(String[] args) {
BTree bTree = new BTree(3);
[Link](1);
[Link](3);
[Link](7);
[Link](10);
[Link](11);
[Link](13);
[Link](14);
[Link](15);
[Link](18);
[Link](16);
[Link](19);
[Link](24);
 [Link](25);
[Link](26);
[Link](21);
[Link](4);
[Link](5);
[Link](20);
[Link](22);
[Link](2);
[Link](17);
[Link](12);
[Link](6);
[Link]("B-tree after insertion:");
// Display the tree structure or traverse it as needed
int keyToSearch = 6;
if ([Link](keyToSearch)) {
[Link]("Key " + keyToSearch + " found in the B-tree");
} else {
[Link]("Key " + keyToSearch + " not found in the B-tree");
}
int keyToDelete = 13;
[Link](keyToDelete);
[Link]("\nB-tree after deletion of key " + keyToDelete + ":");
// Display the tree structure or traverse it as needed
}
}

Output:
B-tree after insertion:
Key 6 found in the B-tree
B-tree after deletion of key 13:
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

import [Link];
public class MinMaxHeap {
private int[] heap;
private int size;
private static final int INITIAL_CAPACITY = 10;
 public MinMaxHeap() {
[Link] = new int[INITIAL_CAPACITY];
[Link] = 0;
}
public void insert(int value) {
if (size == [Link] - 1) {
resize();
}
size++;
heap[size] = value;
if (size > 1) {
trickleUp(size);
}
}
public void delete(int value) {
if (size == 0) {
[Link]("Heap is empty. Cannot delete.");
return;
}
int index = findIndex(value);
if (index == -1) {
[Link]("Value not found in the heap. Cannot delete.");
return;
}
heap[index] = heap[size];
size--;
if (index > 2 && index % 2 == 0) {
// Even level node (Max level), check for Max violations
if (heap[index] < heap[index / 2]) {
swap(index, index / 2);
 trickleDownMax(index / 2);
} else {
trickleUpMin(index);
}
} else {
// Odd level node (Min level), check for Min violations
trickleDownMin(index);
}
}
public boolean search(int value) {
return findIndex(value) != -1;
}
private int findIndex(int value) {
for (int i = 1; i <= size; i++) {
if (heap[i] == value) {
return i;
}
}
return -1;
}
private void resize() {
int newCapacity = [Link] * 2;
heap = [Link](heap, newCapacity);
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
private void trickleUp(int index) {
 if (index % 2 == 0) {
trickleUpMax(index);
} else {
trickleUpMin(index);
}
}
private void trickleUpMin(int index) {
int parent = index / 2;
if (parent > 0 && heap[index] > heap[parent]) {
swap(index, parent);
trickleUpMin(parent);
}
}
private void trickleUpMax(int index) {
int grandParent = index / 4;
if (grandParent > 0 && heap[index] < heap[grandParent]) {
swap(index, grandParent);
trickleUpMax(grandParent);
}
}
private void trickleDownMin(int index) {
int minChildIndex = findMinChildIndex(index);
if (minChildIndex != -1 && heap[index] > heap[minChildIndex]) {
swap(index, minChildIndex);
if (minChildIndex <= size / 2) {
trickleDownMin(minChildIndex);
}
}
}
private void trickleDownMax(int index) {
int maxChildIndex = findMaxChildIndex(index);
if (maxChildIndex != -1 && heap[index] < heap[maxChildIndex]) {
swap(index, maxChildIndex);
if (maxChildIndex <= size / 2) {
trickleDownMax(maxChildIndex);
}
}
}
private int findMinChildIndex(int index) {
int leftChild = index * 2;
int rightChild = index * 2 + 1;
if (rightChild <= size) {
return (heap[leftChild] < heap[rightChild]) ? leftChild : rightChild;
} else if (leftChild <= size) {
return leftChild;
} else {
return -1;
}
}
private int findMaxChildIndex(int index) {
int leftChild = index * 2;
int rightChild = index * 2 + 1;
if (rightChild <= size) {
return (heap[leftChild] > heap[rightChild]) ? leftChild : rightChild;
} else if (leftChild <= size) {
return leftChild;
} else {
return -1;
}
}
 public void printHeap() {
for (int i = 1; i <= size; i++) {
[Link](heap[i] + " ");
}
[Link]();
}
public static void main(String[] args) {
MinMaxHeap minMaxHeap = new MinMaxHeap();
[Link](10);
[Link](8);
[Link](7);
[Link](5);
[Link](3);
[Link](15);
[Link]("Min-Max Heap after insertions:");
[Link]();
int keyToSearch = 7;
if ([Link](keyToSearch)) {
[Link]("Key " + keyToSearch + " found in the Min-Max Heap");
} else {
[Link]("Key " + keyToSearch + " not found in the Min-Max Heap");
}
int keyToDelete = 8;
[Link](keyToDelete);
[Link]("\nMin-Max Heap after deletion of key " + keyToDelete + ":");
[Link]();
}
}

Output:
Min-Max Heap after insertions:
10 8 15 5 3 7
Key 7 found in the Min-Max Heap

Min-Max Heap after deletion of key 8:

10 7 15 5 3

5. Write a program to perform the following operations:

a) Insert an element into a Lefiist tree
b) Delete an element from a Leftist tree
c) Search for a key element in a Leftist tree

class LeftistNode {
int key;
int rank;
LeftistNode left;
LeftistNode right;
public LeftistNode(int key) {
[Link] = key;
[Link] = 1; // Initial rank for a new node is 1
[Link] = null;
[Link] = null;
}
}
public class LeftistTree {
private LeftistNode root;
public LeftistTree() {
[Link] = null;
}
// Operation to insert an element into a Leftist tree
public void insert(int key) {
LeftistNode newNode = new LeftistNode(key);
root = merge(root, newNode);
}
// Operation to delete an element from a Leftist tree
public void delete(int key) {
if (search(root, key)) {
root = delete(root, key);
[Link]("Element " + key + " deleted from the Leftist tree.");
} else {
[Link]("Element " + key + " not found in the Leftist tree.");
}
}
// Operation to search for a key element in a Leftist tree
public boolean search(int key) {
return search(root, key);
}
 // Helper method to search for a key element in a Leftist tree
private boolean search(LeftistNode node, int key) {
if (node == null) {
return false;
} else if (key == [Link]) {
return true;
} else {
return search([Link], key) || search([Link], key);
}
}
// Helper method to merge two Leftist trees
private LeftistNode merge(LeftistNode a, LeftistNode b) {
if (a == null) {
return b;
} else if (b == null) {
return a;
}
if ([Link] > [Link]) {
LeftistNode temp = a;
a = b;
b = temp;
}
[Link] = merge([Link], b);
if ([Link] == null || [Link] < [Link]) {
LeftistNode temp = [Link];
[Link] = [Link];
[Link] = temp;
}
if ([Link] == null) {
[Link] = 1;
 } else {
[Link] = [Link] + 1;
}
return a;
}
// Helper method to delete a key element from a Leftist tree
private LeftistNode delete(LeftistNode node, int key) {
if (node == null) {
return null;
}
if (key < [Link]) {
[Link] = delete([Link], key);
} else if (key > [Link]) {
[Link] = delete([Link], key);
} else {
node = merge([Link], [Link]);
}
return node;
}
public static void main(String[] args) {
LeftistTree leftistTree = new LeftistTree();
// Insert elements
[Link](10);
[Link](5);
[Link](20);
[Link](3);
[Link](7);
// Search for a key element
int keyToSearch = 5;
[Link]("Is " + keyToSearch + " present in the Leftist tree? " +
[Link](keyToSearch));
// Delete an element
int keyToDelete = 20;
[Link](keyToDelete);
// Search for a key element after deletion
[Link]("Is " + keyToDelete + " present in the Leftist tree after deletion? " +
[Link](keyToDelete));
}
}

Output:
Is 5 present in the Leftist tree? true
Element 20 deleted from the Leftist tree.
Is 20 present in the Leftist tree after deletion? False

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

class BinomialNode {
int key;
int degree; // Degree of the binomial tree rooted at this node
BinomialNode parent;
BinomialNode child;
 BinomialNode sibling;
public BinomialNode(int key) {
[Link] = key;
[Link] = 0;
[Link] = null;
[Link] = null;
[Link] = null;
}
}
public class BinomialHeap {
private BinomialNode head; // Reference to the head of the binomial heap
public BinomialHeap() {
[Link] = null;
}
// Operation to insert an element into a binomial heap
public void insert(int key) {
BinomialNode newNode = new BinomialNode(key);
head = merge(head, newNode);
}
// Operation to delete an element from a binomial heap
public void delete(int key) {
if (search(head, key)) {
decreaseKey(head, key, Integer.MIN_VALUE); // Decrease the key to negative
infinity
extractMin();
[Link]("Element " + key + " deleted from the binomial heap.");
} else {
[Link]("Element " + key + " not found in the binomial heap.");
}
}
// Operation to search for a key element in a binomial heap
 public boolean search(int key) {
return search(head, key);
}
// Helper method to search for a key element in a binomial heap
private boolean search(BinomialNode node, int key) {
if (node == null) {
return false;
}
return ([Link] == key) || search([Link], key) || search([Link], key);
}
// Helper method to merge two binomial heaps
private BinomialNode merge(BinomialNode h1, BinomialNode h2) {
if (h1 == null) {
return h2;
} else if (h2 == null) {
return h1;
}
BinomialNode head = null;
BinomialNode tail = null;
BinomialNode prevX = null;
BinomialNode x = h1;
BinomialNode y = h2;
while (x != null && y != null) {
if ([Link] <= [Link]) {
if (tail == null) {
tail = x;
head = tail;
} else {
[Link] = x;
tail = x;
 }
x = [Link]:
} else {
if (tail == null) {
tail = y;
head = tail;
} else {
[Link] = y;
tail = y;
}
y = [Link];
}
if (prevX != null) {
[Link] = tail;
}
prevX = tail;
}
if (x != null) {
[Link] = x;
} else {
[Link] = y;
}
return head;
}
// Operation to extract the minimum element from the binomial heap
public int extractMin() {
if (head == null) {
return Integer.MIN_VALUE:
}
BinomialNode minPrev = null;
 BinomialNode min = head;
BinomialNode current = [Link];
BinomialNode prev = head;
while (current != null) {
if ([Link] < [Link]) {
min = current;
minPrev = prev;
}
prev = current;
current = [Link];
}
if (minPrev == null) {
head = [Link];
} else {
[Link] = [Link];
}
BinomialNode child = [Link];
BinomialNode prevChild = null;
while (child != null) {
BinomialNode next = [Link];
[Link] = prevChild;
[Link] = null;
prevChild = child;
child = next;
}
head = merge(head, prevChild);
return [Link];
}
// Helper method to decrease the key of a node in a binomial heap
private void decreaseKey(BinomialNode node, int oldKey, int newKey) {
 if (node == null) {
return;
}
if ([Link] == oldKey) {
[Link] = newKey;
if ([Link] != null && [Link] < [Link]) {
swap(node, [Link]);
decreaseKey([Link], oldKey, newKey);
}
}
decreaseKey([Link], oldKey, newKey);
decreaseKey([Link], oldKey, newKey);
}
// Helper method to swap two nodes in a binomial heap
private void swap(BinomialNode node1, BinomialNode node2) {
int tempKey = [Link];
[Link] = [Link];
[Link] = tempKey;
}
// Helper method to print a binomial heap
private void printHeap(BinomialNode node, int depth) {
if (node == null) {
return;
}
for (int i = 0; i < depth; i++) {
[Link]("\t");
}
[Link]([Link]);
printHeap([Link], depth + 1);
printHeap([Link], depth);
 }
public void printHeap() {
[Link]("Binomial Heap:");
printHeap(head, 0);
[Link]();
}
public static void main(String[] args) {
BinomialHeap binomialHeap = new BinomialHeap();
// Insert elements
[Link](10);
[Link](5);
[Link](20);
[Link](3);
[Link](7);
// Print the initial binomial heap
[Link]();
// Search for a key element
int keyToSearch = 5;
[Link]("Is " + keyToSearch + " present in the binomial heap? " +
[Link](keyToSearch));
// Delete an element
int keyToDelete = 20;
[Link](keyToDelete);
// Print the binomial heap after deletion
[Link]();
}
}

Output:
Binomial Heap:
3
5
10
7
20
Is 5 present in the binomial heap? true
Element 20 deleted from the binomial heap.
Binomial Heap:
3
5
10
7

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.

class AVLNode {
int key;
int height;
AVLNode left;
AVLNode right;
public AVLNode(int key) {
 [Link] = key;
[Link] = 1;
[Link] = null;
[Link] = null;
}
}
public class AVLTree {
private AVLNode root;
public AVLTree() {
[Link] = null;
}
// Operation to insert an element into an AVL tree
public void insert(int key) {
root = insert(root, key);
}
private AVLNode insert(AVLNode node, int key) {
if (node == null) {
return new AVLNode(key);
}
if (key < [Link]) {
[Link] = insert([Link], key);
} else if (key > [Link]) {
[Link] = insert([Link], key);
} else {
// Duplicate keys are not allowed in AVL trees
return node;
}
// Update height of the current node
[Link] = 1 + [Link](getHeight([Link]), getHeight([Link]));
// Check balance factor and perform rotations if necessary
 int balance = getBalance(node);
// Left Left Case
if (balance > 1 && key < [Link]) {
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && key > [Link]) {
return leftRotate(node);

}
// Left Right Case
if (balance > 1 && key > [Link]) {
[Link] = leftRotate([Link]);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < [Link]) {
[Link] = rightRotate([Link]);
return leftRotate(node);
}
return node;
}
// Operation to delete an element from an AVL tree
public void delete(int key) {
root = delete(root, key);
}
private AVLNode delete(AVLNode node, int key) {
if (node == null) {
return null;
}
 if (key < [Link]) {
[Link] = delete([Link], key);
} else if (key > [Link]) {
[Link] = delete([Link], key);
} else {
// Node with only one child or no child
if ([Link] == null || [Link] == null) {
AVLNode temp = ([Link] != null) ? [Link] : [Link];
// No child case
if (temp == null) {
temp = node;
node = null;
} else {
// One child case
node = temp; // Copy the contents of the non-empty child
}
temp = null;
} else {
// Node with two children: Get the inorder successor (smallest
// in the right subtree)
AVLNode temp = minValueNode([Link]);
// Copy the inorder successor's data to this node
[Link] = [Link];
// Delete the inorder successor
[Link] = delete([Link], [Link]);
}
}
// If the tree had only one node, then return
if (node == null) {
return null;
}
// Update height of the current node
[Link] = 1 + [Link](getHeight([Link]), getHeight([Link]));
// Check balance factor and perform rotations if necessary
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && getBalance([Link]) >= 0) {
return rightRotate(node);
}
// Left Right Case
if (balance > 1 && getBalance([Link]) < 0) {
[Link] = leftRotate([Link]);
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && getBalance([Link]) <= 0) {
return leftRotate(node);
}
// Right Left Case
if (balance < -1 && getBalance([Link]) > 0) {
[Link] = rightRotate([Link]);
return leftRotate(node);
}
return node;
}
// Helper method to perform a left rotation
private AVLNode leftRotate(AVLNode y) {
AVLNode x = [Link];
AVLNode T2 = [Link];
// Perform rotation
 [Link] = y;
[Link] = T2;
// Update heights
[Link] = 1 + [Link](getHeight([Link]), getHeight([Link]));
[Link] = 1 + [Link](getHeight([Link]), getHeight([Link]));
return x;
}
// Helper method to perform a right rotation
private AVLNode rightRotate(AVLNode x) {
AVLNode y = [Link];
AVLNode T2 = [Link];
// Perform rotation
[Link] = x;
[Link] = T2;
// Update heights
[Link] = 1 + [Link](getHeight([Link]), getHeight([Link]));
[Link] = 1 + [Link](getHeight([Link]), getHeight([Link]));
return y;
}
// Helper method to get the balance factor of a node
private int getBalance(AVLNode node) {
if (node == null) {
return 0;
}
return getHeight([Link]) - getHeight([Link]);
}
// Helper method to get the height of a node
private int getHeight(AVLNode node) {
if (node == null) {
return 0;
 }
return [Link];
}
// Helper method to find the node with the smallest key value in a tree
private AVLNode minValueNode(AVLNode node) {
AVLNode current = node;
while ([Link] != null) {
current = [Link];
}
return current;
}
// Operation to search for a key element in an AVL tree
public boolean search(int key) {
return search(root, key);
}
private boolean search(AVLNode node, int key) {
if (node == null) {
return false;
}
if (key == [Link]) {
return true;
} else if (key < [Link]) {
return search([Link], key);
} else {
return search([Link], key);
}
}
// Helper method to print an AVL tree in-order
private void inOrderTraversal(AVLNode node) {
if (node != null) {
 inOrderTraversal([Link]);
[Link]([Link] + " ");
inOrderTraversal([Link]);
}
}
public void inOrderTraversal() {
[Link]("In-order traversal: ");
inOrderTraversal(root);
[Link]();
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
// Insert elements
[Link](10);
[Link](5);
[Link](20);
[Link](3);
[Link](7);
// Print the initial AVL tree
[Link]();
// Search for a key element
int keyToSearch = 5;
[Link]("Is " + keyToSearch + " present in the AVL tree? " +
[Link](keyToSearch));
// Delete an element
int keyToDelete = 20;
[Link](keyToDelete);
// Print the AVL tree after deletion
[Link]();
}
}

Output:
In-order traversal: 3 5 7 10 20
Is 5 present in the AVL tree? True
In-order traversal: 3 5 7 10

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

// Red Black Tree operations in C

#include <stdio.h>
#include <stdlib.h>

// Red-Black Tree Node Structure

typedef struct Node {
int data;
struct Node* parent;
 struct Node* left;
struct Node* right;
int color; // 0 for black, 1 for red
} Node;

// Red-Black Tree Structure

typedef struct RedBlackTree {
Node* root;
} RedBlackTree;

// Create a new Red-Black Tree Node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation error\n");
exit(1);
}
newNode->data = data;
newNode->parent = newNode->left = newNode->right = NULL;
newNode->color = 1; // New nodes are initially red
return newNode;
}

// Create a new Red-Black Tree

RedBlackTree* createRedBlackTree() {
RedBlackTree* newTree =
(RedBlackTree*)malloc(sizeof(RedBlackTree));
if (newTree == NULL) {
printf("Memory allocation error\n");
exit(1);
}
newTree->root = NULL;
return newTree;
}

// Function to perform left rotation

void leftRotate(RedBlackTree* tree, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NULL)
tree->root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
 y->left = x;
x->parent = y;
}

// Function to perform right rotation

void rightRotate(RedBlackTree* tree, Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == NULL)
tree->root = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
}

// Function to fix the Red-Black Tree properties after

insertion
void insertFixup(RedBlackTree* tree, Node* z) {
while (z->parent != NULL && z->parent->color == 1) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y != NULL && y->color == 1) {
z->parent->color = 0; // Black
y->color = 0; // Black
z->parent->parent->color = 1; // Red
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
leftRotate(tree, z);
}
z->parent->color = 0; // Black
z->parent->parent->color = 1; // Red
rightRotate(tree, z->parent->parent);
}
} else {
Node* y = z->parent->parent->left;
if (y != NULL && y->color == 1) {
z->parent->color = 0; // Black
y->color = 0; // Black
z->parent->parent->color = 1; // Red
z = z->parent->parent;
 } else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(tree, z);
}
z->parent->color = 0; // Black
z->parent->parent->color = 1; // Red
leftRotate(tree, z->parent->parent);
}
}
}
tree->root->color = 0; // Root must be black
}

// Function to insert a node into the Red-Black Tree

void insert(RedBlackTree* tree, int data) {
Node* z = createNode(data);
Node* y = NULL;
Node* x = tree->root;

while (x != NULL) {
y = x;
if (z->data < x->data)
x = x->left;
else
x = x->right;
}

z->parent = y;
if (y == NULL)
tree->root = z;
else if (z->data < y->data)
y->left = z;
else
y->right = z;

insertFixup(tree, z);
}

// Function to find the minimum value node in the tree rooted

at a given node
Node* findMinValueNode(Node* node) {
Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
// Function to fix the Red-Black Tree properties after
deletion
void deleteFixup(RedBlackTree* tree, Node* x) {
while (x != tree->root && x->color == 0) {
if (x == x->parent->left) {
Node* w = x->parent->right;
if (w->color == 1) {
w->color = 0; // Change sibling to black
x->parent->color = 1; // Change parent to red
leftRotate(tree, x->parent);
w = x->parent->right;
}
if (w->left->color == 0 && w->right->color == 0) {
w->color = 1; // Change sibling to red
x = x->parent; // Move up the tree
} else {
if (w->right->color == 0) {
w->left->color = 0; // Change sibling's
left child to black
w->color = 1; // Change sibling to red
rightRotate(tree, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = 0; // Change parent to
black
w->right->color = 0; // Change sibling's right
child to black
leftRotate(tree, x->parent);
x = tree->root; // This is to exit the loop
}
} else {
// Same as then clause with "right" and "left"
exchanged
Node* w = x->parent->left;
if (w->color == 1) {
w->color = 0;
x->parent->color = 1;
rightRotate(tree, x->parent);
w = x->parent->left;
}
if (w->right->color == 0 && w->left->color == 0) {
w->color = 1;
x = x->parent;
} else {
if (w->left->color == 0) {
w->right->color = 0;
w->color = 1;
 leftRotate(tree, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = 0;
w->left->color = 0;
rightRotate(tree, x->parent);
x = tree->root;
}
}
}
x->color = 0; // Ensure the root is black
}

// Transplant helper function

void transplant(RedBlackTree* tree, Node* u, Node* v) {
if (u->parent == NULL) {
tree->root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
if (v != NULL) {
v->parent = u->parent;
}
}

// Function to delete a node from the Red-Black Tree

void delete(RedBlackTree* tree, int data) {
Node* z = tree->root;
while (z != NULL && z->data != data) {
if (data < z->data)
z = z->left;
else
z = z->right;
}

if (z == NULL) {
printf("Node not found in the tree\n");
return; // Node to be deleted not found
}

Node* y = z; // Node to be unlinked from the tree

Node* x; // y's only child or NULL
int yOriginalColor = y->color;

if (z->left == NULL) {
 x = z->right;
transplant(tree, z, z->right);
} else if (z->right == NULL) {
x = z->left;
transplant(tree, z, z->left);
} else {
y = findMinValueNode(z->right); // Find the minimum
node of the right subtree
yOriginalColor = y->color;
x = y->right;

if (y->parent == z) {
x->parent = y; // Necessary when x is NULL
} else {
transplant(tree, y, y->right);
y->right = z->right;
y->right->parent = y;
}

transplant(tree, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}

free(z);

if (yOriginalColor == 0) {
deleteFixup(tree, x);
}
}

// Function to perform in-order traversal of the Red-Black

Tree
void inOrderTraversal(Node* root) {
char c[2][6]={"BLACK","RED"};
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d,%s -> ", root->data, c[root->color]);
inOrderTraversal(root->right);
}
}

// Function to free memory by deallocating nodes

void freeMemory(Node* root) {
if (root == NULL)
return;
freeMemory(root->left);
 freeMemory(root->right);
free(root);
}

int main() {
int choice,value;
RedBlackTree* tree = createRedBlackTree();
do
{
printf("\n1. Insertion\n2. Deletion\n3. Display\n4.
Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
insert(tree, value);
break;
case 2: printf("Enter the value to be deleted: ");
scanf("%d",&value);
delete(tree, value);
break;
case 3: inOrderTraversal(tree->root);
break;
case 4: freeMemory(tree->root);
break;
default: printf("\nWrong selection!!! Try again!!!");
}
}while(choice!=4);
return(0);
}

OUTPUT
/tmp/tnOjm2NG3L.o
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1
Enter the value to be insert: 1
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1
Enter the value to be insert: 2
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1
Enter the value to be insert: 3
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 3
1,RED -> 2,BLACK -> 3,RED ->
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1
Enter the value to be insert: 4
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1
Enter the value to be insert: 5
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 3
1,BLACK -> 2,BLACK -> 3,RED -> 4,BLACK -> 5,RED ->
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 2
Enter the value to be deleted: 3
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 3
1,BLACK -> 2,BLACK -> 4,BLACK -> 5,RED ->
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 2
Enter the value to be deleted: 5
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 3
1,BLACK -> 2,BLACK -> 4,BLACK ->
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 4

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

hashing.
#include <iostream>
#include <string>
#include <list>

using namespace std;

class HashTable {
private:
int size;
list<pair<string, int>>* table;
public:
HashTable(int size) {
this->size = size;
table = new list<pair<string, int>>[size];
}
~HashTable() {
delete[] table;
}
int hashFunction(const string& key) {
int hashValue = 0;
for (char c : key) {
hashValue += c;
}
return hashValue % size;
}
void insert(const string& key, int value) {
int index = hashFunction(key);
for (auto& pair : table[index]) {
if ([Link] == key) {
[Link] = value;
return;
 }
}
table[index].push_back(make_pair(key, value));
}

int get(const string& key) {

int index = hashFunction(key);
for (const auto& pair : table[index]) {
if ([Link] == key) {
return [Link];
}
}
return -1; // Key not found
}
void remove(const string& key) {
int index = hashFunction(key);
table[index].remove_if([key](const pair<string, int>& pair) {
return [Link] == key;
});
}
void display() {
for (int i = 0; i < size; ++i) {
cout << "Index " << i << ": ";
for (const auto& pair : table[i]) {
cout << [Link] << " -> " << [Link] << ", ";
}
cout << endl;
}
}
};
int main() {
HashTable dictionary(10);
[Link]("apple", 5);
[Link]("banana", 7);
[Link]("orange", 3);
[Link]();
cout << "Value of 'apple': " << [Link]("apple") << endl;
[Link]("banana");
[Link]();
return 0;
}

Output:
Index 0:
Index 1:
Index 2:
Index 3:
Index 4:
Index 5:
Index 6: orange -> 3,
Index 7:
Index 8: apple -> 5,
Index 9: banana -> 7,
Value of 'apple': 5
Index 0:
Index 1:
Index 2:
Index 3:
Index 4:
Index 5:
Index 6: orange -> 3,
Index 7:
Index 8: apple -> 5,

[Link] a program for implementing Knuth-Morris-Pratt pattern

matching algorithm.
#include <stdio.h>
#include <string.h>

int lps[100];
void longestPrefixSuffix(char p[])
{
int i=1,j=0;
int m = strlen(p);
lps[0] = 0;
while(i < m)
{
if( p[j] == p[i])
{
lps[i]=j+1;
i++;
j++;
}
else if(j>0)
j = lps[j-1];
else
{
lps[i]=0;
i++;
}
}
}

int kmp (char p[],char t[])

{
int n,m;
int i=0,j=0;
n = strlen(t);
m = strlen(p);
longestPrefixSuffix(p);
while( i < n )
{
if ( p[j] == t[i])
{
if (j == m-1 )
return i-j;
i++;
j++;
}
else if(j>0)
j = lps[j-1];
else
i++;
}
 return 0;
}

int main() {
char t[]="kiss*miss*in*mississippi";
char p[]="missi";
int i;
i=kmp(p,t);
if(i)
printf("pattern is present in text at position
%d",i+1);
else
printf("pattern is not present in text");
return 0;
}

OUTPUT
pattern is present in text at position 14

[Link] a program for implementing Brute Force pattern matching

algorithm.
#include <stdio.h>
#include <string.h>
int brute_force_pattern_matching(char *text, char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
for (int i = 0; i <= n - m; i++) {
int match = 1;
for (int j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
match = 0;
break;
} }
if (match) {
return i;
} }
return -1;
}
int main() {
char text[] = "abcabcabc";
char pattern[] = "abc";
int index = brute_force_pattern_matching(text, pattern);
if (index != -1) {
printf("Pattern found at index %d\n", index);
} else {
printf("Pattern not found\n");
}
return 0;
}
Output:
Pattern found at index 0

12. Write a program for implementing Boyer pattern matching algorithm.

#include <stdio.h>
#include <string.h>

int max(int a, int b)

{
if(a > b)
return a;
else
return b;
}
int boyermorre(char p[],char t[])
{
int bctable[128],i,j,k;
int n = strlen(t);
int m = strlen(p);
for(j=0; j<128; j++)
{
bctable[j]=m;
}
for(j=0; j<m; j++)
{
k=(int)p[j];
bctable[k]=m-j-1;
}
i=m-1;
while(i < n)
{
j=m-1;
while(j >= 0 && p[j] == t[i])
{
i--;
j--;
}
if(j == -1)
return i+1;
i = i + max((int)bctable[t[i]],m-j);
}
return 0;
}

int main() {
char t[]="kiss*miss*in*mississippi";
char p[]="missi";
int i;
i=boyermorre(p,t);
if(i)
printf("pattern is present in text at position
%d",i+1);
 else
printf("pattern is not present in text");
return 0;
}

Output:

pattern is present in text at position 14