Write a program to implement merge sort in C language.

#include <stdio.h>

/* Function to merge the subarrays of a[] */

void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;

int LeftArray[n1], RightArray[n2]; //temporary arrays

/* copy data to temp arrays */

for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];

i = 0; /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */

while (i < n1 && j < n2)

{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}

while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}
void mergeSort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}

/* Function to print the array */

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

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}
Output:

Write a pgm to implement

A) binary search tree
#include <stdio.h> #include <stdlib.h> struct node { int data; struct node *right
_child; struct node *left_child; }; struct node* new_node(int x){ struct node *te
mp; temp = malloc(sizeof(struct node)); temp->data = x; temp->left_child = NU
LL; temp->right_child = NULL; return temp; } struct node* search(struct nod
e * root, int x){ if (root == NULL || root->data == x) return root; else if (x > ro
ot->data) return search(root->right_child, x); else return search(root-
>left_child, x); } struct node* insert(struct node * root, int x){ if (root == NULL)
return new_node(x); else if (x > root->data) root->right_child = insert(root-
>right_child, x); else root -> left_child = insert(root->left_child, x); return root
; } struct node* find_minimum(struct node * root) { if (root == NULL) return
NULL; else if (root->left_child != NULL) return find_minimum(root-
>left_child); return root; } struct node* delete(struct node * root, int x) { if (ro
ot == NULL) return NULL; if (x > root->data) root->right_child = delete(root
->right_child, x); else if (x < root->data) root->left_child = delete(root-
>left_child, x); else { if (root->left_child == NULL && root->right_child == N
ULL){ free(root); return NULL; } else if (root->left_child == NULL ||
root->right_child == NULL){ struct node *temp; if (root->left_child == NU
LL) temp = root->right_child; else temp = root->left_child; free(r
oot); return temp; } else { struct node *temp = find_minimum(root-
>right_child); root->data = temp->data; root->right_child = delete(root-
>right_child, temp->data); } } return root; } void inorder(struct node *root){
if (root != NULL) { inorder(root->left_child); printf(" %d ", root->data);
inorder(root->right_child); } } int main() { struct node *root; root = new_no
de(20); insert(root, 5); insert(root, 1); insert(root, 15); insert(root, 9); insert(r
oot, 7); insert(root, 12); insert(root, 30); insert(root, 25); insert(root, 40); ins
ert(root, 45); insert(root, 42); inorder(root); printf("\n"); root = delete(root, 1
); root = delete(root, 40); root = delete(root, 45); root = delete(root, 9); in
order(root); printf("\n"); return 0; } Output1 5 7 9 12 15 20 25 30 40 42 455 7
12 15 20 25 30 42
B) B Tree
#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct BTreeNode {
int val[MAX + 1], count;
struct BTreeNode *link[MAX + 1];
};

struct BTreeNode *root;

// Create a node
struct BTreeNode *createNode(int val, struct BTreeNode *child) {
struct BTreeNode *newNode;
newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
newNode->val[1] = val;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
}

// Insert node
void insertNode(int val, int pos, struct BTreeNode *node,
 struct BTreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
node->link[j + 1] = node->link[j];
j--;
}
node->val[j + 1] = val;
node->link[j + 1] = child;
node->count++;
}

