Holy Mary Institute of Technology & Science

(UGC - Autonomous)

[Link] - Computer Science and Engineering (R25)

ADVANCED DATA STRUCTURES LAB

(LAB - I)
Course Code: B3CS104PC

Lab Manual

Prepared By:
Mr. Jitendra Alaparthi
Associate Professor & Head, CSE
Holy Mary Institute of Technology & Science

Academic Year: 2025-26

Contents

1 Binary Search Tree Operations 2

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

3 B-Tree Operations 15

4 Min-Max Heap Operations 24

5 Leftist Tree Operations 33

6 Binomial Heap Operations 38

7 AVL Tree Operations 43

8 Red–Black Tree Operations 53

9 Dictionary Using Hashing 62

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

11 Brute-Force Pattern Matching Algorithm 74

12 Boyer–Moore Pattern Matching Algorithm 78

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

Problem Statement
Design and implement a menu-driven program in C that:

ˆ Inserts a key into a BST.

ˆ Deletes a key from the BST.
ˆ Searches for a key in the BST.
ˆ Displays the BST using inorder traversal.
Algorithm
BST Insertion
1. If the tree is empty, create a new node and make it the root.

2. Otherwise, compare the key with the root key.

3. If key is less than root key, recursively insert into the left subtree.

4. If key is greater than root key, recursively insert into the right subtree.

5. If key is equal, optionally ignore (no duplicates) or handle duplicates.

2
 Advanced Data Structures Lab Manual B3CS104PC
BST Search
1. If the current node is NULL, key is not found.

2. If key equals current node key, return success.

3. If key is less, search in the left subtree.

4. If key is greater, search in the right subtree.

BST Deletion
1. If node to delete is a leaf, simply remove it.

2. If node has one child, replace it with its child.

3. If node has two children:

3.1. Find the inorder successor (smallest in right subtree).

3.2. Copy its key to the current node.
3.3. Recursively delete the inorder successor node.

Program
1 #include <stdio.h>
2 #include <stdlib.h>
3

4 typedef struct Node {

5 int key;
6 struct Node *left, *right;
7 } Node;
8

9 Node* createNode(int key) {

10 Node *temp = (Node*)malloc(sizeof(Node));
11 temp->key = key;
12 temp->left = temp->right = NULL;
13 return temp;
14 }
15

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

17 if (root == NULL) return createNode(key);
18 if (key < root->key)
19 root->left = insert(root->left, key);

3
 Advanced Data Structures Lab Manual B3CS104PC
20 else if (key > root->key)
21 root->right = insert(root->right, key);
22 else
23 printf("Duplicate key %d ignored.\n", key);
24 return root;
25 }
26

27 Node* findMin(Node* root) {

28 while (root && root->left != NULL)
29 root = root->left;
30 return root;
31 }
32

33 Node* delete(Node* root, int key) {

34 if (root == NULL) {
35 printf("Key %d not found.\n", key);
36 return root;
37 }
38 if (key < root->key)
39 root->left = delete(root->left, key);
40 else if (key > root->key)
41 root->right = delete(root->right, key);
42 else {
43 // node found
44 if (root->left == NULL && root->right == NULL) {
45 free(root);
46 root = NULL;
47 } else if (root->left == NULL) {
48 Node *temp = root;
49 root = root->right;
50 free(temp);
51 } else if (root->right == NULL) {
52 Node *temp = root;
53 root = root->left;
54 free(temp);
55 } else {
56 Node *succ = findMin(root->right);
57 root->key = succ->key;
58 root->right = delete(root->right, succ->key);
59 }
60 }

4
 Advanced Data Structures Lab Manual B3CS104PC
61 return root;
62 }
63

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

65 if (root == NULL) return NULL;
66 if (key == root->key) return root;
67 if (key < root->key) return search(root->left, key);
68 return search(root->right, key);
69 }
70

71 void inorder(Node* root) {

72 if (root == NULL) return;
73 inorder(root->left);
74 printf("%d ", root->key);
75 inorder(root->right);
76 }
77

78 int main() {
79 Node *root = NULL;
80 int choice, key;
81 while (1) {
82 printf("\n--- BST Operations ---\n");
83 printf("1. Insert\n2. Delete\n3. Search\n4. Inorder
Traversal\n5. Exit\n");
84 printf("Enter choice: ");
85 if (scanf("%d", &choice) != 1) break;
86 switch (choice) {
87 case 1:
88 printf("Enter key to insert: ");
89 scanf("%d", &key);
90 root = insert(root, key);
91 break;
92 case 2:
93 printf("Enter key to delete: ");
94 scanf("%d", &key);
95 root = delete(root, key);
96 break;
97 case 3:
98 printf("Enter key to search: ");
99 scanf("%d", &key);
100 if (search(root, key))

5
 Advanced Data Structures Lab Manual B3CS104PC
101 printf("Key %d found in BST.\n", key);
102 else
103 printf("Key %d not found in BST.\n", key);
104 break;
105 case 4:
106 printf("Inorder Traversal: ");
107 inorder(root);
108 printf("\n");
109 break;
110 case 5:
111 exit(0);
112 default:
113 printf("Invalid choice.\n");
114 }
115 }
116 return 0;
117 }

Sample Input and Expected Output

Sample Input

1 50
1 30
1 70
1 20
1 40
4
3 40
2 30
4
5

Expected Output (conceptual)

Inorder Traversal: 20 30 40 50 70
Key 40 found in BST.
Inorder Traversal: 20 40 50 70

6
 Advanced Data Structures Lab Manual B3CS104PC
Result
The operations of insertion, deletion, and search on a Binary Search Tree were successfully
implemented and tested using C.

1.1 Viva Questions

*

1. What is a Binary Search Tree? State its properties. A Binary Search Tree
(BST) is a binary tree where each node has a key, and keys in the left subtree are
smaller while keys in the right subtree are larger. Both subtrees must also be valid
BSTs. This ordering property makes searching and updating efficient.

2. What is the time complexity of search in a BST in best and worst case?
The best case occurs when the key is found at the root, giving a time complexity
of O(1). The worst case occurs in a skewed BST (like a linked list), giving O(n).
For a balanced BST, average search time is O(log n).

3. How does deletion differ for nodes with zero, one, and two children? If
the node is a leaf (zero children), it is removed directly. If it has one child, the node
is replaced by its child. If it has two children, the inorder successor (or predecessor)
replaces its key, and the successor node is deleted recursively.

4. What is the relation between inorder traversal of a BST and sorted order
of keys? Inorder traversal visits nodes in the order: Left Subtree 
Root 
Right
Subtree. For a BST, this traversal produces keys in strictly increasing sorted order.
This property is often used to verify if a tree is a valid BST.

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

Objectives
ˆ Understand the divide-and-conquer strategy in Merge Sort and Quick Sort.
ˆ Understand heap-based selection strategy in Heap Sort.
ˆ Compare the time and space complexities of three major sorting algorithms.
ˆ Implement each algorithm in C and analyze differences.
Problem Statement
Write a C program that:

ˆ Reads an array of integers from the user.

ˆ Sorts the array using one of the following: Merge Sort, Heap Sort, or Quick Sort.
ˆ Displays the sorted array after the selected algorithm is applied.

8
 Advanced Data Structures Lab Manual B3CS104PC
Theory
Sorting is a fundamental operation in computer science. Among many available sorting
techniques, Merge Sort, Heap Sort, and Quick Sort are widely used due to their
performance and reliability.

Comparison of Three Sorting Algorithms

Algorithm Best Case Worst Case Space Complexity
Merge Sort O(n log n) O(n log n) O(n) (extra array)
Heap Sort O(n log n) O(n log n) O(1)
2
Quick Sort O(n log n) O(n ) (bad pivot) O(log n) (stack)

Algorithm
Merge Sort
Merge Sort uses the Divide and Conquer strategy:

1. Split the array into two halves recursively.

2. Sort each half.

3. Merge the two sorted halves into one sorted array.

Characteristics:

ˆ Stable sort.
ˆ Requires additional memory.
ˆ Consistent O(n log n) performance.
Heap Sort
Heap Sort uses a binary heap structure:

1. Convert the array into a max heap.

2. Swap the root (maximum element) with the last element.

3. Reduce heap size and heapify the root again.

Characteristics:

9
 Advanced Data Structures Lab Manual B3CS104PC
ˆ Not stable.
ˆ In-place sorting algorithm.
ˆ Consistent O(n log n) performance.
Quick Sort
Quick Sort also follows Divide and Conquer:

1. Select a pivot element.

2. Partition the array into two subarrays:

ˆ Elements smaller than pivot.

ˆ Elements greater than pivot.
3. Recursively sort the two partitions.

Characteristics:

ˆ Very fast in practice.

ˆ Worst case occurs when pivot is smallest/largest.
ˆ Uses in-place partitioning.
Program
Complete C program implementing all three sorting algorithms:
1 #include <stdio.h>
2

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

4 int n1 = m - l + 1;
5 int n2 = r - m;
6 int L[1000], R[1000];
7 int i, j, k;
8

9 for (i = 0; i < n1; i++) L[i] = a[l + i];

10 for (j = 0; j < n2; j++) R[j] = a[m + 1 + j];
11

12 i = 0; j = 0; k = l;
13 while (i < n1 && j < n2) {
14 if (L[i] <= R[j]) a[k++] = L[i++];

10
 Advanced Data Structures Lab Manual B3CS104PC
15 else a[k++] = R[j++];
16 }
17 while (i < n1) a[k++] = L[i++];
18 while (j < n2) a[k++] = R[j++];
19 }
20

21 void mergeSort(int a[], int l, int r) {

22 if (l < r) {
23 int m = (l + r) / 2;
24 mergeSort(a, l, m);
25 mergeSort(a, m + 1, r);
26 merge(a, l, m, r);
27 }
28 }
29

30 void swap(int *x, int *y) {

31 int t = *x; *x = *y; *y = t;
32 }
33

34 /* Heap Sort Helpers */

