BST operations in Java [Link] = insertRec(root.

right, key);
return root; boolean searchRec(Node root, int key) {
} if (root == null)
1. Write a program to perform the following return false;
operations: // Delete an element if ([Link] == key)
a) Insert an element into a binary search tree. void delete(int key) { return true;
b) Delete an element from a binary search tree. root = deleteRec(root, key); return key < [Link] ? searchRec([Link], key) : searchRec([Link], key);
c) Search for a key element in a binary search tree. } }
(write code in java and give answers only)
Node deleteRec(Node root, int key) { // Inorder traversal
if (root == null) void inorder() {
java
return root; inorderRec(root);
}
class BST {
if (key < [Link])
class Node {
[Link] = deleteRec([Link], key); void inorderRec(Node root) {
int key;
else if (key > [Link]) if (root != null) {
Node left, right;
[Link] = deleteRec([Link], key); inorderRec([Link]);
else { [Link]([Link] + " ");
Node(int item) {
if ([Link] == null) inorderRec([Link]);
key = item;
return [Link]; }
left = right = null;
else if ([Link] == null) }
}
return [Link];
}
public static void main(String[] args) {
[Link] = minValue([Link]); BST tree = new BST();
Node root;
[Link] = deleteRec([Link], [Link]);
} [Link](50);
BST() {
return root; [Link](30);
root = null;
} [Link](20);
}
[Link](40);
int minValue(Node root) { [Link](70);
// Insert an element
int minv = [Link]; [Link](60);
void insert(int key) {
while ([Link] != null) { [Link](80);
root = insertRec(root, key);
minv = [Link];
}
root = [Link]; [Link]("Inorder traversal: ");
} [Link]();
Node insertRec(Node root, int key) {
return minv;
if (root == null) {
} [Link]("\nSearch 40: " + [Link](40));
root = new Node(key);
[Link]("Search 100: " + [Link](100));
return root;
// Search for an element
}
boolean search(int key) { [Link]("Delete 20");
if (key < [Link])
return searchRec(root, key); [Link](20);
[Link] = insertRec([Link], key);
} [Link]();
else if (key > [Link])

1/47 2/47 3/47

L[i] = arr[l + i]; arr[largest] = swap;

[Link]("\nDelete 30"); for (int j = 0; j < n2; j++) heapify(arr, n, largest);
[Link](30); R[j] = arr[m + 1 + j]; }
[Link](); }
int i = 0, j = 0, k = l;
[Link]("\nDelete 50"); while (i < n1 && j < n2) // Quick Sort
[Link](50); arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++]; void quickSort(int[] arr, int low, int high) {
[Link](); if (low < high) {
} while (i < n1) int pi = partition(arr, low, high);
} arr[k++] = L[i++]; quickSort(arr, low, pi - 1);
while (j < n2) quickSort(arr, pi + 1, high);
arr[k++] = R[j++]; }
} }
2. Write a program for implementing the following
sorting methods: // Heap Sort int partition(int[] arr, int low, int high) {
a) Merge sort b) Heap sort c) Quick sort (write code in void heapSort(int[] arr) { int pivot = arr[high];
java and give answers only) int n = [Link]; int i = (low - 1);
for (int i = n / 2 - 1; i >= 0; i--) for (int j = low; j < high; j++) {
heapify(arr, n, i); if (arr[j] < pivot) {
java
i++;
for (int i = n - 1; i > 0; i--) { int temp = arr[i];
import [Link].*;
int temp = arr[0]; arr[i] = arr[j];
arr[0] = arr[i]; arr[j] = temp;
public class SortingMethods {
arr[i] = temp; }
heapify(arr, i, 0); }
// Merge Sort
} int temp = arr[i + 1];
void mergeSort(int[] arr, int l, int r) {
} arr[i + 1] = arr[high];
if (l < r) {
arr[high] = temp;
int m = (l + r) / 2;
void heapify(int[] arr, int n, int i) { return i + 1;
mergeSort(arr, l, m);
int largest = i; }
mergeSort(arr, m + 1, r);
int l = 2 * i + 1;
merge(arr, l, m, r);
int r = 2 * i + 2; // Utility function
}
void printArray(int[] arr) {
}
if (l < n && arr[l] > arr[largest]) for (int n : arr)
largest = l; [Link](n + " ");
void merge(int[] arr, int l, int m, int r) {
[Link]();
int n1 = m - l + 1;
if (r < n && arr[r] > arr[largest]) }
int n2 = r - m;
largest = r;
public static void main(String[] args) {
int[] L = new int[n1];
if (largest != i) { SortingMethods s = new SortingMethods();
int[] R = new int[n2];
int swap = arr[i]; int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
arr[i] = arr[largest]; int[] arr2 = [Link]();
for (int i = 0; i < n1; i++)

4/47 5/47 6/47

 int[] arr3 = [Link](); [Link] = new int[2 * t - 1]; if (children[i + 1].n == 2 * t - 1) {
[Link] = new BTreeNode[2 * t]; splitChild(i + 1, children[i + 1]);
[Link]("Original Array:"); this.n = 0; if (keys[i + 1] < k)
[Link](arr1); } i++;
}
[Link](arr1, 0, [Link] - 1); void traverse() { children[i + 1].insertNonFull(k);
[Link]("Merge Sorted:"); int i; }
[Link](arr1); for (i = 0; i < n; i++) { }
if (!leaf)
[Link](arr2); children[i].traverse(); void splitChild(int i, BTreeNode y) {
[Link]("Heap Sorted:"); [Link](keys[i] + " "); BTreeNode z = new BTreeNode(y.t, [Link]);
[Link](arr2); } z.n = t - 1;
if (!leaf)
[Link](arr3, 0, [Link] - 1); children[i].traverse(); for (int j = 0; j < t - 1; j++)
[Link]("Quick Sorted:"); } [Link][j] = [Link][j + t];
[Link](arr3);
} BTreeNode search(int k) { if (![Link]) {
} int i = 0; for (int j = 0; j < t; j++)
while (i < n && k > keys[i]) [Link][j] = [Link][j + t];
i++; }

3. Write a program to perform the following if (i < n && keys[i] == k) y.n = t - 1;

operations: return this; for (int j = n; j >= i + 1; j--)
a) Insert an element into a B- tree. children[j + 1] = children[j];
b) Delete an element from a B- tree. if (leaf) children[i + 1] = z;
c) Search for a key element in a B- tree. (write code in return null;
java and give answers only) for (int j = n - 1; j >= i; j--)
return children[i].search(k); keys[j + 1] = keys[j];
} keys[i] = [Link][t - 1];
java
n++;
void insertNonFull(int k) { }
import [Link].*;
int i = n - 1;
if (leaf) { void remove(int k) {
class BTreeNode {
while (i >= 0 && keys[i] > k) { int idx = findKey(k);
int[] keys;
keys[i + 1] = keys[i];
int t;
i--; if (idx < n && keys[idx] == k) {
BTreeNode[] children;
} if (leaf)
int n;
keys[i + 1] = k; removeFromLeaf(idx);
boolean leaf;
n++; else
} else { removeFromNonLeaf(idx);
BTreeNode(int t, boolean leaf) {
while (i >= 0 && keys[i] > k) } else {
this.t = t;
i--; if (leaf)
[Link] = leaf;

7/47 8/47 9/47

return; int getPred(int idx) {

BTreeNode cur = children[idx]; keys[idx - 1] = [Link][sibling.n - 1];
boolean flag = (idx == n); while (![Link]) child.n++;
if (children[idx].n < t) cur = [Link][cur.n]; sibling.n--;
fill(idx); return [Link][cur.n - 1]; }
}
if (flag && idx > n) void borrowFromNext(int idx) {
children[idx - 1].remove(k); int getSucc(int idx) { BTreeNode child = children[idx];
else BTreeNode cur = children[idx + 1]; BTreeNode sibling = children[idx + 1];
children[idx].remove(k); while (![Link])
} cur = [Link][0]; [Link][child.n] = keys[idx];
} return [Link][0];
} if (![Link])
int findKey(int k) { [Link][child.n + 1] = [Link][0];
int idx = 0; void fill(int idx) {
while (idx < n && keys[idx] < k) if (idx != 0 && children[idx - 1].n >= t) keys[idx] = [Link][0];
++idx; borrowFromPrev(idx);
return idx; else if (idx != n && children[idx + 1].n >= t) for (int i = 1; i < sibling.n; ++i)
} borrowFromNext(idx); [Link][i - 1] = [Link][i];
else {
void removeFromLeaf(int idx) { if (idx != n) if (![Link]) {
for (int i = idx + 1; i < n; ++i) merge(idx); for (int i = 1; i <= sibling.n; ++i)
keys[i - 1] = keys[i]; else [Link][i - 1] = [Link][i];
n--; merge(idx - 1); }
} }
} child.n++;
void removeFromNonLeaf(int idx) { sibling.n--;
int k = keys[idx]; void borrowFromPrev(int idx) { }
if (children[idx].n >= t) { BTreeNode child = children[idx];
int pred = getPred(idx); BTreeNode sibling = children[idx - 1]; void merge(int idx) {
keys[idx] = pred; BTreeNode child = children[idx];
children[idx].remove(pred); for (int i = child.n - 1; i >= 0; --i) BTreeNode sibling = children[idx + 1];
} else if (children[idx + 1].n >= t) { [Link][i + 1] = [Link][i];
int succ = getSucc(idx); [Link][t - 1] = keys[idx];
keys[idx] = succ; if (![Link]) {
children[idx + 1].remove(succ); for (int i = child.n; i >= 0; --i) for (int i = 0; i < sibling.n; ++i)
} else { [Link][i + 1] = [Link][i]; [Link][i + t] = [Link][i];
merge(idx); }
children[idx].remove(k); if (![Link]) {
} [Link][0] = keys[idx - 1]; for (int i = 0; i <= sibling.n; ++i)
} if (!leaf) [Link][i + t] = [Link][i];
[Link][0] = [Link][sibling.n]; }

10/47 11/47 12/47

 [Link][i].insertNonFull(k);
for (int i = idx + 1; i < n; ++i) root = s; [Link](13);
keys[i - 1] = keys[i]; } else [Link]("\nTraversal after removing 13 (not present):");
for (int i = idx + 2; i <= n; ++i) [Link](k); [Link]();
children[i - 1] = children[i]; }
} [Link](7);
child.n += sibling.n + 1; [Link]("\nTraversal after removing 7:");
n--; void remove(int k) { [Link]();
} if (root == null)
} return; [Link](4);
[Link]("\nTraversal after removing 4 (not present):");
class BTree { [Link](k); [Link]();
BTreeNode root;
int t; if (root.n == 0) { [Link](2);
if ([Link]) [Link]("\nTraversal after removing 2 (not present):");
BTree(int t) { root = null; [Link]();
[Link] = null; else
this.t = t; root = [Link][0]; [Link](16);
} } [Link]("\nTraversal after removing 16 (not present):");
} [Link]();
void traverse() { }
if (root != null) [Link](); public static void main(String[] args) { }
} BTree t = new BTree(3); // t is degree