// Split node
void splitNode(int val, int *pval, int pos, struct BTreeNode *node,
struct BTreeNode *child, struct BTreeNode **newNode) {
int median, j;

if (pos > MIN)

median = MIN + 1;
else
median = MIN;

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

j = median + 1;
while (j <= MAX) {
(*newNode)->val[j - median] = node->val[j];
(*newNode)->link[j - median] = node->link[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;

if (pos <= MIN) {

insertNode(val, pos, node, child);
} else {
insertNode(val, pos - median, *newNode, child);
}
*pval = node->val[node->count];
(*newNode)->link[0] = node->link[node->count];
node->count--;
}

// Set the value

int setValue(int val, int *pval,
struct BTreeNode *node, struct BTreeNode **child) {
int pos;
if (!node) {
*pval = val;
*child = NULL;
return 1;
 }

if (val < node->val[1]) {

pos = 0;
} else {
for (pos = node->count;
(val < node->val[pos] && pos > 1); pos--)
;
if (val == node->val[pos]) {
printf("Duplicates are not permitted\n");
return 0;
}
}
if (setValue(val, pval, node->link[pos], child)) {
if (node->count < MAX) {
insertNode(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}

// Insert the value

void insert(int val) {
int flag, i;
struct BTreeNode *child;

flag = setValue(val, &i, root, &child);

if (flag)
root = createNode(i, child);
}

// Search node
void search(int val, int *pos, struct BTreeNode *myNode) {
if (!myNode) {
return;
}

if (val < myNode->val[1]) {

*pos = 0;
} else {
for (*pos = myNode->count;
(val < myNode->val[*pos] && *pos > 1); (*pos)--)
;
if (val == myNode->val[*pos]) {
printf("%d is found", val);
return;
}
 }
search(val, pos, myNode->link[*pos]);

return;
}

// Traverse then nodes

void traversal(struct BTreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->link[i]);
printf("%d ", myNode->val[i + 1]);
}
traversal(myNode->link[i]);
}
}

int main() {
int val, ch;

insert(8);
insert(9);
insert(10);
insert(11);
insert(15);
insert(16);
insert(17);
insert(18);
insert(20);
insert(23);

traversal(root);

printf("\n");
search(11, &ch, root);
}
Output:
8 9 10 11 15 16 17 18 20 23 11 is found
C) B+ tree

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

#define MIN_DEGREE \
3 // Minimum degree (defines the range for number of
// keys)

typedef struct Node {

 // Array of keys
int* keys;
// Minimum degree (defines the range for number of keys)
int t;
// Array of child pointers
struct Node** children;
// Current number of keys
int n;
// To determine whether the node is leaf or not
bool leaf;
// Pointer to next leaf node
struct Node* next;
} Node;

typedef struct BTree {

// Pointer to root node
Node* root;
// Minimum degree
int t;
} BTree;

// Function to create a new B+ tree node

Node* createNode(int t, bool leaf)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->t = t;
newNode->leaf = leaf;
newNode->keys = (int*)malloc((2 * t - 1) * sizeof(int));
newNode->children
= (Node**)malloc((2 * t) * sizeof(Node*));
newNode->n = 0;
newNode->next = NULL;
return newNode;
}

// Function to create a new B+ tree

BTree* createBTree(int t)
{
BTree* btree = (BTree*)malloc(sizeof(BTree));
btree->t = t;
btree->root = createNode(t, true);
return btree;
}

// Function to display the B+ tree and print its keys

void display(Node* node)
{
if (node == NULL)
return;
int i;
 for (i = 0; i < node->n; i++) {
if (!node->leaf) {
display(node->children[i]);
}
printf("%d ", node->keys[i]);
}
if (!node->leaf) {
display(node->children[i]);
}
}

// Function to search a key in the B+ tree

bool search(Node* node, int key)
{
int i = 0;
while (i < node->n && key > node->keys[i]) {
i++;
}
if (i < node->n && key == node->keys[i]) {
return true;
}
if (node->leaf) {
return false;
}
return search(node->children[i], key);
}

// Function to split the child of a node during insertion

void splitChild(Node* parent, int i, Node* child)
{
int t = child->t;
Node* newChild = createNode(t, child->leaf);
newChild->n = t - 1;

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

newChild->keys[j] = child->keys[j + t];
}

if (!child->leaf) {
for (int j = 0; j < t; j++) {
newChild->children[j] = child->children[j + t];
}
}

child->n = t - 1;

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

parent->children[j + 1] = parent->children[j];
}
parent->children[i + 1] = newChild;
 for (int j = parent->n - 1; j >= i; j--) {
parent->keys[j + 1] = parent->keys[j];
}
parent->keys[i] = child->keys[t - 1];
parent->n += 1;
}

// Function to insert a non-full node

void insertNonFull(Node* node, int key)
{
int i = node->n - 1;

if (node->leaf) {
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->n += 1;
}
else {
while (i >= 0 && node->keys[i] > key) {
i--;
}
i++;
if (node->children[i]->n == 2 * node->t - 1) {
splitChild(node, i, node->children[i]);
if (node->keys[i] < key) {
i++;
}
}
insertNonFull(node->children[i], key);
}
}

// Function to insert a key into the B+ tree

