PRINCETON INSTITUTE OF ENGINEERING AND

TECHNOLOGY FOR WOMEN

(UGC - Autonomous)

[Link] - Computer Science and Engineering (R25)

ADVANCED DATA STRUCTURES LAB

(LAB - I)
Course Code: 2 5 P D 0 5 1 0 3

Lab Manual

Prepared By:
[Link] indrapalli
Associate Professor & Head, CSE allied Branches
Princeton Institute of Engineering and Technology for women

Academic Year: 2025-26

Contents

1 Binary Search Tree Operations

2 Sorting Algorithms: Merge Sort, Heap Sort, Quick Sort

3 B-Tree Operations

4 Min-Max Heap Operations

5 Leftist Tree Operations

6 Binomial Heap Operations

7 AVL Tree Operations

8 Red–Black Tree Operations

9 Dictionary Using Hashing

10 Knuth–Morris–Pratt (KMP) Pattern Matching Algorithm

11 Brute-Force Pattern Matching Algorithm

12 Boyer–Moore Pattern Matching Algorithm

1
Chapter 1
Binary Search Tree Operations
Aim
To write a C program to perform insertion, deletion, and search operations on a Binary
Search Tree (BST).

Program

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

// Structure of BST Node

struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Create New Node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node));

newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

// Insert Element
struct Node* insert(struct Node* root, int value) {

2
 if (root == NULL)
return createNode(value);

if (value < root->data)

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

else if (value > root->data)

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

return root;
}

// Search Element
struct Node* search(struct Node* root, int key) {

if (root == NULL || root->data == key)

return root;

if (key < root->data)

return search(root->left, key);

return search(root->right, key);

}

// Find Minimum Value Node

struct Node* findMin(struct Node* root) {

while (root->left != NULL)

root = root->left;

return root;
}

// Delete Element
struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL)
3
 return root;

// If key is smaller
if (key < root->data)
root->left = deleteNode(root->left, key);

// If key is greater
else if (key > root->data)
root->right = deleteNode(root->right, key);

// If key is found
else {

// Node with one child or no child

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

else if (root->right == NULL) {

struct Node* temp = root->left;
free(root);
return temp;
}

// Node with two children

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

root->data = temp->data;

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

}

return root;
}