BTreeNode search(int k) { [Link](10);

return (root == null) ? null : [Link](k); [Link](20); 4. Write a program to perform the following
} [Link](5); operations:
[Link](6); a) Insert an element into a Min-Max heap
void insert(int k) { [Link](12); b) Delete an element from a Min-Max heap
if (root == null) { [Link](30); c) Search for a key element in a Min-Max heap (write
root = new BTreeNode(t, true); [Link](7); code in java and give answers only)
[Link][0] = k; [Link](17);
root.n = 1;
java
} else { [Link]("Traversal of B-Tree:");
if (root.n == 2 * t - 1) { [Link]();
import [Link].*;
BTreeNode s = new BTreeNode(t, false);
[Link][0] = root; [Link]("\nSearch key 6: " + ([Link](6) != null));
class MinMaxHeap {
[Link](0, root); [Link]("Search key 15: " + ([Link](15) != null));
private List<Integer> heap;

int i = 0; [Link](6);
public MinMaxHeap() {
if ([Link][0] < k) [Link]("Traversal after removing 6:");
heap = new ArrayList<>();
i++; [Link]();
}

13/47 14/47 15/47

} swap(m, parent);
private boolean isMinLevel(int index) { trickleDownMin(m);
int level = (int) ([Link](index + 1) / [Link](2)); private void bubbleUpMin(int i) { }
return level % 2 == 0; int gp = parent(parent(i)); } else if ([Link](m) < [Link](i)) {
} if (gp >= 0 && [Link](i) < [Link](gp)) { swap(m, i);
swap(i, gp); }
private int parent(int i) { bubbleUpMin(gp); }
return (i - 1) / 2; }
} } private void trickleDownMax(int i) {
int m = largestDescendant(i);
private int leftChild(int i) { private void bubbleUpMax(int i) { if (m == -1) return;
return 2 * i + 1; int gp = parent(parent(i));
} if (gp >= 0 && [Link](i) > [Link](gp)) { if (isGrandchild(i, m)) {
swap(i, gp); if ([Link](m) > [Link](i)) {
private int rightChild(int i) { bubbleUpMax(gp); swap(m, i);
return 2 * i + 2; } int parent = parent(m);
} } if ([Link](m) < [Link](parent))
swap(m, parent);
// Insert an element // Delete root element (min or max) trickleDownMax(m);
public void insert(int key) { public void deleteRoot() { }
[Link](key); if ([Link]()) return; } else if ([Link](m) > [Link](i)) {
bubbleUp([Link]() - 1); [Link](0, [Link]([Link]() - 1)); swap(m, i);
} [Link]([Link]() - 1); }
trickleDown(0); }
private void bubbleUp(int i) { }
if (i == 0) return; private boolean isGrandchild(int i, int m) {
int p = parent(i); private void trickleDown(int i) { return parent(parent(m)) == i;
if (isMinLevel(i)) { if (isMinLevel(i)) }
if ([Link](i) > [Link](p)) { trickleDownMin(i);
swap(i, p); else private int smallestDescendant(int i) {
bubbleUpMax(p); trickleDownMax(i); int size = [Link]();
} else { } int smallest = -1;
bubbleUpMin(i); int minVal = Integer.MAX_VALUE;
} private void trickleDownMin(int i) {
} else { int m = smallestDescendant(i); int[] indices = {leftChild(i), rightChild(i),
if ([Link](i) < [Link](p)) { if (m == -1) return; leftChild(leftChild(i)), rightChild(leftChild(i)),
swap(i, p); leftChild(rightChild(i)), rightChild(rightChild(i))};
bubbleUpMin(p); if (isGrandchild(i, m)) {
} else { if ([Link](m) < [Link](i)) { for (int idx : indices) {
bubbleUpMax(i); swap(m, i); if (idx < size && [Link](idx) < minVal) {
} int parent = parent(m); minVal = [Link](idx);
} if ([Link](m) > [Link](parent)) smallest = idx;

16/47 17/47 18/47

 } [Link](40); class LeftistHeap {
} [Link](30); private LeftistNode root;
return smallest; [Link](5);
} [Link](60); LeftistHeap() {
[Link](15); root = null;
private int largestDescendant(int i) { [Link](70); }
int size = [Link]();
int largest = -1; [Link]("Min-Max Heap:"); // Merge two leftist trees
int maxVal = Integer.MIN_VALUE; [Link](); private LeftistNode merge(LeftistNode h1, LeftistNode h2) {
if (h1 == null) return h2;
int[] indices = {leftChild(i), rightChild(i), [Link]("Search 15: " + [Link](15)); if (h2 == null) return h1;
leftChild(leftChild(i)), rightChild(leftChild(i)), [Link]("Search 100: " + [Link](100));
leftChild(rightChild(i)), rightChild(rightChild(i))}; if ([Link] > [Link]) {
[Link](); LeftistNode temp = h1;
for (int idx : indices) { [Link]("After deleting root:"); h1 = h2;
if (idx < size && [Link](idx) > maxVal) { [Link](); h2 = temp;
maxVal = [Link](idx); } }
largest = idx; }
} [Link] = merge([Link], h2);
}
return largest; if (getNPL([Link]) < getNPL([Link]))
} 5. Write a program to perform the following swapChildren(h1);
operations:
// Search for a key element a) Insert an element into a Lefiist tree [Link] = getNPL([Link]) + 1;
public boolean search(int key) { b) Delete an element from a Leftist tree return h1;
return [Link](key); c) Search for a key element in a Leftist tree (write code }
} in java and give answers only)
private int getNPL(LeftistNode node) {
private void swap(int i, int j) { return (node == null) ? -1 : [Link];
java
int temp = [Link](i); }
[Link](i, [Link](j));
class LeftistNode {
[Link](j, temp); private void swapChildren(LeftistNode node) {
int key;
} LeftistNode temp = [Link];
LeftistNode left, right;
[Link] = [Link];
int npl; // Null path length
public void display() { [Link] = temp;
[Link](heap); }
LeftistNode(int key) {
}
[Link] = key;
// Insert an element
left = right = null;
public static void main(String[] args) { public void insert(int key) {
npl = 0;
MinMaxHeap mmh = new MinMaxHeap(); LeftistNode newNode = new LeftistNode(key);
}
root = merge(root, newNode);
}
[Link](10); }

19/47 20/47 21/47

[Link](5); [Link] = key;

// Delete the minimum element (root) [Link](30); [Link] = 0;
public void deleteMin() { [Link](20); [Link] = null;
if (root == null) { [Link](60); [Link] = null;
[Link]("Heap is empty"); [Link] = null;
return; [Link]("Inorder traversal of Leftist Tree:"); }
} [Link](); }
[Link]("Deleted element: " + [Link]);
root = merge([Link], [Link]); [Link]("Search 30: " + [Link](30)); class BinomialHeap {
} [Link]("Search 100: " + [Link](100)); private BinomialNode head;

// Search for a key [Link](); BinomialHeap() {

public boolean search(int key) { [Link]("Inorder after deleting min:"); head = null;
return searchRec(root, key); [Link](); }
}
[Link](); // Merge two binomial trees of same degree
private boolean searchRec(LeftistNode node, int key) { [Link]("Inorder after deleting another min:"); private BinomialNode mergeTrees(BinomialNode b1, BinomialNode b2) {
if (node == null) return false; [Link](); if ([Link] > [Link]) {
if ([Link] == key) return true; } BinomialNode temp = b1;
if (key < [Link]) return searchRec([Link], key); } b1 = b2;
return searchRec([Link], key); b2 = temp;
} }
[Link] = b1;
// Inorder traversal 6. Write a program to perform the following [Link] = [Link];
public void inorder() { operations: [Link] = b2;
inorderRec(root); a) Insert an element into a binomial heap [Link]++;
[Link](); b) Delete an element from a binomial heap. return b1;
} c) Search for a key element in a binomial heap (write }
code in java and give answers only)
private void inorderRec(LeftistNode node) { // Merge two binomial heaps
if (node != null) { private BinomialNode mergeHeaps(BinomialNode h1, BinomialNode h2) {
java
inorderRec([Link]); if (h1 == null) return h2;
[Link]([Link] + " "); if (h2 == null) return h1;
import [Link].*;
inorderRec([Link]);
} BinomialNode head;
class BinomialNode {
} BinomialNode tail;
int key;
BinomialNode a = h1;
int degree;
public static void main(String[] args) { BinomialNode b = h2;
BinomialNode parent;
LeftistHeap heap = new LeftistHeap();
BinomialNode child;
if ([Link] <= [Link]) {
BinomialNode sibling;
[Link](10); head = a;
[Link](40); a = [Link];
BinomialNode(int key) {

22/47 23/47 24/47

 } else { else [Link] = next; curr = [Link];
head = b; next = mergeTrees(next, curr); }
b = [Link]; curr = next; if ([Link] == minNode)
} } prevMin = curr;
}
tail = head; next = [Link]; if (prevMin != null)
} [Link] = [Link];
while (a != null && b != null) { return newHead; else
if ([Link] <= [Link]) { } head = [Link];
[Link] = a;
a = [Link]; // Insert an element BinomialNode child = [Link];
} else { public void insert(int key) { BinomialNode prev = null;
[Link] = b; BinomialHeap tempHeap = new BinomialHeap(); while (child != null) {
b = [Link]; [Link] = new BinomialNode(key); BinomialNode next = [Link];
} head = union(head, [Link]); [Link] = prev;
tail = [Link]; } [Link] = null;
} prev = child;
// Find minimum node child = next;
[Link] = (a != null) ? a : b; private BinomialNode findMinNode() { }
return head; if (head == null) return null;
} BinomialNode y = null; head = union(head, prev);
BinomialNode x = head; }
// Union operation int min = Integer.MAX_VALUE;
private BinomialNode union(BinomialNode h1, BinomialNode h2) { while (x != null) { // Search for a key element
BinomialNode newHead = mergeHeaps(h1, h2); if ([Link] < min) { public boolean search(int key) {
if (newHead == null) return null; min = [Link]; return searchRec(head, key);
y = x; }
BinomialNode prev = null; }
BinomialNode curr = newHead; x = [Link]; private boolean searchRec(BinomialNode node, int key) {
BinomialNode next = [Link]; } if (node == null) return false;
return y; if ([Link] == key) return true;
while (next != null) { } return searchRec([Link], key) || searchRec([Link], key);
if ([Link] != [Link] || }
([Link] != null && [Link] == [Link])) { // Delete minimum node
prev = curr; public void deleteMin() { // Display heap
curr = next; if (head == null) return; public void display() {
} else { displayRec(head);
if ([Link] <= [Link]) { BinomialNode minNode = findMinNode(); [Link]();
[Link] = [Link]; BinomialNode prevMin = null; }
curr = mergeTrees(curr, next); BinomialNode curr = head;
} else { private void displayRec(BinomialNode node) {
if (prev == null) newHead = next; while ([Link] != null && [Link] != minNode) { while (node != null) {

25/47 26/47 27/47

[Link]([Link] + " "); [Link] = [Link](height([Link]), height([Link])) + 1;

class AVLNode {
displayRec([Link]);
int key, height;
node = [Link]; return y;
AVLNode left, right;
} }
}
AVLNode(int d) {
// Insert operation
key = d;
public static void main(String[] args) { public AVLNode insert(AVLNode node, int key) {
height = 1;
BinomialHeap heap = new BinomialHeap(); if (node == null)
}
return new AVLNode(key);
}
[Link](10);
[Link](20); if (key < [Link])
class AVLTree {
[Link](5); [Link] = insert([Link], key);
private AVLNode root;
[Link](30); else if (key > [Link])
[Link](15); [Link] = insert([Link], key);
private int height(AVLNode N) {
else
return (N == null) ? 0 : [Link];
[Link]("Binomial Heap:"); return node;
}
[Link]();
[Link] = 1 + [Link](height([Link]), height([Link]));
private int getBalance(AVLNode N) {
[Link]("Search 15: " + [Link](15)); int balance = getBalance(node);
return (N == null) ? 0 : height([Link]) - height([Link]);
[Link]("Search 100: " + [Link](100));
}
// Balancing cases
[Link](); if (balance > 1 && key < [Link])
private AVLNode rightRotate(AVLNode y) {
[Link]("After deleting min:"); return rightRotate(node);
AVLNode x = [Link];
[Link]();
AVLNode T2 = [Link];
if (balance < -1 && key > [Link])
[Link](); return leftRotate(node);
[Link] = y;
[Link]("After deleting another min:");
[Link] = T2;
[Link](); if (balance > 1 && key > [Link]) {
} [Link] = leftRotate([Link]);
[Link] = [Link](height([Link]), height([Link])) + 1;
} return rightRotate(node);
[Link] = [Link](height([Link]), height([Link])) + 1;
}

return x;
if (balance < -1 && key < [Link]) {
}
7. Write a program to perform the following [Link] = rightRotate([Link]);
operations: return leftRotate(node);
private AVLNode leftRotate(AVLNode x) {
a) Insert an element into a AVL tree. }
AVLNode y = [Link];
b) Delete an element from a AVL search tree.
AVLNode T2 = [Link];
c) Search for a key element in a AVL search tree. (write return node;
code in java and give answers only) }
[Link] = x;
[Link] = T2;
// Minimum value node
java
private AVLNode minValueNode(AVLNode node) {
[Link] = [Link](height([Link]), height([Link])) + 1;

28/47 29/47 30/47

 AVLNode current = node; return leftRotate(root); [Link]("Search 100: " + [Link](root, 100));
while ([Link] != null)
current = [Link]; if (balance < -1 && getBalance([Link]) > 0) { root = [Link](root, 40);
return current; [Link] = rightRotate([Link]); [Link]("Inorder after deleting 40:");
} return leftRotate(root); [Link](root);
} [Link]();
// Delete operation }
public AVLNode deleteNode(AVLNode root, int key) { return root; }
if (root == null) }
return root;
// Search operation
if (key < [Link]) public boolean search(AVLNode root, int key) { 8. Write a program to perform the following
[Link] = deleteNode([Link], key); if (root == null) return false; operations:
else if (key > [Link]) if ([Link] == key) return true; a) Insert an element into a Red-Black tree.
[Link] = deleteNode([Link], key); return (key < [Link]) ? search([Link], key) : search([Link], key); b) Delete an element from a Red-Black tree. c) Search
else { } for a key element in a Red-Black tree. (write code in
if (([Link] == null) || ([Link] == null)) { java and give answers only)
AVLNode temp = ([Link] != null) ? [Link] : [Link]; // Inorder traversal
root = (temp == null) ? null : temp; public void inorder(AVLNode node) {
java
} else { if (node != null) {
AVLNode temp = minValueNode([Link]); inorder([Link]);
class RedBlackNode {
[Link] = [Link]; [Link]([Link] + " ");
int data;
[Link] = deleteNode([Link], [Link]); inorder([Link]);
RedBlackNode left, right, parent;
} }
boolean color; // true = Red, false = Black
} }