void insert(BTree* btree, int key)
{
Node* root = btree->root;
if (root->n == 2 * btree->t - 1) {
Node* newRoot = createNode(btree->t, false);
newRoot->children[0] = root;
splitChild(newRoot, 0, root);
insertNonFull(newRoot, key);
btree->root = newRoot;
}
else {
insertNonFull(root, key);
}
}

// Function prototypes for helper functions used in

// deleteKey
void deleteKeyHelper(Node* node, int key);
int findKey(Node* node, int key);
void removeFromLeaf(Node* node, int idx);
int getPredecessor(Node* node, int idx);
void fill(Node* node, int idx);
void borrowFromPrev(Node* node, int idx);
void borrowFromNext(Node* node, int idx);
void merge(Node* node, int idx);

// Function for deleting a key from the B+ tree

void deleteKey(BTree* btree, int key)
{
Node* root = btree->root;

// Call a helper function to delete the key recursively

deleteKeyHelper(root, key);

// If root has no keys left and it has a child, make its

// first child the new root
if (root->n == 0 && !root->leaf) {
btree->root = root->children[0];
free(root);
}
}

// Helper function to recursively delete a key from the B+

// tree
void deleteKeyHelper(Node* node, int key)
{
int idx = findKey(
node, key); // Find the index of the key in the node

// If key is present in this node

if (idx < node->n && node->keys[idx] == key) {
if (node->leaf) {
// If the node is a leaf, simply remove the key
removeFromLeaf(node, idx);
}
else {
// If the node is not a leaf, replace the key
// with its predecessor/successor
int predecessor = getPredecessor(node, idx);
node->keys[idx] = predecessor;
// Recursively delete the predecessor
deleteKeyHelper(node->children[idx],
predecessor);
 }
}
else {
// If the key is not present in this node, go down
// the appropriate child
if (node->leaf) {
// Key not found in the tree
printf("Key %d not found in the B+ tree.\n",
key);
return;
}

bool isLastChild = (idx == node->n);

// If the child where the key is supposed to be lies

// has less than t keys, fill that child
if (node->children[idx]->n < node->t) {
fill(node, idx);
}

// If the last child has been merged, it must have

// merged with the previous child

// So, we need to recursively delete the key from

// the previous child
if (isLastChild && idx > node->n) {
deleteKeyHelper(node->children[idx - 1], key);
}
else {
deleteKeyHelper(node->children[idx], key);
}
}
}
// Function to find the index of a key in a node
int findKey(Node* node, int key)
{
int idx = 0;
while (idx < node->n && key > node->keys[idx]) {
idx++;
}
return idx;
}

// Function to remove a key from a leaf node

void removeFromLeaf(Node* node, int idx)
{
for (int i = idx + 1; i < node->n; ++i) {
node->keys[i - 1] = node->keys[i];
}
node->n--;
}

// Function to get the predecessor of a key in a non-leaf

// node
int getPredecessor(Node* node, int idx)
{
Node* curr = node->children[idx];
while (!curr->leaf) {
curr = curr->children[curr->n];
}
return curr->keys[curr->n - 1];
}

// Function to fill up the child node present at the idx-th

// position in the node node
void fill(Node* node, int idx)
{
if (idx != 0 && node->children[idx - 1]->n >= node->t) {
borrowFromPrev(node, idx);
}
else if (idx != node->n
&& node->children[idx + 1]->n >= node->t) {
borrowFromNext(node, idx);
}
else {
if (idx != node->n) {
merge(node, idx);
}
else {
merge(node, idx - 1);
}
}
}

// Function to borrow a key from the previous child and move

// it to the idx-th child
void borrowFromPrev(Node* node, int idx)
{
Node* child = node->children[idx];
Node* sibling = node->children[idx - 1];

// Move all keys in child one step ahead

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

// If child is not a leaf, move its child pointers one

// step ahead
if (!child->leaf) {
for (int i = child->n; i >= 0; --i) {
 child->children[i + 1] = child->children[i];
}
}

// Setting child's first key equal to node's key[idx -

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

// Moving sibling's last child as child's first child

if (!child->leaf) {
child->children[0] = sibling->children[sibling->n];
}

// Moving the key from the sibling to the parent

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

// Incrementing and decrementing the key counts of child

// and sibling respectively
child->n += 1;
sibling->n -= 1;
}