35 void heapify(int a[], int n, int i) {
36 int largest = i;
37 int l = 2 * i + 1;
38 int r = 2 * i + 2;
39 if (l < n && a[l] > a[largest]) largest = l;
40 if (r < n && a[r] > a[largest]) largest = r;
41 if (largest != i) {
42 swap(&a[i], &a[largest]);
43 heapify(a, n, largest);
44 }
45 }
46

47 void heapSort(int a[], int n) {

48 int i;
49 for (i = n / 2 - 1; i >= 0; i--)
50 heapify(a, n, i);
51 for (i = n - 1; i >= 0; i--) {
52 swap(&a[0], &a[i]);
53 heapify(a, i, 0);
54 }
55 }

11
 Advanced Data Structures Lab Manual B3CS104PC
56

57 /* Quick Sort Helpers */

58 int partition(int a[], int low, int high) {
59 int pivot = a[high];
60 int i = low - 1, j;
61 for (j = low; j < high; j++) {
62 if (a[j] <= pivot) {
63 i++;
64 swap(&a[i], &a[j]);
65 }
66 }
67 swap(&a[i + 1], &a[high]);
68 return i + 1;
69 }
70

71 void quickSort(int a[], int low, int high) {

72 if (low < high) {
73 int pi = partition(a, low, high);
74 quickSort(a, low, pi - 1);
75 quickSort(a, pi + 1, high);
76 }
77 }
78

79 void printArray(int a[], int n) {

80 for (int i = 0; i < n; i++) printf("%d ", a[i]);
81 printf("\n");
82 }
83

84 int main() {
85 int a[100], n, i, choice;
86 printf("Enter number of elements: ");
87 scanf("%d", &n);
88 printf("Enter %d elements:\n", n);
89 for (i = 0; i < n; i++) scanf("%d", &a[i]);
90

91 while (1) {
92 printf("\n1. Merge Sort\n2. Heap Sort\n3. Quick
Sort\n4. Exit\n");
93 printf("Enter choice: ");
94 scanf("%d", &choice);
95

12
 Advanced Data Structures Lab Manual B3CS104PC
96 if (choice == 4) break;
97

98 switch (choice) {
99 case 1:
100 mergeSort(a, 0, n - 1);
101 printf("Sorted array (Merge Sort): ");
102 printArray(a, n);
103 break;
104 case 2:
105 heapSort(a, n);
106 printf("Sorted array (Heap Sort): ");
107 printArray(a, n);
108 break;
109 case 3:
110 quickSort(a, 0, n - 1);
111 printf("Sorted array (Quick Sort): ");
112 printArray(a, n);
113 break;
114 default:
115 printf("Invalid choice.\n");
116 }
117 }
118 return 0;
119 }

Sample Input and Expected Output

Sample Input

n = 5
Elements: 5 1 4 2 8

Expected Output (for any sorting method)

1 2 4 5 8

Example Sorting Flow (Merge Sort)

Input: 5 1 4 2 8

Divide  [5 1 4] and [2 8]
Divide  [5 1] [4] and [2] [8]

13
 Advanced Data Structures Lab Manual B3CS104PC
Merge  [1 5 4] and [2 8]
Merge  [1 4 5 2 8]
Final  [1 2 4 5 8]

Result
Merge Sort, Heap Sort, and Quick Sort were implemented in C and their outputs vali-
dated. Each algorithm successfully sorted the given input array, demonstrating different
approaches to sorting.

Viva Questions (Expanded)

1. Explain the Divide and Conquer strategy used in Merge Sort.

2. Why does Merge Sort require additional memory?

3. Compare Quick Sort and Merge Sort in terms of space complexity.

4. What is the role of heapify() in Heap Sort?

5. Why can Quick Sort degrade to O(n2 )?

6. What pivot selection methods improve Quick Sort performance?

7. Why is Heap Sort not considered a stable sorting algorithm?

8. Which algorithm is best suited for linked lists? Why?

9. Explain the difference between internal and external sorting.

10. Which sorting algorithm is preferred in system libraries (C/C++) and why?

14
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.

Objective
The objectives of this experiment are:

ˆ To understand the structure and properties of B-Trees.

ˆ To implement scalable index structures suitable for external storage.
ˆ To perform insertion and searching with node splitting.
ˆ To understand how B-Trees maintain balanced height and ensure efficient disk ac-
cess.

Theory Background
What is a B-Tree?
A B-Tree is a multi-way search tree in which each node may contain multiple keys. It is
designed for disk-based or large-memory storage, minimizing disk accesses.
A B-Tree of minimum degree t has the following properties:

ˆ Every node (except root) has at least t − 1 keys.

ˆ Every node can have at most 2t − 1 keys.
ˆ Every internal node with k keys has k + 1 children.
15
 Advanced Data Structures Lab Manual B3CS104PC
ˆ The tree is height-balanced: all leaves occur at the same depth.
Applications of B-Trees
ˆ Database indexing (MySQL, PostgreSQL)
ˆ File systems (NTFS, EXT4)
ˆ Key-value stores and search engines
ˆ Large-scale storage requiring few disk I/O operations
Problem Statement
Develop a C program to:

ˆ Create a B-Tree of minimum degree t.

ˆ Insert keys into the B-Tree.
ˆ Search for a key in the B-Tree.
ˆ Delete a key (optional; outline included).
Algorithm (High Level)
Insertion Algorithm
1. If the root is full (2t − 1 keys), create a new root and split the old root.

2. Insert key into the correct child of the root.

3. Recursively move down, splitting full nodes on the traversal path.

Search Algorithm
1. Perform linear or binary search on the current node’s keys.

2. If the key is found, return the node.

3. If the node is a leaf, return NULL.

4. Select the appropriate child and continue search recursively.

16
 Advanced Data Structures Lab Manual B3CS104PC
Deletion Algorithm (Conceptual Overview)
B-Tree deletion is complex and involves multiple cases:

1. If key is in a leaf: simply remove it.

2. If key is in internal node:

ˆ Replace it with predecessor or successor.

ˆ Recursively delete from child node.
3. Ensure children have at least t − 1 keys:

ˆ Borrow from left or right sibling.

ˆ Or merge siblings if both have t − 1 keys.
These rules maintain the B-Tree’s structural constraints.

Program (Simplified B-Tree with Insert and Search)

1 #include <stdio.h>
2 #include <stdlib.h>
3

4 #define T 3 /* minimum degree */

5

6 typedef struct BTreeNode {

7 int keys[2*T-1];
8 struct BTreeNode *child[2*T];
9 int n;
10 int leaf;
11 } BTreeNode;
12

13 BTreeNode* createNode(int leaf) {

14 BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode))
;
15 node->leaf = leaf;
16 node->n = 0;
17 int i;
18 for (i = 0; i < 2*T; i++)
19 node->child[i] = NULL;
20 return node;
21 }
22

17
 Advanced Data Structures Lab Manual B3CS104PC
23 void traverse(BTreeNode *root) {
24 int i;
25 if (root == NULL) return;
26 for (i = 0; i < root->n; i++) {
27 if (!root->leaf)
28 traverse(root->child[i]);
29 printf("%d ", root->keys[i]);
30 }
31 if (!root->leaf)
32 traverse(root->child[i]);
33 }
34

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

36 int i = 0;
37 while (i < root->n && k > root->keys[i])
38 i++;
39

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

41 return root;
42

43 if (root->leaf)
44 return NULL;
45

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

47 }
48

49 void splitChild(BTreeNode *x, int i, BTreeNode *y) {

50 BTreeNode *z = createNode(y->leaf);
51 int j;
52

53 z->n = T - 1;
54

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

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

58 if (!y->leaf) {
59 for (j = 0; j < T; j++)
60 z->child[j] = y->child[j + T];
61 }
62

63 y->n = T - 1;

18
 Advanced Data Structures Lab Manual B3CS104PC
64

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

66 x->child[j + 1] = x->child[j];
67 x->child[i + 1] = z;
68

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

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

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

73 x->n = x->n + 1;
74 }
75

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

77 int i = x->n - 1;
78

79 if (x->leaf) {
80 while (i >= 0 && k < x->keys[i]) {
81 x->keys[i + 1] = x->keys[i];
82 i--;
83 }
84 x->keys[i + 1] = k;
85 x->n++;
86 }
87 else {
88 while (i >= 0 && k < x->keys[i])
89 i--;
90 i++;
91

92 if (x->child[i]->n == 2*T - 1) {
93 splitChild(x, i, x->child[i]);
94

95 if (k > x->keys[i])
96 i++;
97 }
98 insertNonFull(x->child[i], k);
99 }
100 }
101

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

103 if (root == NULL) {
104 root = createNode(1);

19
 Advanced Data Structures Lab Manual B3CS104PC
105 root->keys[0] = k;
106 root->n = 1;
107 return root;
108 }
109

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

111 BTreeNode *s = createNode(0);
112 s->child[0] = root;
113 splitChild(s, 0, root);
114

115 int i = 0;
116 if (k > s->keys[0])
117 i++;
118 insertNonFull(s->child[i], k);
119 return s;
120 }
121 else {
122 insertNonFull(root, k);
123 return root;
124 }
125 }
126

127 int main() {

128 BTreeNode *root = NULL;
129 int choice, key;
130

131 while (1) {

132 printf("\n--- B-Tree Operations (degree=%d) ---\n",
T);
133 printf("1. Insert\n2. Search\n3. Traverse\n4. Exit\
n");
134 printf("Enter choice: ");
135 scanf("%d", &choice);
136

137 switch (choice) {

138 case 1:
139 printf("Enter key to insert: ");
140 scanf("%d", &key);
141 root = insert(root, key);
142 break;
143

20
 Advanced Data Structures Lab Manual B3CS104PC
144 case 2:
145 printf("Enter key to search: ");
146 scanf("%d", &key);
147 if (root && search(root, key))
148 printf("Key %d found.\n", key);
149 else
150 printf("Key %d not found.\n", key);
151 break;
152

153 case 3:
154 printf("B-Tree (inorder-like traversal): ");
155 traverse(root);
156 printf("\n");
157 break;
158

159 case 4:
160 exit(0);
161

162 default:
163 printf("Invalid choice.\n");
164 }
165 }
166

167 return 0;
168 }