public RedBlackNode(int data) {

if (root == null) public static void main(String[] args) {
[Link] = data;
return root; AVLTree tree = new AVLTree();
[Link] = true;
AVLNode root = null;
}
[Link] = [Link](height([Link]), height([Link])) + 1;
}
int balance = getBalance(root); root = [Link](root, 10);
root = [Link](root, 20);
class RedBlackTree {
// Balancing cases root = [Link](root, 30);
private RedBlackNode root;
if (balance > 1 && getBalance([Link]) >= 0) root = [Link](root, 40);
private final RedBlackNode NIL;
return rightRotate(root); root = [Link](root, 50);
root = [Link](root, 25);
public RedBlackTree() {
if (balance > 1 && getBalance([Link]) < 0) {
NIL = new RedBlackNode(0);
[Link] = leftRotate([Link]); [Link]("Inorder traversal of AVL Tree:");
[Link] = false;
return rightRotate(root); [Link](root);
[Link] = [Link] = null;
} [Link]();
root = NIL;
}
if (balance < -1 && getBalance([Link]) <= 0) [Link]("Search 25: " + [Link](root, 25));

31/47 32/47 33/47

// Left Rotate if ([Link] == [Link]) { [Link] = NIL;

private void leftRotate(RedBlackNode x) { u = [Link];
RedBlackNode y = [Link]; if ([Link]) { // Case 1 RedBlackNode y = null;
[Link] = [Link]; [Link] = false; RedBlackNode x = root;
if ([Link] != NIL) [Link] = false;
[Link] = x; [Link] = true; while (x != NIL) {
k = [Link]; y = x;
[Link] = [Link]; } else { if ([Link] < [Link])
if ([Link] == null) if (k == [Link]) { // Case 2 x = [Link];
root = y; k = [Link]; else
else if (x == [Link]) leftRotate(k); x = [Link];
[Link] = y; } }
else [Link] = false; // Case 3
[Link] = y; [Link] = true; [Link] = y;
rightRotate([Link]); if (y == null)
[Link] = x; } root = node;
[Link] = y; } else { else if ([Link] < [Link])
} u = [Link]; [Link] = node;
if ([Link]) { // Mirror Case 1 else
// Right Rotate [Link] = false; [Link] = node;
private void rightRotate(RedBlackNode y) { [Link] = false;
RedBlackNode x = [Link]; [Link] = true; if ([Link] == null) {
[Link] = [Link]; k = [Link]; [Link] = false;
if ([Link] != NIL) } else { return;
[Link] = y; if (k == [Link]) { // Mirror Case 2 }
k = [Link];
[Link] = [Link]; rightRotate(k); if ([Link] == null)
if ([Link] == null) } return;
root = x; [Link] = false; // Mirror Case 3
else if (y == [Link]) [Link] = true; fixInsert(node);
[Link] = x; leftRotate([Link]); }
else }
[Link] = x; } // Transplant
} private void transplant(RedBlackNode u, RedBlackNode v) {
[Link] = y; [Link] = false; if ([Link] == null)
[Link] = x; } root = v;
} else if (u == [Link])
// Insert a node [Link] = v;
// Fix violations after insert public void insert(int key) { else
private void fixInsert(RedBlackNode k) { RedBlackNode node = new RedBlackNode(key); [Link] = v;
RedBlackNode u; [Link] = null; [Link] = [Link];
while ([Link] != null && [Link]) { [Link] = NIL; }

34/47 35/47 36/47

 } if (![Link] && ![Link]) {
private RedBlackNode minimum(RedBlackNode node) { [Link] = true;
while ([Link] != NIL) if (!yOriginalColor) x = [Link];
node = [Link]; fixDelete(x); } else {
return node; } if (![Link]) {
} [Link] = false;
// Fix violations after delete [Link] = true;
// Delete node private void fixDelete(RedBlackNode x) { leftRotate(s);
public void delete(int key) { RedBlackNode s; s = [Link];
RedBlackNode z = searchNode(root, key); while (x != root && ![Link]) { }
if (z == NIL) { if (x == [Link]) { [Link] = [Link];
[Link]("Key not found in tree."); s = [Link]; [Link] = false;
return; if ([Link]) { // Case 1 [Link] = false;
} [Link] = false; rightRotate([Link]);
[Link] = true; x = root;
RedBlackNode y = z; leftRotate([Link]); }
RedBlackNode x; s = [Link]; }
boolean yOriginalColor = [Link]; } }
if (![Link] && ![Link]) { // Case 2 [Link] = false;
if ([Link] == NIL) { [Link] = true; }
x = [Link]; x = [Link];
transplant(z, [Link]); } else { // Search for a key
} else if ([Link] == NIL) { if (![Link]) { // Case 3 public boolean search(int key) {
x = [Link]; [Link] = false; return searchNode(root, key) != NIL;
transplant(z, [Link]); [Link] = true; }
} else { rightRotate(s);
y = minimum([Link]); s = [Link]; private RedBlackNode searchNode(RedBlackNode node, int key) {
yOriginalColor = [Link]; } if (node == NIL || key == [Link])
x = [Link]; [Link] = [Link]; // Case 4 return node;
[Link] = false; if (key < [Link])
if ([Link] == z) [Link] = false; return searchNode([Link], key);
[Link] = y; leftRotate([Link]); return searchNode([Link], key);
else { x = root; }
transplant(y, [Link]); }
[Link] = [Link]; } else { // Inorder traversal
[Link] = y; s = [Link]; public void inorder(RedBlackNode node) {
} if ([Link]) { if (node != NIL) {
[Link] = false; inorder([Link]);
transplant(z, y); [Link] = true; [Link]([Link] + " ");
[Link] = [Link]; rightRotate([Link]); inorder([Link]);
[Link] = y; s = [Link]; }
[Link] = [Link]; } }