// Function to borrow a key from the next child and move it

// to the idx-th child
void borrowFromNext(Node* node, int idx)
{
Node* child = node->children[idx];
Node* sibling = node->children[idx + 1];

// Setting child's (t - 1)th key equal to node's

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

// If child is not a leaf, move its child pointers one

// step ahead
if (!child->leaf) {
child->children[(child->n) + 1]
= sibling->children[0];
}

// Setting node's idx-th key equal to sibling's first

// key
node->keys[idx] = sibling->keys[0];

// Moving all keys in sibling one step behind

for (int i = 1; i < sibling->n; ++i) {
sibling->keys[i - 1] = sibling->keys[i];
}

// If sibling is not a leaf, move its child pointers one

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

// Incrementing and decrementing the key counts of child

// and sibling respectively
child->n += 1;
sibling->n -= 1;
}

// Function to merge idx-th child of node with (idx + 1)-th

// child of node
void merge(Node* node, int idx)
{
Node* child = node->children[idx];
Node* sibling = node->children[idx + 1];

// Pulling a key from the current node and inserting it

// into (t-1)th position of child
child->keys[child->n] = node->keys[idx];

// If child is not a leaf, move its child pointers one

// step ahead
if (!child->leaf) {
child->children[child->n + 1]
= sibling->children[0];
}

// Copying the keys from sibling to child

for (int i = 0; i < sibling->n; ++i) {
child->keys[i + child->n + 1] = sibling->keys[i];
}

// If child is not a leaf, copy the children pointers as

// well
if (!child->leaf) {
for (int i = 0; i <= sibling->n; ++i) {
child->children[i + child->n + 1]
= sibling->children[i];
}
}

// Move all keys after idx in the current node one step
// before, so as to fill the gap created by moving
// keys[idx] to child
for (int i = idx + 1; i < node->n; ++i) {
node->keys[i - 1] = node->keys[i];
 }

// Move the child pointers after (idx + 1) in the

// current node one step before
for (int i = idx + 2; i <= node->n; ++i) {
node->children[i - 1] = node->children[i];
}

// Update the key count of child and current node

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

// Free the memory occupied by sibling

free(sibling);
}

int main()
{
BTree* btree = createBTree(MIN_DEGREE);

// Insert elements into the B+ tree

insert(btree, 2);
insert(btree, 4);
insert(btree, 7);
insert(btree, 10);
insert(btree, 17);
insert(btree, 21);
insert(btree, 28);

// Print the B+ tree

printf("B+ Tree after insertion: ");
display(btree->root);
printf("\n");

// Search for a key

int key_to_search = 17;
bool found = search(btree->root, key_to_search);

if (found) {
printf("Key %d found in the B+ tree.\n",
key_to_search);
}
else {
printf("Key %d not found in the B+ tree.\n",
key_to_search);
}

// Delete element from the B+ tree

deleteKey(btree, 17);
 // Print the B+ tree after deletion
printf("B+ Tree after deletion: ");
display(btree->root);
printf("\n");

found = search(btree->root, key_to_search);

if (found) {
printf("Key %d found in the B+ tree.\n",
key_to_search);
}
else {
printf("Key %d not found in the B+ tree.\n",
key_to_search);
}

return 0;
}

Output
B+ Tree after insertion: 2 4 7 10 17 21 28
Key 17 found in the B+ tree.
B+ Tree after deletion: 2 4 7 10 21 28
Key 17 not found in the B+ tree.

D) AVL Tree

#include<stdio.h> #include<stdlib.h> // structure of the tree node struct node {