Sample Input and Expected Output

Input
Insert: 10 20 5 6 12 30 7 17
Traverse

Output
B-Tree (inorder-like traversal):
5 6 7 10 12 17 20 30

21
 Advanced Data Structures Lab Manual B3CS104PC
Observations
ˆ Node splits occurred when inserting keys into a full node.
ˆ The B-Tree remained balanced after every insertion.
ˆ Keys are always stored in sorted order within nodes.
ˆ Searches used binary-like navigation through children.
ˆ Height of the tree grows slowly due to high branching factor (2t children).
Advantages of B-Trees
ˆ Efficient for disk-based storage.
ˆ Logarithmic height, even for millions of entries.
ˆ Supports large block size and minimizes disk I/O.
ˆ Balanced tree; no rotations required (unlike AVL).
Time Complexity
ˆ Search: O(t log n)
ˆ Insertion: O(t log n)
ˆ Deletion: O(t log n)
ˆ Space: O(n)
Result
The B-Tree implementation successfully demonstrates insertion, search, node-splitting,
and traversal. Although deletion is conceptually discussed, the program focuses on inser-
tion and search operations, which are essential for understanding B-Tree structure and
behavior.

22
 Advanced Data Structures Lab Manual B3CS104PC
Viva Questions
1. What is a B-Tree? How does it differ from AVL or Red-Black Trees?

2. What is the minimum degree t in a B-Tree?

3. How many keys and children can a B-Tree node have?

4. What is the purpose of node splitting during insertion?

5. Why do B-Trees perform well on disk-based storage systems?

6. Explain the height property of a B-Tree.

7. How does searching in a B-Tree differ from searching in a BST?

8. What happens when attempting to insert into a full child?

9. What is the difference between B-Trees and B+ Trees?

10. Why do B-Trees maintain sorted keys within nodes?

11. What is the worst-case height of a B-Tree with n keys?

12. How does merge operation help during B-Tree deletion?

23
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).

Objective
The objective of this experiment is to understand:

ˆ How Min-Max Heaps support double-ended priority queue (DEPQ) operations

ˆ How min-priority and max-priority structures can coexist
ˆ Heapify procedures for min-heaps and max-heaps
ˆ Efficient extraction of smallest and largest elements
Theory Background
Double-Ended Priority Queue (DEPQ)
A double-ended priority queue is an abstract data type that supports:

24
 Advanced Data Structures Lab Manual B3CS104PC
ˆ Delete-Min: Remove the element with the lowest priority
ˆ Delete-Max: Remove the element with the highest priority
ˆ Insert: Insert an element with a given priority
ˆ Find-Min and Find-Max: Retrieve minimum and maximum elements
A Min-Max Heap is an efficient implementation of a DEPQ.

Min-Max Heap
A Min-Max Heap is a complete binary tree in which:

ˆ Even levels satisfy min-heap property

ˆ Odd levels satisfy max-heap property
Thus, both minimum and maximum can be found efficiently:

Min = A[0], Max = max(A[1], A[2])

Simplified Two-Heap Approach

Since full Min-Max Heap implementation is complex, here we simulate DEPQ behavior
using:

ˆ A Min Heap for extracting minimum efficiently

ˆ A Max Heap for extracting maximum efficiently
Limitations:

ˆ Two heaps must store duplicate values

ˆ Insert operations require rebuilding both heaps (less efficient)
ˆ Delete-Min and Delete-Max are heap-specific, not synchronized
However, this simplified approach effectively demonstrates core DEPQ principles.

Algorithms
Insertion Algorithm
1. Insert the key into both the Min Heap and Max Heap.

2. Re-heapify both heaps bottom-up using heapify-down.

25
 Advanced Data Structures Lab Manual B3CS104PC
Delete-Min Algorithm
1. The minimum element is the root of the Min Heap.

2. Replace root with last element.

3. Reduce heap size.

4. Apply minHeapify to restore heap structure.

Delete-Max Algorithm
1. The maximum element is the root of the Max Heap.

2. Replace root with last element.

3. Reduce heap size.

4. Apply maxHeapify.

Search Algorithm
Perform a linear search in the Min Heap array:

O(n)

Program (Two-Heaps Based Implementation)

1 #include <stdio.h>
2 #include <stdlib.h>
3

4 #define MAX 100

5

6 typedef struct {
7 int minHeap[MAX];
8 int maxHeap[MAX];
9 int size;
10 } MinMax;
11

12 void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }

13

14 /* Min heapify (down) */

15 void minHeapify(int a[], int n, int i) {
16 int l = 2*i+1, r = 2*i+2, smallest = i;

26
 Advanced Data Structures Lab Manual B3CS104PC
17 if (l < n && a[l] < a[smallest]) smallest = l;
18 if (r < n && a[r] < a[smallest]) smallest = r;
19 if (smallest != i) {
20 swap(&a[i], &a[smallest]);
21 minHeapify(a, n, smallest);
22 }
23 }
24

25 /* Max heapify (down) */

26 void maxHeapify(int a[], int n, int i) {
27 int l = 2*i+1, r = 2*i+2, largest = i;
28 if (l < n && a[l] > a[largest]) largest = l;
29 if (r < n && a[r] > a[largest]) largest = r;
30 if (largest != i) {
31 swap(&a[i], &a[largest]);
32 maxHeapify(a, n, largest);
33 }
34 }
35

36 void insertKey(MinMax *mm, int key) {

37 int i;
38 int n = mm->size;
39 if (n == MAX) {
40 printf("Overflow.\n");
41 return;
42 }
43 mm->minHeap[n] = key;
44 mm->maxHeap[n] = key;
45 mm->size++;
46

47 /* build heaps again (simple but O(n log n)) */

48 n = mm->size;
49 for (i = n/2 - 1; i >= 0; i--) {
50 minHeapify(mm->minHeap, n, i);
51 maxHeapify(mm->maxHeap, n, i);
52 }
53 }
54

55 int extractMin(MinMax *mm) {

56 int n = mm->size;
57 if (n == 0) return -1;

27
 Advanced Data Structures Lab Manual B3CS104PC
58 int root = mm->minHeap[0];
59 mm->minHeap[0] = mm->minHeap[n-1];
60 mm->size--;
61 minHeapify(mm->minHeap, mm->size, 0);
62 return root;
63 }
64

65 int extractMax(MinMax *mm) {

66 int n = mm->size;
67 if (n == 0) return -1;
68 int root = mm->maxHeap[0];
69 mm->maxHeap[0] = mm->maxHeap[n-1];
70 mm->size--;
71 maxHeapify(mm->maxHeap, mm->size, 0);
72 return root;
73 }
74

75 int searchKey(MinMax *mm, int key) {

76 int i;
77 for (i = 0; i < mm->size; i++)
78 if (mm->minHeap[i] == key) return 1;
79 return 0;
80 }
81

82 void printHeaps(MinMax *mm) {

83 int i;
84 printf("MinHeap: ");
85 for (i = 0; i < mm->size; i++) printf("%d ", mm->
minHeap[i]);
86 printf("\nMaxHeap: ");
87 for (i = 0; i < mm->size; i++) printf("%d ", mm->
maxHeap[i]);
88 printf("\n");
89 }
90