// Inorder Traversal
4
void inorder(struct Node* root) {

if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

// Main Function
int main() {

struct Node* root = NULL;

int choice, value;

while (1) {

printf("\n\nBinary Search Tree Operations");

printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Search");
printf("\n4. Display (Inorder)");
printf("\n5. Exit");
printf("\nEnter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
root = insert(root, value);
printf("Inserted successfully.");
break;

case 2:
printf("Enter value to delete: ");
5
 scanf("%d", &value);
root = deleteNode(root, value);
printf("Deleted successfully.");
break;

case 3:
printf("Enter value to search: ");
scanf("%d", &value);

if (search(root, value) != NULL)

printf("Element found.");
else
printf("Element not found.");

break;

case 4:
printf("BST (Inorder Traversal): ");
inorder(root);
break;

case 5:
exit(0);

default:
printf("Invalid choice!");
}
}

return 0;
}

6
OUTPUT
Binary Search Tree Operations
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 1
Enter value to insert: 50
Inserted successful.

7
 Advanced Data Structures Lab Manual

Chapter 2

Sorting Algorithms: Merge Sort,

Heap Sort, Quick Sort

Aim
To implement Merge Sort, Heap Sort, and Quick Sort in C and compare their working
principles, performance, and outputs.

Program

#include <stdio.h>

// Function to display array

void display(int arr[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

/* ================= MERGE SORT ================= */

void merge(int arr[], int l, int m, int r) {

int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

// Copy data
for (i = 0; i < n1; i++)
L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1 + j];

i = 0;
j = 0;
k = l;

// Merge arrays
while (i < n1 && j < n2) {
8
 Advanced Data Structures Lab Manual

if (L[i] <= R[j])

arr[k++] = L[i++];
else
arr[k++] = R[j++];
}

// Copy remaining elements

while (i < n1)
arr[k++] = L[i++];

while (j < n2)

arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {

if (l < r) {

int m = l + (r - l) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

/* ================= HEAP SORT ================= */

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

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

// Left child
if (left < n && arr[left] > arr[largest])
largest = left;

// Right child
if (right < n && arr[right] > arr[largest])
largest = right;

// If largest is not root

if (largest != i) {

int temp = arr[i];

arr[i] = arr[largest];
arr[largest] = temp;

heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n) {

int i;
9
 Advanced Data Structures Lab Manual

// Build heap
for (i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// Extract elements
for (i = n - 1; i >= 0; i--) {

int temp = arr[0];

arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
}

/* ================= QUICK SORT ================= */

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = low - 1, j, temp;

for (j = low; j < high; j++) {

if (arr[j] <= pivot) {

i++;

temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

temp = arr[i + 1];

arr[i + 1] = arr[high];
arr[high] = temp;

return i + 1;
}

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

/* ================= MAIN FUNCTION ================= */

int main() {

int n, choice;
1
0
 Advanced Data Structures Lab Manual

printf("Enter number of elements: ");

scanf("%d", &n);

int arr[n];

printf("Enter elements:\n");

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

scanf("%d", &arr[i]);

while (1) {

printf("\n\nSorting Methods");
printf("\n1. Merge Sort");
printf("\n2. Heap Sort");
printf("\n3. Quick Sort");
printf("\n4. Display Array");
printf("\n5. Exit");

printf("\nEnter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:
mergeSort(arr, 0, n - 1);
printf("Sorted using Merge Sort.\n");
break;

case 2:
heapSort(arr, n);
printf("Sorted using Heap Sort.\n");
break;

case 3:
quickSort(arr, 0, n - 1);
printf("Sorted using Quick Sort.\n");
break;

case 4:
display(arr, n);
break;

case 5:
return 0;

default:
printf("Invalid choice!");
}
}

return 0;
}

Sorting Methods
1. Merge Sort
1
1
 Advanced Data Structures Lab Manual
2. Heap Sort
3. Quick Sort
4. Display Array
5. Exit
Enter your choice: 4
45 12 78 34 23

Sorting Methods
1. Merge Sort
2. Heap Sort
3. Quick Sort
4. Display Array
5. Exit
Enter your choice: 1
Sorted using Merge Sort.

Sorting Methods
1. Merge Sort
2. Heap Sort
3. Quick Sort
4. Display Array
5. Exit
Enter your choice: 4
12 23 34 45 78

Sorting Methods
1. Merge Sort
2. Heap Sort
3. Quick Sort
4. Display Array
5. Exit
Enter your choice: 3
Sorted using Quick Sort.

Sorting Methods
1. Merge Sort
2. Heap Sort
3. Quick Sort
4. Display Array
5. Exit
Enter your choice: 4
12 23 34 45 78

Sorting Methods
1. Merge Sort
2. Heap Sort
3. Quick Sort
4. Display Array
5. Exit
Enter your choice

1
2
 Advanced Data Structures Lab Manual B3CS104PC

Chapter 3

B-Tree Operations

Aim
To implement insertion, deletion, and search operations on a B-Tree of specified minimum
degree t using C programming.

PROGRAM

#include <stdio.h>

#include <stdlib.h>

#define T 3 // Minimum degree

// B-Tree Node Structure

struct BTreeNode {

int keys[2 * T - 1];

struct BTreeNode* child[2 * T];

int n;

int leaf;

};

// Create new node

13
 Advanced Data Structures Lab Manual B3CS104PC
struct BTreeNode* createNode(int leaf) {

struct BTreeNode* node =

(struct BTreeNode*)malloc(sizeof(struct BTreeNode));

node->leaf = leaf;

node->n = 0;

for (int i = 0; i < 2 * T; i++)

node->child[i] = NULL;

return node;

// Traverse tree

void traverse(struct BTreeNode* root) {

if (root != NULL) {

int i;

for (i = 0; i < root->n; i++) {

if (!root->leaf)

traverse(root->child[i]);

14
 Advanced Data Structures Lab Manual B3CS104PC
printf("%d ", root->keys[i]);

if (!root->leaf)

traverse(root->child[i]);

// Search key

struct BTreeNode* search(struct BTreeNode* root, int k) {

int i = 0;

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

i++;

if (i < root->n && root->keys[i] == k)

return root;

if (root->leaf)

return NULL;

return search(root->child[i], k);

// Split child

15
 Advanced Data Structures Lab Manual B3CS104PC
void splitChild(struct BTreeNode* x, int i,

struct BTreeNode* y) {

struct BTreeNode* z = createNode(y->leaf);

z->n = T - 1;

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

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

if (!y->leaf) {

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

z->child[j] = y->child[j + T];

y->n = T - 1;

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

x->child[j + 1] = x->child[j];

x->child[i + 1] = z;

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

x->keys[j + 1] = x->keys[j];

x->keys[i] = y->keys[T - 1];

16
 Advanced Data Structures Lab Manual B3CS104PC
x->n++;

// Insert in non-full node

void insertNonFull(struct BTreeNode* x, int k) {

int i = x->n - 1;

if (x->leaf) {

while (i >= 0 && k < x->keys[i]) {

x->keys[i + 1] = x->keys[i];

i--;

x->keys[i + 1] = k;

x->n++;

else {

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

i--;

i++;

if (x->child[i]->n == 2 * T - 1) {

17
 Advanced Data Structures Lab Manual B3CS104PC

splitChild(x, i, x->child[i]);

if (k > x->keys[i])

i++;

insertNonFull(x->child[i], k);

// Insert key

struct BTreeNode* insert(struct BTreeNode* root, int k) {

if (root == NULL) {

root = createNode(1);

root->keys[0] = k;

root->n = 1;

return root;

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

struct BTreeNode* s = createNode(0);

18
 Advanced Data Structures Lab Manual B3CS104PC

s->child[0] = root;

splitChild(s, 0, root);

int i = 0;

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

i++;

insertNonFull(s->child[i], k);

return s;

else {

insertNonFull(root, k);

return root;

// Simple delete (for leaf only – academic use)

void deleteKey(struct BTreeNode* root, int k) {

if (root == NULL) {

printf("Tree empty!\n");

19
 Advanced Data Structures Lab Manual B3CS104PC
return;

int i;

for (i = 0; i < root->n; i++) {

if (root->keys[i] == k) {

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

root->keys[j] = root->keys[j + 1];

root->n--;

printf("Key deleted.\n");

return;

if (root->leaf) {

printf("Key not found.\n");

return;

deleteKey(root->child[i], k);

20
 Advanced Data Structures Lab Manual B3CS104PC

// Main

int main() {

struct BTreeNode* root = NULL;

int choice, val;

while (1) {

printf("\n\nB-Tree Operations");

printf("\n1. Insert");

printf("\n2. Delete");

printf("\n3. Search");

printf("\n4. Display");

printf("\n5. Exit");

printf("\nEnter choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter value: ");

scanf("%d", &val);

root = insert(root, val);

21
 Advanced Data Structures Lab Manual B3CS104PC
printf("Inserted.\n");

break;

case 2:

printf("Enter value to delete: ");

scanf("%d", &val);

deleteKey(root, val);

break;

case 3:

printf("Enter value to search: ");

scanf("%d", &val);

if (search(root, val))

printf("Key found.\n");

else

printf("Key not found.\n");

break;

case 4:

printf("B-Tree: ");

traverse(root);

printf("\n");

break;

22
 Advanced Data Structures Lab Manual B3CS104PC
case 5:

return 0;

default:

printf("Invalid choice!\n");

return 0;

OUTPUT

B-Tree Operations

1. Insert

2. Delete

3. Search

4. Display

5. Exit

Enter choice: 1

Enter value: 10

Inserted.

B-Tree Operations

23
 Advanced Data Structures Lab Manual B3CS104PC
Enter choice: 1

Enter value: 20

Inserted.

B-Tree Operations

Enter choice: 1

Enter value: 5

Inserted.

B-Tree Operations

Enter choice: 1

Enter value: 6

Inserted.

B-Tree Operations

Enter choice: 1

Enter value: 12

Inserted.

B-Tree Operations

Enter choice: 4

B-Tree: 5 6 10 12 20

24
 Advanced Data Structures Lab Manual B3CS104PC

B-Tree Operations

Enter choice: 3

Enter value to search: 6

Key found.

B-Tree Operations

Enter choice: 2

Enter value to delete: 6

Key deleted.

B-Tree Operations

Enter choice: 4

B-Tree: 5 10 12 20

B-Tree Operations

Enter choice:

25
 Advanced Data Structures Lab Manual

Chapter 4

Min-Max Heap Operations

Aim
To implement the fundamental operations of a Min-Max Heap, specifically:

Insertion of a new element

Extraction of the minimum element

Extraction of the maximum element

Searching for an element

using a two-heap approach (one Min Heap and one Max Heap).

Program

#include <stdio.h>
#include <math.h>

#define MAX 100

int heap[MAX];
int size = 0;

/* Check if node is on Min Level */

int isMinLevel(int index) {

int level = (int)log2(index + 1);

26
 Advanced Data Structures Lab Manual

if (level % 2 == 0)
return 1; // Min level
else
return 0; // Max level
}

/* Swap two elements */

void swap(int *a, int *b) {

int temp = *a;

*a = *b;
*b = temp;
}

/* Bubble Up Min */
void bubbleUpMin(int i) {

if (i >= 3) {

int gp = (i - 3) / 4;

if (heap[i] < heap[gp]) {

swap(&heap[i], &heap[gp]);
bubbleUpMin(gp);
}
}
}

/* Bubble Up Max */
void bubbleUpMax(int i) {

if (i >= 3) {

27
 Advanced Data Structures Lab Manual

int gp = (i - 3) / 4;

if (heap[i] > heap[gp]) {

swap(&heap[i], &heap[gp]);
bubbleUpMax(gp);
}
}
}

/* Insert Element */
void insert(int key) {

if (size >= MAX) {

printf("Heap Overflow!\n");
return;
}

heap[size] = key;
int i = size;
size++;

if (i == 0)
return;

int parent = (i - 1) / 2;

if (isMinLevel(i)) {

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

swap(&heap[i], &heap[parent]);
bubbleUpMax(parent);
}
else
28
 Advanced Data Structures Lab Manual

bubbleUpMin(i);
}
else {

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

swap(&heap[i], &heap[parent]);
bubbleUpMin(parent);
}
else
bubbleUpMax(i);
}

printf("Inserted successfully.\n");
}

/* Heapify Down Min */

void trickleDownMin(int i) {

int smallest = i;

int l = 2 * i + 1;
int r = 2 * i + 2;

int ll = 2 * l + 1;
int lr = 2 * l + 2;
int rl = 2 * r + 1;
int rr = 2 * r + 2;

int candidates[6] = {l, r, ll, lr, rl, rr};

for (int k = 0; k < 6; k++) {

int idx = candidates[k];

29
 Advanced Data Structures Lab Manual

if (idx < size && heap[idx] < heap[smallest])

smallest = idx;
}

if (smallest != i) {

if (smallest >= 4 * i + 3) {

swap(&heap[i], &heap[smallest]);

int parent = (smallest - 1) / 2;

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

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

trickleDownMin(smallest);
}
else {

swap(&heap[i], &heap[smallest]);
}
}
}

/* Heapify Down Max */

void trickleDownMax(int i) {

int largest = i;

int l = 2 * i + 1;
int r = 2 * i + 2;

int ll = 2 * l + 1;
int lr = 2 * l + 2;
int rl = 2 * r + 1;
30
 Advanced Data Structures Lab Manual

int rr = 2 * r + 2;

int candidates[6] = {l, r, ll, lr, rl, rr};

for (int k = 0; k < 6; k++) {

int idx = candidates[k];

if (idx < size && heap[idx] > heap[largest])

largest = idx;
}

if (largest != i) {

if (largest >= 4 * i + 3) {

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

int parent = (largest - 1) / 2;

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

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

trickleDownMax(largest);
}
else {

swap(&heap[i], &heap[largest]);
}
}
}

/* Restore Heap Property */

void trickleDown(int i) {

31
 Advanced Data Structures Lab Manual

if (isMinLevel(i))
trickleDownMin(i);
else
trickleDownMax(i);
}

/* Delete Root (Min) */

void deleteMin() {

if (size == 0) {
printf("Heap is empty!\n");
return;
}

printf("Deleted Min: %d\n", heap[0]);

heap[0] = heap[size - 1];

size--;

trickleDown(0);
}

/* Delete Max */
void deleteMax() {

if (size <= 1) {
deleteMin();
return;
}

int maxIndex;

if (size == 2)
maxIndex = 1;
else
32
 Advanced Data Structures Lab Manual

maxIndex = (heap[1] > heap[2]) ? 1 : 2;

printf("Deleted Max: %d\n", heap[maxIndex]);

heap[maxIndex] = heap[size - 1];

size--;

trickleDown(maxIndex);
}

/* Search Element */
void search(int key) {

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

if (heap[i] == key) {

printf("Element %d found at index %d\n", key, i);

return;
}
}

printf("Element not found.\n");

}

/* Display Heap */
void display() {

if (size == 0) {
printf("Heap is empty!\n");
return;
}

printf("Heap Elements: ");

33
 Advanced Data Structures Lab Manual

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

printf("%d ", heap[i]);

printf("\n");
}

/* Main */
int main() {

int choice, val;

while (1) {

printf("\n\nMin-Max Heap Operations");

printf("\n1. Insert");
printf("\n2. Delete Min");
printf("\n3. Delete Max");
printf("\n4. Search");
printf("\n5. Display");
printf("\n6. Exit");

printf("\nEnter choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:
printf("Enter value: ");
scanf("%d", &val);
insert(val);
break;

case 2:
deleteMin();
break;
34
 Advanced Data Structures Lab Manual

case 3:
deleteMax();
break;

case 4:
printf("Enter value to search: ");
scanf("%d", &val);
search(val);
break;

case 5:
display();
break;

case 6:
return 0;

default:
printf("Invalid choice!\n");
}
}

return 0;
}

OUTPUT

Min-Max Heap Operations

1. Insert
2. Delete Min
3. Delete Max
4. Search
5. Display
6. Exit
35
 Advanced Data Structures Lab Manual

Enter choice: 1
Enter value: 20
Inserted successfully.

Enter choice: 1
Enter value: 5
Inserted successfully.

Enter choice: 1
Enter value: 30
Inserted successfully.

Enter choice: 1
Enter value: 15
Inserted successfully.

Enter choice: 5
Heap Elements: 5 20 30 15

Enter choice: 4
Enter value to search: 15
Element 15 found at index 3

Enter choice: 2
Deleted Min: 5

Enter choice: 5
Heap Elements: 15 20 30

Enter choice: 3
Deleted Max: 30

Enter choice: 5
Heap Elements: 15 20
36
 Advanced Data Structures Lab Manual

Enter choice: 6

CHAPTER 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

#include <stdio.h>

#include <stdlib.h>

/* Structure for Leftist Tree Node */

struct Node {

int key;

int npl; // Null Path Length

struct Node* left;

struct Node* right;

};

37
 Advanced Data Structures Lab Manual

/* Create New Node */

struct Node* createNode(int key) {

struct Node* newNode =

(struct Node*)malloc(sizeof(struct Node));

newNode->key = key;

newNode->npl = 0;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

/* Merge Two Leftist Trees */

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

38
 Advanced Data Structures Lab Manual

if (h1 == NULL)

return h2;

if (h2 == NULL)

return h1;

// Min Heap property

if (h1->key > h2->key) {

struct Node* temp = h1;

h1 = h2;

h2 = temp;

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

39
 Advanced Data Structures Lab Manual

// Maintain Leftist Property

int leftNPL = (h1->left == NULL) ? -1 : h1->left->npl;

int rightNPL = (h1->right == NULL) ? -1 : h1->right->npl;

if (leftNPL < rightNPL) {

struct Node* temp = h1->left;

h1->left = h1->right;

h1->right = temp;

// Update NPL

if (h1->right == NULL)

h1->npl = 0;

else

h1->npl = h1->right->npl + 1;

40
 Advanced Data Structures Lab Manual

return h1;

/* Insert Element */

struct Node* insert(struct Node* root, int key) {

struct Node* newNode = createNode(key);

root = merge(root, newNode);

printf("Inserted successfully.\n");

return root;

/* Delete Minimum (Root) */

struct Node* deleteMin(struct Node* root) {

41
 Advanced Data Structures Lab Manual

if (root == NULL) {

printf("Tree is empty!\n");

return NULL;

printf("Deleted element: %d\n", root->key);

struct Node* left = root->left;

struct Node* right = root->right;

free(root);

return merge(left, right);

42
 Advanced Data Structures Lab Manual

/* Search Element */

int search(struct Node* root, int key) {

if (root == NULL)

return 0;

if (root->key == key)

return 1;

return search(root->left, key) ||

search(root->right, key);

/* Display (Preorder Traversal) */

void display(struct Node* root) {

if (root != NULL) {

43
 Advanced Data Structures Lab Manual

printf("%d ", root->key);

display(root->left);

display(root->right);

/* Main Function */

int main() {

struct Node* root = NULL;

int choice, val;

while (1) {

44
 Advanced Data Structures Lab Manual

printf("\n\nLeftist Tree Operations");

printf("\n1. Insert");

printf("\n2. Delete (Delete Min)");

printf("\n3. Search");

printf("\n4. Display");

printf("\n5. Exit");

printf("\nEnter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter value: ");

scanf("%d", &val);

root = insert(root, val);

45
 Advanced Data Structures Lab Manual

break;

case 2:

root = deleteMin(root);

break;

case 3:

printf("Enter value to search: ");

scanf("%d", &val);

if (search(root, val))

printf("Element found.\n");

else

printf("Element not found.\n");

break;

46
 Advanced Data Structures Lab Manual

case 4:

printf("Leftist Tree (Preorder): ");

display(root);

printf("\n");

break;

case 5:

return 0;

default:

printf("Invalid choice!\n");

return 0;

47
 Advanced Data Structures Lab Manual

OUTPUT

Leftist Tree Operations

1. Insert

2. Delete (Delete Min)

3. Search

4. Display

5. Exit

Enter your choice: 1

Enter value: 10

Inserted successfully.

Enter your choice: 1

Enter value: 5

Inserted successfully.

Enter your choice: 1

48
 Advanced Data Structures Lab Manual

Enter value: 20

Inserted successfully.

Enter your choice: 1

Enter value: 3

Inserted successfully.

Enter your choice: 4

Leftist Tree (Preorder): 3 5 10 20

Enter your choice: 3

Enter value to search: 5

Element found.

Enter your choice: 2

Deleted element: 3

49
 Advanced Data Structures Lab Manual

Enter your choice: 4

Leftist Tree (Preorder): 5 10 20

Enter your choice: 5

CHAPTER 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

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

/* Structure for Binomial Heap Node */

struct Node {

int key;

50
 Advanced Data Structures Lab Manual

int degree;

struct Node* parent;

struct Node* child;

struct Node* sibling;

};

/* Create New Node */

struct Node* createNode(int key) {

struct Node* newNode =

(struct Node*)malloc(sizeof(struct Node));

newNode->key = key;

newNode->degree = 0;

51
 Advanced Data Structures Lab Manual

newNode->parent = NULL;

newNode->child = NULL;

newNode->sibling = NULL;

return newNode;

/* Merge Root Lists */

struct Node* mergeRootLists(struct Node* h1,

struct Node* h2) {

if (!h1) return h2;

if (!h2) return h1;

52
 Advanced Data Structures Lab Manual

struct Node* head = NULL;

struct Node** pos = &head;

while (h1 && h2) {

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

*pos = h1;

h1 = h1->sibling;

else {

*pos = h2;

h2 = h2->sibling;

pos = &((*pos)->sibling);

53
 Advanced Data Structures Lab Manual

*pos = (h1) ? h1 : h2;

return head;

/* Link Two Trees */

void linkTrees(struct Node* y,

struct Node* z) {

y->parent = z;

y->sibling = z->child;

z->child = y;

54
 Advanced Data Structures Lab Manual

z->degree++;

/* Union Two Heaps */

struct Node* unionHeaps(struct Node* h1,

struct Node* h2) {

struct Node* newHead =

mergeRootLists(h1, h2);

if (!newHead)

return NULL;

struct Node* prev = NULL;

struct Node* curr = newHead;

55
 Advanced Data Structures Lab Manual

struct Node* 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) {

56
 Advanced Data Structures Lab Manual

curr->sibling = next->sibling;

linkTrees(next, curr);

else {

if (!prev)

newHead = next;

else

prev->sibling = next;

linkTrees(curr, next);

curr = next;

57
 Advanced Data Structures Lab Manual

next = curr->sibling;

return newHead;

/* Insert */

struct Node* insert(struct Node* heap, int key) {

struct Node* node = createNode(key);

heap = unionHeaps(heap, node);

printf("Inserted successfully.\n");

58
 Advanced Data Structures Lab Manual

return heap;

/* Find Minimum */

struct Node* findMin(struct Node* heap) {

if (!heap)

return NULL;

struct Node* minNode = heap;

int min = heap->key;

struct Node* curr = heap->sibling;

while (curr) {

59
 Advanced Data Structures Lab Manual

if (curr->key < min) {

min = curr->key;

minNode = curr;

curr = curr->sibling;

return minNode;

/* Reverse List */

struct Node* reverseList(struct Node* node) {

60
 Advanced Data Structures Lab Manual

struct Node* prev = NULL;

struct Node* curr = node;

struct Node* next;

while (curr) {

curr->parent = NULL;

next = curr->sibling;

curr->sibling = prev;

prev = curr;

curr = next;

61
 Advanced Data Structures Lab Manual

return prev;

/* Extract Min */

struct Node* deleteMin(struct Node* heap) {

if (!heap) {

printf("Heap is empty!\n");

return NULL;

struct Node* minPrev = NULL;

struct Node* minNode = heap;

62
 Advanced Data Structures Lab Manual

struct Node* prev = NULL;

struct Node* curr = heap;

int min = curr->key;

while (curr) {

if (curr->key < min) {

min = curr->key;

minPrev = prev;

minNode = curr;

prev = curr;

63
 Advanced Data Structures Lab Manual

curr = curr->sibling;

// Remove minNode

if (!minPrev)

heap = minNode->sibling;

else

minPrev->sibling = minNode->sibling;

// Reverse children

struct Node* child =

reverseList(minNode->child);

free(minNode);

64
 Advanced Data Structures Lab Manual

heap = unionHeaps(heap, child);

printf("Minimum deleted.\n");

return heap;

/* Search */

struct Node* search(struct Node* heap, int key) {

if (!heap)

return NULL;

if (heap->key == key)

return heap;

65
 Advanced Data Structures Lab Manual

struct Node* found = search(heap->child, key);

if (found)

return found;

return search(heap->sibling, key);

/* Decrease Key */

void decreaseKey(struct Node* heap,

int oldKey, int newKey) {

if (newKey > oldKey) {

66
 Advanced Data Structures Lab Manual

printf("New key must be smaller.\n");

return;

struct Node* node = search(heap, oldKey);

if (!node) {

printf("Key not found.\n");

return;

node->key = newKey;

struct Node* y = node;

67
 Advanced Data Structures Lab Manual

struct Node* z = y->parent;

while (z && y->key < z->key) {

int temp = y->key;

y->key = z->key;

z->key = temp;

y = z;

z = y->parent;

printf("Key decreased.\n");

68
 Advanced Data Structures Lab Manual

/* Delete Key */

struct Node* deleteKey(struct Node* heap, int key) {

decreaseKey(heap, key, INT_MIN);

heap = deleteMin(heap);

return heap;

/* Display */

void display(struct Node* heap, int level) {

if (!heap)

return;

69
 Advanced Data Structures Lab Manual

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

printf(" ");

printf("%d\n", heap->key);

display(heap->child, level + 1);

display(heap->sibling, level);

/* Main */

int main() {

struct Node* heap = NULL;

70
 Advanced Data Structures Lab Manual

int choice, val;

while (1) {

printf("\n\nBinomial Heap Operations");

printf("\n1. Insert");

printf("\n2. Delete");

printf("\n3. Search");

printf("\n4. Display");

printf("\n5. Exit");

printf("\nEnter choice: ");

scanf("%d", &choice);

switch (choice) {

71
 Advanced Data Structures Lab Manual

case 1:

printf("Enter value: ");

scanf("%d", &val);

heap = insert(heap, val);

break;

case 2:

printf("Enter value to delete: ");

scanf("%d", &val);

heap = deleteKey(heap, val);

break;

72
 Advanced Data Structures Lab Manual

case 3:

printf("Enter value to search: ");

scanf("%d", &val);

if (search(heap, val))

printf("Element found.\n");

else

printf("Element not found.\n");

break;

case 4:

printf("Binomial Heap:\n");

display(heap, 0);

break;

73
 Advanced Data Structures Lab Manual

case 5:

return 0;

default:

printf("Invalid choice!\n");

return 0;

OUTPUT

Binomial Heap Operations

1. Insert

2. Delete

74
 Advanced Data Structures Lab Manual

3. Search

4. Display

5. Exit

Enter choice: 1

Enter value: 10

Inserted successfully.

Enter choice: 1

Enter value: 3

Inserted successfully.

Enter choice: 1

Enter value: 15

Inserted successfully.

75
 Advanced Data Structures Lab Manual

Enter choice: 1

Enter value: 6

Inserted successfully.

Enter choice: 4

Binomial Heap:

15

10

Enter choice: 3

Enter value to search: 6

Element found.

76
 Advanced Data Structures Lab Manual

Enter choice: 2

Enter value to delete: 6

Key decreased.

Minimum deleted.

Enter choice: 4

Binomial Heap:

10

15

Enter choice: 5

77
Advanced Data Structures Lab Manual

78