37/47 38/47 39/47

class HashDictionary { return [Link];

public void printTree() { private static final int SIZE = 10; }
inorder(root); private LinkedList<Entry>[] table; return null;
[Link](); }
} static class Entry {
String key; // Delete a key
public static void main(String[] args) { String value; public void delete(String key) {
RedBlackTree tree = new RedBlackTree(); int index = hash(key);
Entry(String key, String value) { Iterator<Entry> it = table[index].iterator();
[Link](20); [Link] = key; while ([Link]()) {
[Link](15); [Link] = value; Entry e = [Link]();
[Link](25); } if ([Link](key)) {
[Link](10); } [Link]();
[Link](30); [Link]("Deleted: " + key);
[Link](5); @SuppressWarnings("unchecked") return;
public HashDictionary() { }
[Link]("Inorder traversal after insertions:"); table = new LinkedList[SIZE]; }
[Link](); for (int i = 0; i < SIZE; i++) [Link]("Key not found: " + key);
table[i] = new LinkedList<>(); }
[Link]("Search 15: " + [Link](15)); }
[Link]("Search 50: " + [Link](50)); // Display dictionary
private int hash(String key) { public void display() {
[Link](10); return [Link]([Link]() % SIZE); for (int i = 0; i < SIZE; i++) {
[Link]("Inorder after deleting 10:"); } [Link]("Bucket " + i + ": ");
[Link](); for (Entry e : table[i]) {
// Insert a key-value pair [Link]("[" + [Link] + "=" + [Link] + "] ");
[Link](25); public void insert(String key, String value) { }
[Link]("Inorder after deleting 25:"); int index = hash(key); [Link]();
[Link](); for (Entry e : table[index]) { }
} if ([Link](key)) { }
} [Link] = value;
return; public static void main(String[] args) {
} HashDictionary dict = new HashDictionary();
}
9. Write a program to implement all the functions of a table[index].add(new Entry(key, value)); [Link]("apple", "A fruit");
dictionary using hashing. (write code in java and give } [Link]("java", "A programming language");
answers only) [Link]("book", "A source of knowledge");
// Search for a key [Link]("pen", "A writing tool");
public String search(String key) {
java
int index = hash(key); [Link]("Dictionary after insertions:");
for (Entry e : table[index]) { [Link]();
import [Link].*;
if ([Link](key))

40/47 41/47 42/47

 [Link]("Search 'java': " + [Link]("java")); void KMPSearch(String pat, String txt) { give answers only)
[Link]("Search 'car': " + [Link]("car")); int M = [Link]();
int N = [Link]();
java
[Link]("apple"); int[] lps = new int[M];
[Link]("After deleting 'apple':");
class BruteForcePatternMatching {
[Link](); computeLPSArray(pat, M, lps);
}
// Brute force search: prints all occurrences of pattern in text
} int i = 0; // index for txt
public void bruteForceSearch(String txt, String pat) {
int j = 0; // index for pat
int n = [Link]();
int m = [Link]();
while (i < N) {
10. Write a program for implementing Knuth-Morris- if ([Link](j) == [Link](i)) {
for (int i = 0; i <= n - m; i++) {
Pratt pattern matching algorithm. (write code in java i++;
int j;
and give answers only) j++;
for (j = 0; j < m; j++) {
}
if ([Link](i + j) != [Link](j))
java break;
if (j == M) {
}
[Link]("Pattern found at index " + (i - j));
class KMPAlgorithm { if (j == m) {
j = lps[j - 1];
[Link]("Pattern found at index " + i);
} else if (i < N && [Link](j) != [Link](i)) {
// Compute longest prefix-suffix (LPS) array }
if (j != 0)
void computeLPSArray(String pat, int M, int[] lps) { }
j = lps[j - 1];
int len = 0; }
else
int i = 1;
i++;
lps[0] = 0; // Check if pattern exists in text (returns boolean)
}
public boolean contains(String txt, String pat) {
}
while (i < M) { int n = [Link]();
}
if ([Link](i) == [Link](len)) { int m = [Link]();
len++;
public static void main(String[] args) {
lps[i] = len; for (int i = 0; i <= n - m; i++) {
KMPAlgorithm kmp = new KMPAlgorithm();
i++; int j;
String txt = "ABABDABACDABABCABAB";
} else { for (j = 0; j < m; j++) {
String pat = "ABABCABAB";
if (len != 0) if ([Link](i + j) != [Link](j))
[Link]("Text: " + txt);
len = lps[len - 1]; break;
[Link]("Pattern: " + pat);
else { }
[Link](pat, txt);
lps[i] = 0; if (j == m) return true;
}
i++; }
}
} return false;
} }
}
} public static void main(String[] args) {
11. Write a program for implementing Brute Force BruteForcePatternMatching bf = new BruteForcePatternMatching();
pattern matching algorithm. (write code in java and String txt = "THIS IS A SIMPLE EXAMPLE";
// KMP Search function

43/47 44/47 45/47

String pat = "SIMPLE"; int j = m - 1;

[Link]("Text: " + txt); while (j >= 0 && [Link](j) == [Link](s + j))

[Link]("Pattern: " + pat); j--;
[Link](txt, pat);
if (j < 0) {
[Link]("Contains pattern? " + [Link](txt, pat)); [Link]("Pattern found at index " + s);
} s += (s + m < n) ? m - badChar[[Link](s + m)] : 1;
} } else {
s += [Link](1, j - badChar[[Link](s + j)]);
}
}
12. Write a program for implementing Boyer pattern }
matching algorithm.(write code in java and give
answers only) public static void main(String[] args) {
BoyerMooreAlgorithm bm = new BoyerMooreAlgorithm();
String txt = "AABAACAADAABAABA";
java
String pat = "AABA";

class BoyerMooreAlgorithm {
[Link]("Text: " + txt);
[Link]("Pattern: " + pat);
private final int ALPHABET_SIZE = 256;
[Link](txt, pat);
}
// Function to create the bad character heuristic table
}
private void badCharHeuristic(String pat, int[] badChar) {
int m = [Link]();
for (int i = 0; i < ALPHABET_SIZE; i++)
badChar[i] = -1;

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

badChar[[Link](i)] = i;
}

// Boyer-Moore search function

public void search(String txt, String pat) {
int m = [Link]();
int n = [Link]();
int[] badChar = new int[ALPHABET_SIZE];

badCharHeuristic(pat, badChar);

int s = 0; // shift of the pattern with respect to text

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

46/47 47/47