91 int main() {
92 MinMax mm;
93 [Link] = 0;
94 int choice, key, x;
95

96 while (1) {

28
 Advanced Data Structures Lab Manual B3CS104PC
97 printf("\n1. Insert\n2. Extract Min\n3. Extract Max
\n");
98 printf("4. Search\n5. Print Heaps\n6. Exit\n");
99 printf("Enter choice: ");
100 scanf("%d", &choice);
101

102 switch (choice) {

103 case 1:
104 printf("Enter key: ");
105 scanf("%d", &key);
106 insertKey(&mm, key);
107 break;
108

109 case 2:
110 x = extractMin(&mm);
111 if (x == -1) printf("Heap empty.\n");
112 else printf("Min = %d\n", x);
113 break;
114

115 case 3:
116 x = extractMax(&mm);
117 if (x == -1) printf("Heap empty.\n");
118 else printf("Max = %d\n", x);
119 break;
120

121 case 4:
122 printf("Enter key to search: ");
123 scanf("%d", &key);
124 if (searchKey(&mm, key)) printf("Key found.\n")
;
125 else printf("Key not found.\n");
126 break;
127

128 case 5:
129 printHeaps(&mm);
130 break;
131

132 case 6:
133 exit(0);
134

135 default:

29
 Advanced Data Structures Lab Manual B3CS104PC
136 printf("Invalid choice.\n");
137 }
138 }
139 return 0;
140 }

Sample Input/Output
Input
1
Enter key: 40
1
Enter key: 10
1
Enter key: 80
1
Enter key: 5
5
2
3
5

Output
MinHeap: 5 10 80 40
MaxHeap: 80 40 10 5
Min = 5
Max = 80
MinHeap: 10 40 80
MaxHeap: 40 10 5

Observations
ˆ The minimum value is always at the root of the Min Heap.
ˆ The maximum value is always at the root of the Max Heap.
ˆ Insert operation requires heap reconstruction, making the approach less optimal.

30
 Advanced Data Structures Lab Manual B3CS104PC
ˆ Search operation is linear because heap property does not support binary search.
ˆ The two-heap method demonstrates double-ended priority queue behavior but is
not a true Min-Max Heap.

Time Complexity Analysis

ˆ Insert: O(n log n) (due to rebuilding both heaps)
ˆ Extract-Min: O(log n)
ˆ Extract-Max: O(log n)
ˆ Search: O(n)
Advantages and Limitations
Advantages
ˆ Easy to implement
ˆ Demonstrates DEPQ concept
ˆ Useful for teaching heaps and priority queues
Limitations
ˆ Duplicate storage doubles memory usage
ˆ Insert is costly compared to real Min-Max Heap
ˆ Min and Max heaps can become unsynchronized in advanced use cases
Result
A Min-Max priority queue was implemented using two heaps (Min Heap and Max Heap).
Operations such as insertion, deletion of minimum, deletion of maximum, and search
were successfully performed and verified.

31
 Advanced Data Structures Lab Manual B3CS104PC
Viva Questions
1. What is a Min-Max Heap? How is it different from Min Heap or Max
Heap?
A Min-Max Heap supports both delete-min and delete-max operations efficiently,
unlike a normal heap which supports only one of them.

2. What operations does a double-ended priority queue support?

It supports insertion, find-min, find-max, delete-min, and delete-max.

3. What are the time complexities of insert and delete operations in a heap?
Insert: O(log n), Delete-min and delete-max: O(log n).

4. Why is the Min-Max Heap useful?

It combines advantages of both min and max heaps to handle priority queues with
two extremes efficiently.

5. What is the limitation of using two separate heaps?

They store duplicate data and require full rebuild on every insertion.

32
Chapter 5

Leftist Tree Operations

Aim
To implement the core operations of a Leftist Tree (also called a Leftist Heap), namely:
ˆ Insertion of a key
ˆ Deletion of the minimum element (Delete-Min)
ˆ Searching for a key
ˆ Displaying the heap (Inorder traversal)
using the merge-based leftist heap implementation.

Objective
The purpose of this experiment is to understand:
ˆ How Leftist Trees maintain structural properties to support efficient merging
ˆ How merge operations form the basis of insert and delete-min
ˆ How null-path length (NPL) influences the structure of the tree
ˆ How Leftist Trees compare with other priority queue structures like binary heaps
Theory Background
Leftist Tree
A Leftist Tree is a variant of a min-heap that is explicitly designed to make the merge
operation efficient.
Each node in a Leftist Heap stores:

33
 Advanced Data Structures Lab Manual B3CS104PC
ˆ Key value
ˆ Left and right children
ˆ Null Path Length (NPL), also called dist
Null Path Length (NPL)
The Null Path Length of a node is defined as:

NPL(x) = length of the shortest path from x to a leaf or null child

For any node in a Leftist Heap, the leftist property must be maintained:

NPL(left child) ≥ NPL(right child)

Leftist Property
A Leftist Tree always leans to the left, ensuring the shortest null path is always on the
right side. This structure ensures:

Merge operation is efficient: O(log n)

Operations
1. Merge The fundamental operation. Algorithm:

1. Compare roots; the smaller key becomes the new root.

2. Recursively merge the right subtree of the root with the other heap.

3. Swap children if NPL(left) ¡ NPL(right) to maintain leftist property.

4. Update NPL value.

2. Insertion Insertion is done by:

insert(H, x) = merge(H, {x})

3. Delete-Min Deletion removes the root node:

1. Remove root and free memory.

2. Merge its left and right subtrees.

4. Search Search is performed using standard binary-tree traversal.

34
 Advanced Data Structures Lab Manual B3CS104PC
Algorithm
Algorithm for Merge
1. If either heap is empty, return the other.

2. Ensure the root with the smaller key becomes the new root.

3. Recursively merge right subtree of root with the other heap.

4. If leftist property violated, swap children.

5. Update NPL.

Algorithm for Insertion

1. Create a single-node heap.

2. Merge it with existing heap.

Algorithm for Delete-Min

1. Save root value as minimum.

2. Merge left and right subtrees.

3. Return merged heap.

Algorithm for Search

1. If node is NULL, return false.

2. If key matches, success.

3. If key ¡ node’s key, stop search (min-heap property).

4. Else, search both children.

Program
(The C program remains unchanged.)
1 <same code here>

35
 Advanced Data Structures Lab Manual B3CS104PC
Sample Input and Output
Sample Input
1
Enter key: 30
1
Enter key: 10
1
Enter key: 40
1
Enter key: 5
4
2
4

Sample Output
Inorder: 5 10 30 40
Min deleted: 5
Inorder: 10 30 40

Observations
ˆ The heap maintained leftist property by swapping children where needed.
ˆ Insertion internally called the merge operation, ensuring logarithmic performance.
ˆ Delete-min operation reduced heap height by merging the root’s subtrees.
ˆ Search stops early if key ¡ current node (due to heap property).
ˆ The right spine of a leftist heap is always the shortest.
Time Complexity Analysis
ˆ Merge: O(log n)
ˆ Insert: O(log n)
ˆ Delete-Min: O(log n)
ˆ Search: O(n) (heap property does not guarantee BST order)
36
 Advanced Data Structures Lab Manual B3CS104PC
Result
The operations of a Leftist Tree — merge, insertion, delete-min, search, and traversal —
were successfully implemented using recursive algorithms. The output verifies correctness
of the leftist property and null-path lengths.

Viva Questions
1. What is the null path length (NPL) in a Leftist Tree?
It is the length of the shortest path from a node to a leaf or null child.

2. Why are Leftist Heaps efficient for merging?

The right spine is always the shortest due to the leftist property. Thus, merge depth
is logarithmic.

3. Compare Leftist Heap and Binary Heap.

Leftist Heap supports fast merge (O(log n)), while binary heap merge is O(n).
Binary Heap has predictable array structure, Leftist Heap is pointer-based.

4. What is the purpose of swapping left and right children?

To enforce the leftist property: NPL(left) ¿= NPL(right).

5. Where are Leftist Heaps used?

In applications requiring frequent priority queue merges: network optimization,
event simulation, job scheduling.

37
Chapter 6

Binomial Heap Operations

Aim
To develop and implement a program in C for performing the following operations using
a Binomial Heap:

ˆ Insertion of a key
ˆ Deletion of the minimum element (Delete-Min)
ˆ Searching for an element
ˆ Displaying the heap in Binomial Tree format
Objective
Binomial Heaps are an essential data structure in priority queue implementations. They
support efficient merging (union) of heaps, unlike binary heaps. This experiment helps
students:

ˆ Understand binomial tree properties

ˆ Learn heap operations involving merging and linking
ˆ Implement the delete-min operation efficiently
ˆ Analyze recursive traversal for search
Theory Background
Binomial Tree
A Binomial Tree Bk of order k is defined recursively as:

38
 Advanced Data Structures Lab Manual B3CS104PC
ˆB 0 is a single node.

ˆB k is made by linking two Bk−1 trees, making one the leftmost child of the other.

Properties:

ˆ Height of B is k.
k

ˆ Number of nodes is 2 . k

ˆ Exactly
nodes are at depth i.

k
i

Binomial Heap
A Binomial Heap is a collection of Binomial Trees satisfying:

1. Min-heap property: Parent key ≤ children’s keys.

2. At most one binomial tree of any degree.

3. Trees are linked similar to binary representation of heap size.

Major Operations
1. Union Operation The most important operation:

ˆ Merge root lists in increasing order of degree.

ˆ Resolve duplicate degrees by linking trees.
2. Insert Operation Insert = Union of existing heap with a new singleton binomial
tree.
3. Delete-Min Steps:

1. Locate minimum root.

2. Remove it from the root list.

3. Reverse its children list to form a new heap.

4. Union this new heap with the remaining heap.

4. Search Operation Search operation is recursive over:

ˆ sibling pointers
ˆ child pointers

39
 Advanced Data Structures Lab Manual B3CS104PC
Algorithm
1. Insertion
1. Create a single-node binomial tree.

2. Merge it into the existing root list.

3. Resolve duplicate degrees by linking.

2. Delete-Min
1. Traverse root list and find the minimum key.

2. Remove that tree root.

3. Reverse the order of its children.

4. Merge this reversed list with remaining heap.

3. Search
ˆ Recursively search the key in:
1. Current root
2. Child subtree
3. Sibling nodes

4. Print Heap
Print each binomial tree as:
Bk : root → children

Program
(The C program remains exactly as provided by the user.)
1 <same program code here>

40
 Advanced Data Structures Lab Manual B3CS104PC
Sample Input/Output
Input
1
Enter key: 20
1
Enter key: 5
1
Enter key: 30
4
2
4

Output
B0: 5
B1: 5 20
Min deleted: 5
B1: 20 30

Observations
ˆ Binomial Heap construction is dependent on binary representation of heap size.
ˆ Insert operation frequently triggers union-heaps mechanism.
ˆ Delete-Min efficiently removes minimum using list reversal of children.
ˆ Search operation is recursive across sibling and child trees.
ˆ At all times, heap maintains at most one tree of each degree.
Time Complexity Analysis
ˆ Insert: O(log n)
ˆ Delete-Min: O(log n)
ˆ Search: O(n)
ˆ Union: O(log n)

41
 Advanced Data Structures Lab Manual B3CS104PC
Result
The operations of a Binomial Heap—namely insertion, deletion of minimum, search, and
printing the heap—were successfully implemented. The program demonstrates correct
construction and maintenance of binomial trees with proper linking and merging.

Viva Questions
1. What is a Binomial Heap? How is it different from a Binary Heap?
A Binomial Heap is a collection of binomial trees that supports efficient merging.
Binary heaps cannot merge in O(log n); binomial heaps can.

2. Explain the Union operation in a Binomial Heap.

Union merges root lists in sorted degree order and repeatedly links trees with iden-
tical degrees to maintain uniqueness.

3. Why is the Delete-Min operation efficient in Binomial Heaps?

Delete-Min removes a root tree and merges its reversed children in O(log n) time.

4. What is the structure of a Binomial Tree Bk ?

Bk has 2k nodes, height k, and exactly one node of degree k.

5. What are real applications of Binomial Heaps?

Priority queues, Dijkstra’s shortest path, scheduling algorithms, real-time job pri-
ority management.

42
Chapter 7

AVL Tree Operations

Aim
To design and implement insertion, deletion, and search operations on an AVL Tree in
C, ensuring the tree remains height-balanced after each modification.

Problem Statement
An AVL Tree (named after Adelson-Velsky and Landis) is a self-balancing Binary Search
Tree where the height difference between the left and right subtrees (called the Balance
Factor) is always maintained between −1 and +1. The goal of this experiment is to:
ˆ Insert nodes into an AVL Tree
ˆ Delete a node from an AVL Tree
ˆ Search for a key in the AVL Tree
ˆ Automatically rebalance the tree using rotations
ˆ Display the tree using preorder traversal
Description
The AVL Tree ensures that the height of the binary search tree remains logarithmic,
guaranteeing O(log n) search, insertion, and deletion times.

Balance Factor
The Balance Factor of a node is defined as:

BF = height(lef t subtree) − height(right subtree)

43
 Advanced Data Structures Lab Manual B3CS104PC
Valid values:
BF = −1, 0, +1

When the balance factor goes beyond this range, rotations are performed.

Types of Rotations
ˆ LL Rotation (Right Rotation): Left-heavy subtree.
ˆ RR Rotation (Left Rotation): Right-heavy subtree.
ˆ LR Rotation (Left-Right): Left child right-heavy.
ˆ RL Rotation (Right-Left): Right child left-heavy.
These rotations restructure the AVL Tree to restore balance.

Key Concepts
ˆ AVL tree keeps a height field in each node.
ˆ After every insertion or deletion, heights are updated bottom-up.
ˆ If imbalance is detected, an appropriate rotation is applied.
Algorithm
1. Insertion Algorithm
1. Insert the key as in a normal BST.

2. Update height of the ancestor nodes.

3. Compute balance factor:

BF = height(lef t) − height(right)

4. If imbalance occurs, apply rotations based on cases:

ˆ LL Case  Right Rotation

ˆ RR Case  Left Rotation
ˆ LR Case  Left Rotate child, then Right Rotate parent
ˆ RL Case  Right Rotate child, then Left Rotate parent
44
 Advanced Data Structures Lab Manual B3CS104PC
2. Deletion Algorithm
1. Delete the node similar to BST deletion.

2. If node has two children, replace with inorder successor.

3. Update height of current node.

4. Check for imbalance and apply appropriate rotations.

3. Search Algorithm
1. Compare the key with current node.

2. Move left or right based on comparison.

3. If found, return the node; otherwise return NULL.

4. Traversal
Preorder traversal prints:

root, lef t subtree, right subtree

Program
1 #include <stdio.h>
2 #include <stdlib.h>
3

4 typedef struct AVLNode {

5 int key;
6 struct AVLNode *left, *right;
7 int height;
8 } AVLNode;
9

10 // Get height of node

11 int height(AVLNode *n) {
12 return n ? n->height : 0;
13 }
14

15 // Utility to get maximum of two integers

16 int max(int a, int b) { return a > b ? a : b; }
17

45
 Advanced Data Structures Lab Manual B3CS104PC
18 // Create a new AVL Node
19 AVLNode* createNode(int key) {
20 AVLNode *n = (AVLNode*)malloc(sizeof(AVLNode));
21 n->key = key;
22 n->left = n->right = NULL;
23 n->height = 1;
24 return n;
25 }
26

27 // Right Rotate
28 AVLNode* rightRotate(AVLNode *y) {
29 AVLNode *x = y->left;
30 AVLNode *T2 = x->right;
31

32 x->right = y;
33 y->left = T2;
34

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

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

38 return x;
39 }
40

41 // Left Rotate
42 AVLNode* leftRotate(AVLNode *x) {
43 AVLNode *y = x->right;
44 AVLNode *T2 = y->left;
45

46 y->left = x;
47 x->right = T2;
48

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

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

52 return y;
53 }
54

55 // Get Balance Factor

56 int getBalance(AVLNode *n) {
57 if (!n) return 0;
58 return height(n->left) - height(n->right);

46
 Advanced Data Structures Lab Manual B3CS104PC
59 }
60

61 // Insert into AVL Tree

62 AVLNode* insert(AVLNode *root, int key) {
63 if (!root) return createNode(key);
64

65 if (key < root->key)

66 root->left = insert(root->left, key);
67 else if (key > root->key)
68 root->right = insert(root->right, key);
69 else
70 return root;
71

72 root->height = max(height(root->left), height(root->

right)) + 1;
73

74 int balance = getBalance(root);

75

76 // LL Case
77 if (balance > 1 && key < root->left->key)
78 return rightRotate(root);
79

80 // RR Case
81 if (balance < -1 && key > root->right->key)
82 return leftRotate(root);
83

84 // LR Case
85 if (balance > 1 && key > root->left->key) {
86 root->left = leftRotate(root->left);
87 return rightRotate(root);
88 }
89

90 // RL Case
91 if (balance < -1 && key < root->right->key) {
92 root->right = rightRotate(root->right);
93 return leftRotate(root);
94 }
95

96 return root;
97 }
98

47
 Advanced Data Structures Lab Manual B3CS104PC
99 // Get Inorder Successor
100 AVLNode* minValueNode(AVLNode *node) {
101 AVLNode *current = node;
102 while (current->left) current = current->left;
103 return current;
104 }
105

106 // Delete from AVL Tree

107 AVLNode* deleteNode(AVLNode *root, int key) {
108 if (!root) return root;
109

110 if (key < root->key)

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

113 else if (key > root->key)

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

116 else {
117 if (!root->left || !root->right) {
118 AVLNode *temp = root->left ? root->left : root
->right;
119

120 if (!temp) {
121 temp = root;
122 root = NULL;
123 } else {
124 *root = *temp;
125 }
126 free(temp);
127 }
128 else {
129 AVLNode *temp = minValueNode(root->right);
130 root->key = temp->key;
131 root->right = deleteNode(root->right, temp->key
);
132 }
133 }
134

135 if (!root) return root;

136

48
 Advanced Data Structures Lab Manual B3CS104PC
137 root->height = max(height(root->left), height(root->
right)) + 1;
138 int balance = getBalance(root);
139

140 // LL Case
141 if (balance > 1 && getBalance(root->left) >= 0)
142 return rightRotate(root);
143

144 // LR Case
145 if (balance > 1 && getBalance(root->left) < 0) {
146 root->left = leftRotate(root->left);
147 return rightRotate(root);
148 }
149

150 // RR Case
151 if (balance < -1 && getBalance(root->right) <= 0)
152 return leftRotate(root);
153

154 // RL Case
155 if (balance < -1 && getBalance(root->right) > 0) {
156 root->right = rightRotate(root->right);
157 return leftRotate(root);
158 }
159

160 return root;

161 }
162

163 // Search
164 AVLNode* search(AVLNode *root, int key) {
165 if (!root) return NULL;
166 if (key == root->key) return root;
167 if (key < root->key) return search(root->left, key);
168 return search(root->right, key);
169 }
170

171 // Preorder Traversal

172 void preorder(AVLNode *root) {
173 if (!root) return;
174 printf("%d ", root->key);
175 preorder(root->left);
176 preorder(root->right);

49
 Advanced Data Structures Lab Manual B3CS104PC
177 }
178

179 int main() {

180 AVLNode *root = NULL;
181 int choice, key;
182

183 while (1) {

184 printf("\n1. Insert\n2. Delete\n3. Search\n4.
Preorder\n5. Exit\n");
185 printf("Enter choice: ");
186 scanf("%d", &choice);
187

188 switch (choice) {

189 case 1:
190 printf("Enter key: ");
191 scanf("%d", &key);
192 root = insert(root, key);
193 break;
194

195 case 2:
196 printf("Enter key: ");
197 scanf("%d", &key);
198 root = deleteNode(root, key);
199 break;
200

201 case 3:
202 printf("Enter key: ");
203 scanf("%d", &key);
204 printf(search(root, key) ? "Found\n" : "Not
found\n");
205 break;
206

207 case 4:
208 printf("Preorder: ");
209 preorder(root);
210 printf("\n");
211 break;
212

213 case 5:
214 exit(0);
215 }

50
 Advanced Data Structures Lab Manual B3CS104PC
216 }
217 return 0;
218 }

Sample Input
1
Enter key: 30
1
Enter key: 20
1
Enter key: 40
1
Enter key: 10
4

Expected Output
Preorder: 30 20 10 40

Observations
ˆ Insertions that caused imbalance triggered LL, RR, LR, or RL rotations.
ˆ After every insertion or deletion, node heights are recalculated.
ˆ AVL Tree ensures height remains O(log n).
ˆ Preorder traversal displays structure accurately after rotations.
Result
The AVL Tree was successfully implemented including insertion, deletion, search, and
preorder traversal. The tree maintained its balance through appropriate rotations after
each update operation.

51
 Advanced Data Structures Lab Manual B3CS104PC
Viva Questions
1. What is the balance factor in an AVL tree?
It is the difference between the heights of the left and right subtrees:

BF = height(lef t) − height(right)

2. Explain LL, RR, LR, and RL rotations.

LL  Right rotation, RR  Left rotation, LR  Left rotation on child then right
rotation, RL  Right rotation on child then left rotation.

3. Compare AVL trees and Red–Black trees.

AVL trees are more strictly balanced; height is smaller. Red–Black trees allow slight
imbalance but provide faster insertion/deletion in practice.

4. Why is AVL tree height always logarithmic?

Because rebalancing is enforced at every insert/delete.

5. In which applications AVL trees are preferred?

Databases, in-memory indexing, and search-heavy systems needing fast lookups.

52
Chapter 8

Red–Black Tree Operations

Aim
To design and implement insertion, fix-up, and search operations of a Red–Black Tree
(RBT) in C, ensuring that the Red–Black Tree properties remain satisfied after each
insertion.

Problem Statement
A Red–Black Tree is a self-balancing binary search tree that guarantees O(log n) time
complexity for searching, insertion, and deletion. The objective of this experiment is to:
ˆ Insert keys into an RBT
ˆ Perform search on an RBT
ˆ Apply rotations and recoloring to maintain RBT properties
ˆ Display the inorder traversal with node colors
Description
Red–Black Trees balance themselves using color properties and rotations. They are widely
used in:
ˆ STL map/set (C++)
ˆ Linux kernel process scheduler
ˆ Java TreeMap, TreeSet
ˆ Memory management modules
Each node is either RED or BLACK, and NIL (leaf) nodes are always BLACK.

53
 Advanced Data Structures Lab Manual B3CS104PC
Red–Black Tree Properties
1. Every node is either RED or BLACK.

2. The root node is always BLACK.

3. Every leaf (NIL pointer) is BLACK.

4. RED nodes cannot have RED parents (no two consecutive REDs).

5. Every path from a node to its descendant NIL nodes contains the same number of
BLACK nodes.

Balancing Techniques
ˆ Left Rotation – pushes heavier left subtree downward.
ˆ Right Rotation – pushes heavier right subtree downward.
ˆ Recoloring – flips colors to maintain Black-Height.
ˆ Fix-Up – applied after insertion to restore RBT properties.
Algorithm
1. Insertion Algorithm
1. Insert new node like in a regular BST (color = RED).

2. If parent is BLACK, no violation, done.

3. If parent is RED, violations occur:

(a) If uncle is RED  Recolor parent, uncle, and grandparent.

(b) If uncle is BLACK  Perform rotations + recoloring.

4. Ensure root is BLACK at end.

2. Search Algorithm
1. Compare key with root.

2. If key matches, return node.

3. Recursively search left or right subtree.

4. If NIL reached, key not found.

54
 Advanced Data Structures Lab Manual B3CS104PC
3. Inorder Traversal
Displays nodes in sorted order with colors:

10(B) 15(R) 20(B) ...

Program (Insertion, Fix-Up, Search, Inorder)

1 #include <stdio.h>
2 #include <stdlib.h>
3

4 typedef enum { RED, BLACK } Color;

5

6 typedef struct RBNode {

7 int key;
8 Color color;
9 struct RBNode *left, *right, *parent;
10 } RBNode;
11

12 RBNode *NIL = NULL;

13 RBNode *root = NULL;
14

15 RBNode* createNode(int key) {

16 RBNode *n = (RBNode*)malloc(sizeof(RBNode));
17 n->key = key;
18 n->color = RED;
19 n->left = n->right = n->parent = NIL;
20 return n;
21 }
22

23 // Left Rotation
24 void leftRotate(RBNode **root, RBNode *x) {
25 RBNode *y = x->right;
26

27 x->right = y->left;
28 if (y->left != NIL) y->left->parent = x;
29

30 y->parent = x->parent;
31 if (x->parent == NIL)
32 *root = y;
33 else if (x == x->parent->left)
34 x->parent->left = y;

55
 Advanced Data Structures Lab Manual B3CS104PC
35 else
36 x->parent->right = y;
37

38 y->left = x;
39 x->parent = y;
40 }
41

42 // Right Rotation
43 void rightRotate(RBNode **root, RBNode *y) {
44 RBNode *x = y->left;
45

46 y->left = x->right;
47 if (x->right != NIL) x->right->parent = y;
48

49 x->parent = y->parent;
50 if (y->parent == NIL)
51 *root = x;
52 else if (y == y->parent->left)
53 y->parent->left = x;
54 else
55 y->parent->right = x;
56

57 x->right = y;
58 y->parent = x;
59 }
60

61 // Fix violations after insertion

62 void insertFixup(RBNode **root, RBNode *z) {
63 while (z->parent->color == RED) {
64

65 if (z->parent == z->parent->parent->left) {
66

67 RBNode *y = z->parent->parent->right;
68

69 if (y->color == RED) {
70 z->parent->color = BLACK;
71 y->color = BLACK;
72 z->parent->parent->color = RED;
73 z = z->parent->parent;
74 }
75 else {

56
 Advanced Data Structures Lab Manual B3CS104PC
76 if (z == z->parent->right) {
77 z = z->parent;
78 leftRotate(root, z);
79 }
80 z->parent->color = BLACK;
81 z->parent->parent->color = RED;
82 rightRotate(root, z->parent->parent);
83 }
84 }
85 else {
86

87 RBNode *y = z->parent->parent->left;
88

89 if (y->color == RED) {
90 z->parent->color = BLACK;
91 y->color = BLACK;
92 z->parent->parent->color = RED;
93 z = z->parent->parent;
94 }
95 else {
96 if (z == z->parent->left) {
97 z = z->parent;
98 rightRotate(root, z);
99 }
100 z->parent->color = BLACK;
101 z->parent->parent->color = RED;
102 leftRotate(root, z->parent->parent);
103 }
104 }
105 }
106 (*root)->color = BLACK;
107 }
108

109 // Insert into Red-Black Tree

110 void insertRB(RBNode **root, int key) {
111 RBNode *z = createNode(key);
112 RBNode *y = NIL;
113 RBNode *x = *root;
114

115 while (x != NIL) {

116 y = x;

57
 Advanced Data Structures Lab Manual B3CS104PC
117 if (z->key < x->key)
118 x = x->left;
119 else
120 x = x->right;
121 }
122

123 z->parent = y;
124 if (y == NIL)
125 *root = z;
126 else if (z->key < y->key)
127 y->left = z;
128 else
129 y->right = z;
130

131 z->left = z->right = NIL;

132 insertFixup(root, z);
133 }
134

135 // Search in RBT

136 RBNode* searchRB(RBNode *root, int key) {
137 if (root == NIL || root == NULL) return NIL;
138 if (key == root->key) return root;
139 if (key < root->key)
140 return searchRB(root->left, key);
141 return searchRB(root->right, key);
142 }
143

144 // Inorder Traversal

145 void inorder(RBNode *root) {
146 if (root == NIL) return;
147 inorder(root->left);
148 printf("%d(%c) ", root->key, root->color == RED ? ’R’ :
’B’);
149 inorder(root->right);
150 }
151

152 int main() {

153 int choice, key;
154

155 NIL = (RBNode*)malloc(sizeof(RBNode));

156 NIL->color = BLACK;

58
 Advanced Data Structures Lab Manual B3CS104PC
157 NIL->left = NIL->right = NIL->parent = NIL;
158

159 root = NIL;

160

161 while (1) {

162 printf("\n1. Insert\n2. Search\n3. Inorder\n4. Exit
\n");
163 printf("Enter choice: ");
164 scanf("%d", &choice);
165

166 switch (choice) {

167 case 1:
168 printf("Enter key: ");
169 scanf("%d", &key);
170 insertRB(&root, key);
171 break;
172

173 case 2:
174 printf("Enter key: ");
175 scanf("%d", &key);
176 printf(searchRB(root, key) != NIL ? "Found\n" :
"Not found\n");
177 break;
178

179 case 3:
180 inorder(root);
181 printf("\n");
182 break;
183

184 case 4:
185 exit(0);
186 }
187 }
188 return 0;
189 }

Sample Input
1
Enter key: 20

59
 Advanced Data Structures Lab Manual B3CS104PC
1
Enter key: 15
1
Enter key: 30
1
Enter key: 25
3

Expected Output
15(R) 20(B) 25(R) 30(B)

Observations
ˆ The newly inserted nodes are initially RED.
ˆ Rotations and recoloring ensure RBT properties remain valid.
ˆ Root always becomes BLACK after insertion.
ˆ Inorder traversal prints keys in sorted order with node colors.
Result
Red–Black Tree insertion, fix-up, and search operations were successfully implemented.
The program maintains all Red–Black Tree balancing properties using rotations and
recoloring.

Viva Questions
1. State the properties of a Red–Black Tree.
All paths from a node to leaves contain the same number of BLACK nodes, root is
BLACK, etc.

2. Why are Red–Black Trees used in standard libraries?

They guarantee O(log n) operations and provide good worst-case balance.

3. Compare the height of AVL Tree vs Red–Black Tree.

AVL trees are more strictly balanced height O(log n) but shorter. Red–Black
trees allow slight imbalance height ≤ 2 log n.

60
 Advanced Data Structures Lab Manual B3CS104PC
4. What is the purpose of rotations?
Rotations restore BST structure and maintain balancing properties.

5. Does Red–Black Tree guarantee perfect balance?

No, it guarantees approximate balance.

6. Why are NIL (leaf ) nodes BLACK?

To simplify property checking and maintain uniform Black-Height.

61
Chapter 9

Dictionary Using Hashing

Aim
To design and implement a dictionary (key-based lookup structure) using hashing and
to perform basic operations such as insertion, searching, deletion, and display using the
open addressing technique with linear probing.

Problem Statement
A dictionary stores key-value pairs, enabling fast insertion, deletion, and search. The
challenge is to design a hash table of fixed size and implement collision resolution using
linear probing. The program should allow the user to:

ˆ Insert a key
ˆ Search for a key
ˆ Delete a key
ˆ Display the hash table
Description
Hashing is an efficient technique for implementing dictionaries. A hash function maps
a key to an index of a hash table. Collisions occur when multiple keys map to the same
index. To handle collisions, we use:

ˆ Open Addressing — All entries are stored within the table.

ˆ Linear Probing — If collision occurs at index i, check (i+1), (i+2), . . . cyclically.

62
 Advanced Data Structures Lab Manual B3CS104PC
Special markers used:

ˆ EMPTY = Slot has never been used.

ˆ DELETED = Slot previously occupied but now deleted.
Algorithm
1. Hash Function
1. Compute: index = key mod T ABLE SIZE

2. Return the computed index.

2. Insert Operation
1. Compute initial index using the hash function.

2. If slot is EMPTY or DELETED, insert key.

3. Otherwise, probe sequentially (linear probing).

4. If the table is full, report failure.

3. Search Operation
1. Compute initial index.

2. While slot not EMPTY:

ˆ If the key matches, return index.

ˆ Else probe next slot.
3. If EMPTY reached, key does not exist.

4. Delete Operation
1. Search the key.

2. If found, mark slot as DELETED.

3. If not found, print error message.

63
 Advanced Data Structures Lab Manual B3CS104PC
5. Display Operation
1. For each index i:

ˆ If EMPTY, print EMPTY.

ˆ If DELETED, print DELETED.
ˆ Else print stored key.
Program (Open Addressing with Linear Probing)
1 #include <stdio.h>
2 #include <stdlib.h>
3

4 #define TABLE_SIZE 10
5 #define EMPTY -1
6 #define DELETED -2
7

8 int hashTable[TABLE_SIZE];
9

10 // Hash function
11 int hash(int key) {
12 return key % TABLE_SIZE;
13 }
14

15 // Initialize hash table

16 void initTable() {
17 int i;
18 for (i = 0; i < TABLE_SIZE; i++)
19 hashTable[i] = EMPTY;
20 }
21

22 // Insert a key (linear probing)

23 void insert(int key) {
24 int index = hash(key);
25 int start = index;
26

27 while (hashTable[index] != EMPTY && hashTable[index] !=

DELETED) {
28 index = (index + 1) % TABLE_SIZE;
29

30 if (index == start) {

64
 Advanced Data Structures Lab Manual B3CS104PC
31 printf("Hash table full.\n");
32 return;
33 }
34 }
35 hashTable[index] = key;
36 }
37

38 // Search for a key

39 int search(int key) {
40 int index = hash(key);
41 int start = index;
42

43 while (hashTable[index] != EMPTY) {

44 if (hashTable[index] == key)
45 return index;
46

47 index = (index + 1) % TABLE_SIZE;

48

49 if (index == start)
50 break;
51 }
52 return -1;
53 }
54

55 // Delete a key
56 void deleteKey(int key) {
57 int pos = search(key);
58

59 if (pos == -1) {
60 printf("Key not found.\n");
61 return;
62 }
63

64 hashTable[pos] = DELETED;
65 printf("Key %d deleted.\n", key);
66 }
67

68 // Display hash table

69 void display() {
70 int i;
71 printf("\n--- Hash Table ---\n");

65
 Advanced Data Structures Lab Manual B3CS104PC
72

73 for (i = 0; i < TABLE_SIZE; i++) {

74 printf("%d: ", i);
75

76 if (hashTable[i] == EMPTY)
77 printf("EMPTY");
78 else if (hashTable[i] == DELETED)
79 printf("DELETED");
80 else
81 printf("%d", hashTable[i]);
82

83 printf("\n");
84 }
85 }
86

87 int main() {
88 int choice, key;
89

90 initTable();
91

92 while (1) {
93 printf("\n1. Insert\n2. Search\n3. Delete\n4.
Display\n5. Exit\n");
94 printf("Enter choice: ");
95 scanf("%d", &choice);
96

97 switch (choice) {
98 case 1:
99 printf("Enter key: ");
100 scanf("%d", &key);
101 insert(key);
102 break;
103

104 case 2:
105 printf("Enter key: ");
106 scanf("%d", &key);
107 printf(search(key) != -1 ? "Found\n" : "Not
found\n");
108 break;
109

110 case 3:

66
 Advanced Data Structures Lab Manual B3CS104PC
111 printf("Enter key: ");
112 scanf("%d", &key);
113 deleteKey(key);
114 break;
115

116 case 4:
117 display();
118 break;
119

120 case 5:
121 exit(0);
122

123 default:
124 printf("Invalid choice.\n");
125 }
126 }
127

128 return 0;
129 }

Sample Input
1
Enter key: 25
1
Enter key: 15
1
Enter key: 35
4

Expected Output
--- Hash Table ---
0: EMPTY
1: EMPTY
2: EMPTY
3: EMPTY
4: EMPTY
5: 25

67
 Advanced Data Structures Lab Manual B3CS104PC
6: 15
7: 35
8: EMPTY
9: EMPTY

Observations
ˆ Keys 25, 15, and 35 are placed based on their hash values and collisions.
ˆ Linear probing resolves collisions by checking the next available slot.
ˆ Deletion leaves DELETED markers to preserve probing sequences.
Result
The dictionary operations (insert, search, delete, and display) were successfully imple-
mented using hashing with open addressing and linear probing.

Viva Questions
1. What is a hash function? What properties should it have?
It maps keys to table indices. Good hash functions are uniform, deterministic, and
fast to compute.

2. What is a collision? Name different collision resolution techniques.

When two keys map to the same index, a collision occurs. Techniques include
chaining, linear probing, quadratic probing, and double hashing.

3. Compare chaining and open addressing.

Chaining uses linked lists for collisions; memory grows dynamically. Open address-
ing stores all keys in the table; requires probing but avoids pointers.

4. What is primary clustering?

Clustering occurs in linear probing when groups of filled entries build up, causing
long search sequences.

5. Why do we need a DELETED marker?

To prevent breaking search chains while supporting deletion.

68
Chapter 10

Knuth–Morris–Pratt (KMP)
Pattern Matching Algorithm

Aim
To design and implement the Knuth–Morris–Pratt (KMP) pattern matching algorithm
in C, using the LPS (Longest Proper Prefix–Suffix) preprocessing technique to efficiently
search for occurrences of a pattern within a text.

Problem Statement
Given a text string T of length n and a pattern string P of length m, write a C program to
search for all occurrences of P in T without performing unnecessary re-comparisons. The
KMP algorithm must preprocess the pattern to compute the LPS array, which enables
efficient shifting without backtracking in the text.

Description
The KMP algorithm improves upon brute-force pattern matching by ensuring that the
text index never moves backward. Instead of re-checking already matched characters,
KMP uses a preprocessed table known as the LPS (Longest Proper Prefix–Suffix)
array.

Key Features
ˆ Avoids redundant comparisons.
ˆ Ensures linear-time performance: O(n + m).
ˆ Particularly efficient for long patterns and repetitive strings.
69
 Advanced Data Structures Lab Manual B3CS104PC
LPS (Longest Proper Prefix–Suffix) Array
For each prefix of the pattern, LP S[i] stores the length of the longest proper prefix
which is also a suffix. This helps determine how many characters can be skipped after a
mismatch.
Example:
Pattern: ABABAC LPS Array: [0, 0, 1, 2, 3, 0]

Algorithm
Step 1: Compute LPS Array
1. Initialize LPS array with 0 at index 0.

2. Maintain a length variable ‘len‘ to track the current prefix-suffix match length.

3. For each index i:

ˆ If characters match, increment ‘len‘ and set LPS[i] = len.

ˆ If mismatch and len ¿ 0, update len to LPS[len - 1].
ˆ If mismatch and len = 0, set LPS[i] = 0.
Step 2: KMP Search
1. Compare pattern and text characters.

2. If match, increment both text and pattern indices.

3. If full pattern matched (j == m):

ˆ Record the found index.

ˆ Reset j using LP S[j − 1].
4. If mismatch:

ˆ If j > 0, shift using LPS.

ˆ Otherwise, advance text index only.
Time Complexity
ˆ Preprocessing (LPS): O(m)
ˆ Pattern Search: O(n)
70
 Advanced Data Structures Lab Manual B3CS104PC
ˆ Total Time Complexity: O(n + m)
ˆ Space Complexity: O(m)
Program
1 #include <stdio.h>
2 #include <string.h>
3

4 // Build LPS array: Longest Proper Prefix which is also

Suffix
5 void computeLPS(char *pat, int m, int lps[]) {
6 int len = 0;
7 int i = 1;
8 lps[0] = 0;
9

10 while (i < m) {
11 if (pat[i] == pat[len]) {
12 len++;
13 lps[i] = len;
14 i++;
15 } else {
16 if (len != 0)
17 len = lps[len - 1];
18 else {
19 lps[i] = 0;
20 i++;
21 }
22 }
23 }
24 }
25

26 // KMP Search Algorithm

27 void KMP(char *txt, char *pat) {
28 int n = strlen(txt);
29 int m = strlen(pat);
30 int lps[100];
31

32 computeLPS(pat, m, lps);
33

34 int i = 0, j = 0;

71
 Advanced Data Structures Lab Manual B3CS104PC
35 while (i < n) {
36 if (pat[j] == txt[i]) {
37 i++;
38 j++;
39 }
40 if (j == m) {
41 printf("Pattern found at index %d\n", i - j);
42 j = lps[j - 1];
43 } else if (i < n && pat[j] != txt[i]) {
44 if (j != 0)
45 j = lps[j - 1];
46 else
47 i++;
48 }
49 }
50 }
51

52 int main() {
53 char txt[200], pat[100];
54

55 printf("Enter text: ");

56 fgets(txt, sizeof(txt), stdin);
57 txt[strcspn(txt, "\n")] = ’\0’;
58

59 printf("Enter pattern: ");

60 fgets(pat, sizeof(pat), stdin);
61 pat[strcspn(pat, "\n")] = ’\0’;
62

63 KMP(txt, pat);
64

65 return 0;
66 }

Sample Input
Enter text: ABABDABACDABABCABAB
Enter pattern: ABABCABAB

72
 Advanced Data Structures Lab Manual B3CS104PC
Expected Output
Pattern found at index 10

Explanation of Output
ˆ The algorithm begins matching from left to right.
ˆ Whenever mismatch occurs, instead of rechecking all characters, the LPS array is
used to skip unnecessary comparisons.

ˆ The pattern is correctly found starting at index 10.

Result
The Knuth–Morris–Pratt (KMP) algorithm was successfully implemented in C. The pro-
gram correctly computes the LPS array and efficiently finds pattern matches without
redundant comparisons, demonstrating linear-time string matching.

Viva Questions
1. What is the time complexity of KMP?
The time complexity is O(n + m), where n is text length and m is pattern length.

2. What is the purpose of the LPS array?

The LPS array helps identify how many characters can be skipped when a mismatch
occurs, avoiding unnecessary re-comparisons.

3. Compare KMP with brute-force pattern matching.

Brute-force may re-check characters and can be O(nm) in worst-case. KMP guar-
antees linear time and avoids redundant comparisons by using LPS.

4. Does KMP ever backtrack in the text?

No, the text index never moves backward.

5. What is a proper prefix?

A substring that starts at index 0 but does not include the full string.

6. Can the LPS array contain decreasing values?

Yes, depending on the structure of the pattern, LPS values may rise or fall.

73
Chapter 11

Brute-Force Pattern Matching

Algorithm

Aim
To write and execute a C program that implements the Naive (Brute-Force) pattern
matching algorithm to find all occurrences of a pattern within a given text.

Problem Statement
Given a text string T of length n and a pattern string P of length m, the task is to
compare P with every possible substring of T and identify all starting positions where
an exact match is found. This experiment demonstrates the simplest string searching
method, where characters are compared sequentially without using any preprocessing or
skipping techniques.

Description
The brute-force (naive) pattern matching algorithm is the simplest and most intuitive
method of searching for a substring within a text. It checks for a match by aligning the
pattern P at every possible starting position in the text T and comparing characters
one-by-one.

Characteristics
ˆ No preprocessing or heuristics used.
ˆ Always checks from left to right.

74
 Advanced Data Structures Lab Manual B3CS104PC
ˆ Useful for small-scale and simple applications.
ˆ Performs poorly on long texts with repeated characters.
Algorithm
1. Read input text string T and pattern string P .

2. Compute the lengths n = |T | and m = |P |.

3. For each possible shift i from 0 to n − m:

(a) Compare P [j] with T [i + j] for all j from 0 to m − 1.

(b) If a mismatch occurs, break and shift the pattern one position to the right.
(c) If all characters match (j == m), record the occurrence index i.

4. If no index satisfies equality, the pattern does not exist in the text.

Time Complexity
ˆ Best Case: O(n) (first characters mismatch frequently)
ˆ Worst Case: O(nm) (repeated characters, e.g., text = “AAAAAA”, pattern =
“AAA”)

ˆ Space Complexity: O(1) (in-place comparison)

Program
1 #include <stdio.h>
2 #include <string.h>
3

4 // Brute-Force String Matching Function

5 void bruteForceMatch(char *txt, char *pat) {
6 int n = strlen(txt);
7 int m = strlen(pat);
8 int i, j;
9

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

11 for (j = 0; j < m; j++) {
12 if (txt[i + j] != pat[j])
13 break;

75
 Advanced Data Structures Lab Manual B3CS104PC
14 }
15 if (j == m)
16 printf("Pattern found at index %d\n", i);
17 }
18 }
19

20 int main() {
21 char txt[200], pat[100];
22

23 printf("Enter text: ");

24 fgets(txt, sizeof(txt), stdin);
25 txt[strcspn(txt, "\n")] = ’\0’;
26

27 printf("Enter pattern: ");

28 fgets(pat, sizeof(pat), stdin);
29 pat[strcspn(pat, "\n")] = ’\0’;
30

31 bruteForceMatch(txt, pat);
32

33 return 0;
34 }

Sample Input
Enter text: AABAACAADAABAABA
Enter pattern: AABA

Expected Output
Pattern found at index 0
Pattern found at index 9
Pattern found at index 12

Explanation of Output
ˆ The pattern “AABA” occurs at positions 0, 9, and 12 in the text.
ˆ At every matching position, all characters of the pattern match sequentially.
ˆ When mismatch occurs, only one shift is made—no skipping optimizations.
76
 Advanced Data Structures Lab Manual B3CS104PC
Result
The brute-force pattern matching algorithm was successfully implemented. The program
correctly identifies all occurrences of a given pattern in the text by performing sequential
character comparisons without using preprocessing tables.

Viva Questions
1. What is the worst-case time complexity of the brute-force algorithm?
The worst-case time complexity is O(nm), where n is the length of the text and m
is the length of the pattern.

2. When is brute-force still acceptable or useful?

It is acceptable in situations where input sizes are small, or where the overhead of
preprocessing (as in KMP or Boyer–Moore) is unnecessary.

3. Compare brute-force with KMP and Boyer–Moore.

Brute-force does not skip characters and may compare many redundant positions.
KMP uses prefix-based failure function to reduce backtracking. Boyer–Moore uses
heuristics to skip large portions of text, offering sub-linear average time.

4. Does brute-force require additional memory?

No, it works in constant space O(1).

5. What happens if the pattern is longer than the text?

No comparisons are made since n − m becomes negative, and no match is possible.

6. How many comparisons happen in the best case?

Approximately O(n) comparisons when mismatches occur early.

77
Chapter 12

Boyer–Moore Pattern Matching

Algorithm

Aim
To design and implement the Boyer–Moore pattern matching algorithm in C using the
Bad-Character Heuristic, and to analyze its efficiency in comparison with other string
matching algorithms.

Problem Statement
Given a text string T of length n and a pattern string P of length m, write a C program
to find all occurrences of P in T using the Boyer–Moore algorithm. Implement the bad-
character heuristic to efficiently skip unnecessary comparisons and minimize the number
of character checks.

Description
The Boyer–Moore pattern matching algorithm is one of the most efficient string searching
methods. It improves upon naive pattern matching by using two ideas:

1. Bad-Character Heuristic — shifts the pattern based on the last occurrence of a

mismatched character.

2. Good-Suffix Heuristic — shifts the pattern based on matching suffixes.

In this experiment, we implement the Bad-Character rule, which:

ˆ compares pattern characters from right to left,

78
 Advanced Data Structures Lab Manual B3CS104PC
ˆ skips portions of the text intelligently,
ˆ offers sub-linear average-case performance.
It is widely used in text editors, command-line tools (grep), and search engines.

Algorithm
Step 1: Preprocessing (Bad-Character Table)
1. Initialize an array badchar[256] with all values set to −1.

2. For every character present in the pattern:

(a) Set badchar[pattern[i]] = i.

3. This stores the rightmost index of each character in the pattern.

Step 2: Searching Phase

1. Start comparing pattern characters from the end (j = m − 1).

2. If characters match, move leftwards.

3. If mismatch occurs:

(a) Check the mismatched text character c.

(b) Find its last occurrence in the pattern using badchar[c].
(c) Compute shift:
shift = max(1, j − badchar[c])

(d) Move the pattern to the right by the shift value.

4. If j < 0, pattern found at index s.

5. Shift pattern to continue searching for next occurrences.

Time Complexity
ˆ Best Case: O(n/m) due to large jumps.
ˆ Average Case: Sub-linear time O(n).
ˆ Worst Case: O(n · m) (rare).
79
 Advanced Data Structures Lab Manual B3CS104PC
Program (Bad-Character Heuristic)
1 #include <stdio.h>
2 #include <string.h>
3

4 #define ALPHABET_SIZE 256

5

6 // Preprocessing: Construct Bad Character Table

7 void badCharHeuristic(char *pat, int m, int badchar[]) {
8 int i;
9 for (i = 0; i < ALPHABET_SIZE; i++)
10 badchar[i] = -1;
11

12 for (i = 0; i < m; i++)

13 badchar[(unsigned char)pat[i]] = i;
14 }
15

16 // Boyer-Moore Search (Bad Character Rule Only)

17 void boyerMoore(char *txt, char *pat) {
18 int n = strlen(txt);
19 int m = strlen(pat);
20 int badchar[ALPHABET_SIZE];
21

22 badCharHeuristic(pat, m, badchar);
23

24 int s = 0; // shift of the pattern

25 while (s <= (n - m)) {
26

27 int j = m - 1;
28

29 // Compare pattern from right to left

30 while (j >= 0 && pat[j] == txt[s + j])
31 j--;
32

33 if (j < 0) {
34 printf("Pattern found at index %d\n", s);
35

36 // Shift pattern for next potential match

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

80
 Advanced Data Structures Lab Manual B3CS104PC
39 } else {
40 // Mismatch shift using bad character rule
41 int shift = j - badchar[(unsigned char)txt[s +
j]];
42 if (shift < 1) shift = 1;
43 s += shift;
44 }
45 }
46 }
47

48 int main() {
49 char txt[200], pat[100];
50

51 printf("Enter text: ");

52 fgets(txt, sizeof(txt), stdin);
53 txt[strcspn(txt, "\n")] = ’\0’; // remove newline
54

55 printf("Enter pattern: ");

56 fgets(pat, sizeof(pat), stdin);
57 pat[strcspn(pat, "\n")] = ’\0’;
58

59 boyerMoore(txt, pat);
60 return 0;
61 }

Sample Input and Output

Input
Text: ABABDABACDABABCABAB
Pattern: ABABCABAB

Expected Output
Pattern found at index 10

Result
The Boyer–Moore pattern matching algorithm was successfully implemented using the
Bad-Character heuristic. The program efficiently located pattern occurrences within the

81
 Advanced Data Structures Lab Manual B3CS104PC
given text by minimizing unnecessary comparisons and using intelligent shifting strate-
gies.

Viva Questions
1. What are the heuristics used in the Boyer–Moore algorithm? Answer: Bad-
Character Heuristic and Good-Suffix Heuristic.

2. Why is Boyer–Moore considered efficient in practice? Answer: Because it can skip

large portions of the text, achieving sub-linear average performance.

3. Compare Boyer–Moore with KMP in terms of shift strategy. Answer: KMP uses
prefix-based failure function and never skips characters in text. Boyer–Moore uses
mismatch-based shifts allowing larger jumps and is often faster.

4. What is the role of the Bad-Character Table? Answer: It stores the rightmost
occurrence of each character in the pattern to determine how far the pattern should
shift after mismatch.

5. What happens when the mismatched character does not exist in the pattern? An-
swer: The pattern shifts by m positions (pattern length), maximizing the skip.

6. Can Boyer–Moore scan text from left-to-right? Answer: No, it compares pattern
characters from right-to-left.

7. Why is the worst-case performance rare? Answer: Because the algorithm’s shifts
depend on rare cases of repeating patterns.

82