int data; struct node* left; struct node* right; int ht; }; // global initializati
on of root node struct node* root = NULL; // function prototyping struct node* cr
eate(int); struct node* insert(struct node*, int); struct node* delete(struct node*, int);
struct node* search(struct node*, int); struct node* rotate_left(struct node*); struct n
ode* rotate_right(struct node*); int balance_factor(struct node*); int height(struct no
de*); void inorder(struct node*); void preorder(struct node*); void postorder(struct
node*); int main() { int user_choice, data; char user_continue = 'y'; struct
node* result = NULL; while (user_continue == 'y' || user_continue == 'Y') {
printf("\n\n------- AVL TREE --------\n"); printf("\n1. Insert"); printf("\
n2. Delete"); printf("\n3. Search"); printf("\n4. Inorder"); printf("\n5.
Preorder"); printf("\n6. Postorder"); printf("\n7. EXIT"); printf("\n\
nEnter Your Choice: "); scanf("%d", &user_choice); switch(user_choice
) { case 1: printf("\nEnter data: "); scanf("%d", &d
ata); root = insert(root, data); break; case 2:
printf("\nEnter data: "); scanf("%d", &data); root = delete(root, d
ata); break; case 3: printf("\nEnter data: "); s
canf("%d", &data); result = search(root, data); if (result == NUL
L) { printf("\nNode not found!"); } else
{ printf("\n Node found"); } break;
case 4: inorder(root); break; case 5: preorder
(root); break; case 6: postorder(root); break;
case 7: printf("\n\tProgram Terminated\n"); return 1;
 default: printf("\n\tInvalid Choice\n"); } printf("\n\nDo
you want to continue? "); scanf(" %c", &user_continue); } return 0; }
// creates a new tree node struct node* create(int data) { struct node* new_node =
(struct node*) malloc (sizeof(struct node)); // if a memory error has occurred i
f (new_node == NULL) { printf("\nMemory can't be allocated\n"); retu
rn NULL; } new_node->data = data; new_node->left = NULL; new_nod
e->right = NULL; return new_node; } // rotates to the left struct node* rotate_l
eft(struct node* root) { struct node* right_child = root->right; root->right = rig
ht_child->left; right_child->left = root; // update the heights of the nodes r
oot->ht = height(root); right_child->ht = height(right_child); // return the new
node after rotation return right_child; } // rotates to the right struct node* rotate
_right(struct node* root) { struct node* left_child = root->left; root->left = left
_child->right; left_child->right = root; // update the heights of the nodes ro
ot->ht = height(root); left_child->ht = height(left_child); // return the new nod
e after rotation return left_child; } // calculates the balance factor of a node int
balance_factor(struct node* root) { int lh, rh; if (root == NULL) return 0;
if (root->left == NULL) lh = 0; else lh = 1 + root->left->ht; if (ro
ot->right == NULL) rh = 0; else rh = 1 + root->right->ht; return lh -
rh; } // calculate the height of the node int height(struct node* root) { int lh, rh;
if (root == NULL) { return 0; } if (root->left == NULL) lh = 0
; else lh = 1 + root->left->ht; if (root->right == NULL) rh = 0; els
e rh = 1 + root->right->ht; if (lh > rh) return (lh); return (rh); } /
/ inserts a new node in the AVL tree struct node* insert(struct node* root, int data) {
if (root == NULL) { struct node* new_node = create(data); if (new_
node == NULL) { return NULL; } root = new_node; }
else if (data > root->data) { // insert the new node to the right root-
>right = insert(root->right, data); // tree is unbalanced, then rotate it if (b
alance_factor(root) == -2) { if (data > root->right->data) {
root = rotate_left(root); } else { root->right =
rotate_right(root->right); root = rotate_left(root); } } }
else { // insert the new node to the left root->left = insert(root->left, dat
a); // tree is unbalanced, then rotate it if (balance_factor(root) == 2)
{ if (data < root->left->data) { root = rotate_right(root);
} else { root->left = rotate_left(root->left); r
oot = rotate_right(root); } } } // update the heights of the nodes
root->ht = height(root); return root; } // deletes a node from the AVL tree struct
node * delete(struct node *root, int x) { struct node * temp = NULL; if (root
== NULL) { return NULL; } if (x > root->data) { root-
>right = delete(root->right, x); if (balance_factor(root) == 2) { if (
balance_factor(root->left) >= 0) { root = rotate_right(root);
} else { root->left = rotate_left(root->left); root
= rotate_right(root); } } } else if (x < root->data) { root-
>left = delete(root->left, x); if (balance_factor(root) == -2) { if (ba
lance_factor(root->right) <= 0) { root = rotate_left(root); }
else { root->right = rotate_right(root->right); roo
t = rotate_left(root); } } } else { if (root->right != NULL)
{ temp = root->right; while (temp->left != NULL) te
mp = temp->left; root->data = temp->data; root->right = delete(root
->right, temp->data); if (balance_factor(root) == 2) { if (ba
lance_factor(root->left) >= 0) { root = rotate_right(root);
 } else { root->left = rotate_left(root->left);
root = rotate_right(root); } } } else {
return (root->left); } } root->ht = height(root); return (root); } //
search a node in the AVL tree struct node* search(struct node* root, int key) { if (
root == NULL) { return NULL; } if(root->data == key) { ret
urn root; } if(key > root->data) { search(root->right, key); } els
e { search(root->left, key); } } // inorder traversal of the tree void inor
der(struct node* root) { if (root == NULL) { return; } inorder(roo
t->left); printf("%d ", root->data); inorder(root->right); } // preorder traversa
l of the tree void preorder(struct node* root) { if (root == NULL) { retur
n; } printf("%d ", root->data); preorder(root->left); preorder(root-
>right); } // postorder traversal of the tree void postorder(struct node* root) { i
f (root == NULL) { return; } postorder(root->left); postorder(root
->right); printf("%d ", root->data); } Test it NowOutput------- AVL TREE --------
1. Insert2. Delete3. Search4. Inorder5. Preorder6. Postorder7. EXITEnter Your
Choice: 1Enter data: 2Do you want to continue? y------- AVL TREE --------1. Insert2.
Delete3. Search4. Inorder5. Preorder6. Postorder7. EXITEnter Your Choice: 1Enter
data: 2Do you want to continue? y------- AVL TREE --------1. Insert2. Delete3.
Search4. Inorder5. Preorder6. Postorder7. EXITEnter Your Choice: 3Enter data:
2Node found
E) RED BLACK TREE
// Implementing Red-Black Tree in
C#include <stdio.h> #include <stdlib.h> // Define the structure for a Red-Black Tre
e node struct Node { int data; struct Node* parent; struct Node* left; stru
ct Node* right; int color; // 0 for black, 1 for red }; // Global pointers for the root
and NIL (sentinel) nodes struct Node* root = NULL; struct Node* NIL = NULL; //
Function to perform left rotation void leftRotate(struct Node* x) { struct Node* y
= x->right; x->right = y->left; if (y->left != NIL) { y->left->parent = x;
} y->parent = x->parent; if (x->parent == NULL) { root = y; } else if (
x == x->parent->left) { x->parent->left = y; } else { x->parent->right =
y; } y->left = x; x->parent = y; } // Function to perform right rotation voi
d right rotate(struct Node* y) { struct Node* x = y->left; y->left = x->right; i
f (x->right != NIL) { x->right->parent = y; } x->parent = y->parent; if
(y->parent == NULL) { root = x; } else if (y == y->parent->left) { y-
>parent->left = x; } else { y->parent->right = x; } x->right = y; y-
>parent = x; } // Function to fix the Red-Black Tree properties after insertion void i
nsertFixUp(struct Node* z) { while (z->parent != NULL && z->parent->color ==
1) { if (z->parent == z->parent->parent->left) { struct Node* y = z-
>parent->parent->right; // Uncle of z if (y->color == 1) { // Case 1:
z's uncle is red z->parent->color = 0; // Set parent to black y-
>color = 0; // Set uncle to black z->parent->parent->color = 1; // Set grandp
arent to red z = z->parent->parent; // Move to the grandparent } els
e{ if (z == z->parent->right) { // Case 2: z's uncle is black, an
d z is a right child z = z->parent; leftRotate(z); // Transform
into Case 3 } // Case 3: z's uncle is black, and z is a left child
z->parent->color = 0; // Set parent to black z->parent->parent->color
= 1; // Set grandparent to red rightRotate(z->parent->parent); }
} else { // Symmetric cases with left and right swapped struct Node*
y = z->parent->parent->left; if (y->color == 1) { z->parent->color
= 0; y->color = 0; z->parent->parent->color = 1; z=z
->parent->parent; } else { if (z == z->parent->left) { z
= z->parent; rightRotate(z); } z->parent->color = 0;
z->parent->parent->color = 1; leftRotate(z->parent->parent);
} } } root->color = 0; // Ensure that the root is black } // Function t
o insert a value into the Red-Black Tree void insert(int data) { // Allocate memory
for the new node struct Node* z = (struct Node*)malloc(sizeof(struct Node)); z-
>data = data; struct Node* y = NULL; struct Node* x = root; // Perform sta
ndard BST insertion while (x != NIL) { y = x; if (z->data < x->data) {
x = x->left; } else { x = x->right; } } z->parent = y;
if (y == NULL) { root = z; // Tree was empty, so z becomes the root } else i
f (z->data < y->data) { y->left = z; } else { y->right = z; } z-
>left = NIL; z->right = NIL; z->color = 1; // Color the new node as red // Fi
x any violations of the Red-Black Tree properties insertFixUp(z); } // Function t
o perform an in-order traversal and print the tree void inOrderTraversal(struct Node*
x) { if (x != NIL) { inOrderTraversal(x->left); printf("%d %s ", x-
>data, (x->color == 0) ? "Black" : "Red"); inOrderTraversal(x->right); } }
// Main function to test the Red-Black Tree insertion int main() { // Initialize NIL
node NIL = (struct Node*)malloc(sizeof(struct Node)); NIL->color = 0; // NIL i
s black int values[] = {10, 20, 30, 15, 5}; int n = sizeof(values) / sizeof(values[
0]); for (int i = 0; i < n; i++) { insert(values[i]); } printf("In-Order Tr
aversal of the Red-Black Tree:\n"); inOrderTraversal(root); return 0; } Outp
ut:5 Black 10 Black 15 Red 20 Black 30 Black

10. BOYER MOORE

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

#define NO_OF_CHARS 256

// A utility function to get maximum of two integers

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

// The preprocessing function for Boyer Moore's

// bad character heuristic
void badCharHeuristic(char* str, int size,
int badchar[NO_OF_CHARS])
{
int i;

// Initialize all occurrences as -1

for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;

// Fill the actual value of last occurrence

// of a character
for (i = 0; i < size; i++)
badchar[(int)str[i]] = i;
}
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
void search(char* txt, char* pat)
{
int m = strlen(pat);
int n = strlen(txt);

int badchar[NO_OF_CHARS];

/* Fill the bad character array by calling

the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);

int s = 0; // s is shift of the pattern with

// respect to text
while (s <= (n - m)) {
int j = m - 1;

/* Keep reducing index j of pattern while

characters of pattern and text are
matching at this shift s */
while (j >= 0 && pat[j] == txt[s + j])
j--;

/* If the pattern is present at current

shift, then index j will become -1 after
the above loop */
if (j < 0) {
printf("\n pattern occurs at shift = %d", s);

/* Shift the pattern so that the next

character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
}

else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s + j]]);
 }
}

/* Driver program to test above function */

int main()
{
char txt[] = "AABAACAADAABAABA";
char pat[] = "AABA";
search(txt, pat);
return 0;
}

Output
pattern occurs at shift = 0
pattern occurs at shift = 9
pattern occurs at shift = 12

KMP

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

#define NO_OF_CHARS 256

// A utility function to get maximum of two integers

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

// The preprocessing function for Boyer Moore's

// bad character heuristic
void badCharHeuristic(char* str, int size,
int badchar[NO_OF_CHARS])
{
int i;

// Initialize all occurrences as -1

for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;

// Fill the actual value of last occurrence

// of a character
for (i = 0; i < size; i++)
badchar[(int)str[i]] = i;
}

/* A pattern searching function that uses Bad

Character Heuristic of Boyer Moore Algorithm */
void search(char* txt, char* pat)
{
 int m = strlen(pat);
int n = strlen(txt);

int badchar[NO_OF_CHARS];

/* Fill the bad character array by calling

the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);

int s = 0; // s is shift of the pattern with

// respect to text
while (s <= (n - m)) {
int j = m - 1;

/* Keep reducing index j of pattern while

characters of pattern and text are
matching at this shift s */
while (j >= 0 && pat[j] == txt[s + j])
j--;

/* If the pattern is present at current

shift, then index j will become -1 after
the above loop */
if (j < 0) {
printf("\n pattern occurs at shift = %d", s);

/* Shift the pattern so that the next

character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
}

else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s + j]]);
}
}

/* Driver program to test above function */

int main()
{
char txt[] = "AABAACAADAABAABA";
char pat[] = "AABA";
search(txt, pat);
return 0;
}

Output
pattern occurs at shift = 0
pattern occurs at shift = 9
pattern occurs at shift = 12