Data Structures (15B11CI311)

Assignment
Sahil Srivastava
9923103032
F2 Batch

Ans 1)
#include <iostream>
#include <queue>
#include <set>
using namespace std;

class MedianFinder {
private:
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
multiset<int> data;

public:
void insert(int num) {
data.insert(num);
if (maxHeap.empty() || num <= maxHeap.top()) {
maxHeap.push(num);
} else {
minHeap.push(num);
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}

void remove(int num) {

auto it = data.find(num);
if (it != data.end()) {
data.erase(it);
 if (!maxHeap.empty() && num <= maxHeap.top()) {
maxHeap.pop();
} else {
minHeap.pop();
}
}

while (maxHeap.size() > minHeap.size() + 1) {

minHeap.push(maxHeap.top());
maxHeap.pop();
}

while (minHeap.size() > maxHeap.size()) {

maxHeap.push(minHeap.top());
minHeap.pop();
}
}

double getMedian() {
if (maxHeap.size() > minHeap.size()) {
return maxHeap.top();
} else {
return (maxHeap.top() + minHeap.top()) / 2.0;
}
}
};

int main() {
MedianFinder mf;
int ch, num;

while (true) {
cout << "1. Insert\n2. Remove\n3. Get Median\n4. Exit\n";
cout << "Enter choice: ";
cin >> ch;

switch (ch) {
case 1:
cout << "Enter number to insert: ";
cin >> num;
mf.insert(num);
 break;
case 2:
cout << "Enter number to remove: ";
cin >> num;
mf.remove(num);
break;
case 3:
cout << "Median: " << mf.getMedian() << "\n";
break;
case 4:
return 0;
default:
cout << "Invalid choice. Try again.\n";
}
}
}

Ans 2)
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
map<char, Node*>
next; bool endMarker =
false; int count = 0;
};
class SearchHelper {
private:
Node* base;
void gatherWords(Node* current, string buildPrefix,
vector<pair<string, int>>& results) {
if (!current) return;
 if (current->endMarker)
results.push_back({buildPrefix, current->count});
for (auto& child : current->next)
gatherWords(child.second, buildPrefix +
child.first, results);
}
public:
SearchHelper() {base = new Node(); }
void addEntry(const string& term, int weight = 1) {
Node* pointer = base;
for (char symbol : term) {
if (!pointer->next[symbol]) pointer->next[symbol]
= new Node();
pointer = pointer->next[symbol];
}
pointer->endMarker =
true; pointer->count +=
weight;
}
vector<string> fetchMatches(const string& start) {
Node* pointer = base;
for (char symbol : start) {
if (!pointer->next[symbol]) return
{}; pointer = pointer->next[symbol];
}
vector<pair<string, int>> results;
gatherWords(pointer, start, results);
sort(results.begin(), results.end(), [](const pair<string,
int>& a, const pair<string, int>& b) {
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
vector<string> output;
for (auto& result : results)
output.push_back(result.first);
return output;}};
int main() {
SearchHelper helper;
int entries;
cout << "Number of terms to add: ";
 cin >> entries;
for (int i = 0; i < entries; ++i) {
string term;
int weight;
cout << "Enter term and weight: ";
cin >> term >> weight;
helper.addEntry(term, weight);
}
while (true) {
string queryStart;
cout << "Enter query prefix (type 'stop' to exit):
";
cin >> queryStart;
if (queryStart == "stop") break;
vector<string> matches =
helper.fetchMatches(queryStart);
if (matches.empty()) {
cout << "No matches found.\n";
} else {
cout << "Matches:\n";
for (const string& match : matches)
cout << match << "\n";
}
}
return 0;
ANS 3)

CODE
#include <iostream>
using namespace std;
template <class T>
class queue {
private:
int size;
int front;
int rear;
T* arr;
public:
queue(int size) {
this->size = size;
front = rear = 0;
arr = new T[size];
}
bool isEmpty() { return (front == rear); }
bool isFull() { return ((rear + 1) % size == front); }
void enqueue(T val) {
if (isFull()) {
cout << "Queue is full! Cannot enqueue " <<
val << endl;
return;
}
rear = (rear + 1) % size;
 arr[rear] = val;
}
T dequeue() {
if (isEmpty()) {
cout << "Queue is empty! Cannot dequeue."
<< endl;
return T();
}
front = (front + 1) % size;
return arr[front];
}
void display() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return;
}
cout << "Queue state: ";
for (int i = (front + 1) % size; i != (rear + 1) %
size; i = (i + 1) % size) {
cout << arr[i] << " ";
}
cout << endl;
}

int getSize() {
int count = (rear - front + size) % size;
return count;
}
};

int main() {
int n = 6;
queue<int> q(n + 1);
cout << "Enqueue tasks 1 to " << n << ":" << endl;
for (int i = 1; i <= n; i++)
q.enqueue(i);
q.display();
cout << "Processed tasks (dequeue 3): ";
for (int i = 0; i < 3; i++)
cout << q.dequeue() << " ";
cout << endl;
q.display();
cout << "Enqueue tasks " << n + 1 << " to " << n +
3 << ":" << endl;
 for (int i = n + 1; i <= n + 3; i++)
q.enqueue(i);
q.display();
cout << "Processed tasks (dequeue 2): ";
for (int i = 0; i < 2; i++)
cout << q.dequeue() << " ";
cout << endl;
q.display();
cout << "Final queue state: ";
q.display();
cout << "Final queue size: " << q.getSize() << endl;
return 0;
}

Ans 4)

Initial Linked List:

10 -> 20 -> 30 -> 40 ->50
Step 1: Reverse the List:
50 -> 40->30->20->10
Step 2: Insert 25 After 20:
50->40->30->20->25->10
Step 3: Delete the Node with Value
40: 50->30->20->25->10
Step 4: Merge with Another Linked List:
50->30->20->25->10->100->200->300
Final Linked List:
Elements: 50,30,20,25,10,100,200,300
Length: 8

CODE
#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
};

Node* reverseList(Node* head) {

Node* prev = nullptr;
Node* current = head;
 Node* next = nullptr;
while (current) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

void insertAfter(Node* head, int value, int newData) {

Node* current = head;
while (current && current->data != value)
current = current->next;
if (current) {
Node* newNode = new Node{newData, current->next};
current->next = newNode;
}
}

Node* deleteNode(Node* head, int value) {

if (!head) return nullptr;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return head;
}

Node* current = head;

while (current->next && current->next->data != value)
current = current->next;
if (current->next) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
return head;
}

Node* mergeLists(Node* list1, Node* list2) {

 if (!list1) return list2;
if (!list2) return list1;
Node* current = list1;
while (current->next) {
current = current->next;
}
current->next = list2;
return list1;
}

void printList(Node* head) {

Node* current = head;
while (current) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}

int main() {
Node* list1 = new Node{10, new Node{20, new Node{30, new Node{40, new Node{50,
nullptr}}}}};
list1 = reverseList(list1);
insertAfter(list1, 20, 25);
list1 = deleteNode(list1, 40);
Node* list2 = new Node{100, new Node{200, new Node{300, nullptr}}};
Node* finalList = mergeLists(list1, list2);

cout << "Final List: ";

printList(finalList);

int length = 0;
Node* current = finalList;
while (current) {
length++;
current = current->next;
}

cout << "Length: " << length << endl;

return 0;
}
ANS 5)
INSERTION IN RB TR
 Root Node Color: Black

Root Children Colors:

 Left Child: Black

 Right Child : Black

Properties of a Red-Black Tree:

1. Every node is either red or black.

2. The root is always black.

3. Red nodes cannot have red children (no two consecutive red nodes).

4. Every path from a node to its descendant NULL pointers contains the
same number of black nodes (black-height property).

Insertions into the AVL Tree:

CODE
#include <bits/stdc++.h>
using namespace std;
enum Color { RED, BLACK };
struct Node {
int data;
int color;
Node *left, *right, *parent;
explicit Node(int data) {
this->data = data;
color = RED;
left = right = parent = nullptr;
}
};
class RBTree {
private:
Node *root;
protected:
void rotateLeft(Node *&);
void rotateRight(Node *&);
void fixInsertRBTree(Node
*&); void inorderBST(Node
*&);
int getColor(Node *&);
void setColor(Node *&, int);
Node *insertBST(Node *&, Node *&);
public:
RBTree();
void insertValue(int);
void inorder();
};
RBTree::RBTree() {
root = nullptr;
}
int RBTree::getColor(Node *&node)
{ if (node == nullptr) return
BLACK; return node->color;
}
void RBTree::setColor(Node *&node, int color) {
if (node == nullptr) return;
 node->color = color;
}

Node *RBTree::insertBST(Node *&root, Node *&ptr) {

if (root == nullptr) return ptr;

if (ptr->data < root->data) {

root->left = insertBST(root->left, ptr);
root->left->parent = root;
} else if (ptr->data > root->data) {
root->right = insertBST(root->right, ptr);
root->right->parent = root;
}
return root;
}
void RBTree::rotateLeft(Node *&ptr)
{ Node *right_child = ptr->right;
ptr->right = right_child-
>left; if (ptr->right !=
nullptr)
ptr->right->parent = ptr;
right_child->parent = ptr-
>parent; if (ptr->parent ==
nullptr)
root = right_child;
else if (ptr == ptr->parent->left)
ptr->parent->left =
right_child;
else
ptr->parent->right = right_child;
right_child->left = ptr;
ptr->parent =
right_child;
}
void RBTree::rotateRight(Node *&ptr)
{ Node *left_child = ptr->left;
ptr->left = left_child->right;
if (ptr->left != nullptr)
ptr->left->parent = ptr;
left_child->parent = ptr-
>parent; if (ptr->parent ==
 nullptr)
root = left_child;
else if (ptr == ptr->parent->left)
ptr->parent->left =
left_child;
else
ptr->parent->right =
left_child; left_child->right = ptr;
ptr->parent = left_child;
}
void RBTree::fixInsertRBTree(Node *&ptr)
{ Node *parent = nullptr;
Node *grandparent = nullptr;
while (ptr != root && getColor(ptr) == RED && getColor(ptr->parent) == RED) {
parent = ptr->parent;
grandparent = parent->parent;
if (parent == grandparent->left) {
Node *uncle = grandparent->right;
if (getColor(uncle) == RED) {
setColor(uncle, BLACK);
setColor(parent, BLACK);
setColor(grandparent, RED);
ptr = grandparent;
} else {
if (ptr == parent->right) {
rotateLeft(parent);
ptr = parent;
parent = ptr->parent;
}
rotateRight(grandparent);
swap(parent->color, grandparent->color);
ptr = parent;
}
} else {
Node *uncle = grandparent->left;

if (getColor(uncle) == RED) {
setColor(uncle, BLACK);
setColor(parent, BLACK);
setColor(grandparent, RED);
ptr = grandparent;
} else {
 if (ptr == parent->left) {
rotateRight(parent);
ptr = parent;
parent = ptr->parent;
}
rotateLeft(grandparent);
swap(parent->color, grandparent->color);
ptr = parent;
}
}
}
setColor(root, BLACK);
}

void RBTree::inorderBST(Node *&ptr)

{ if (ptr == nullptr) return;

inorderBST(ptr->left);
cout << ptr->data << " " << ptr->color <<
endl; inorderBST(ptr->right);
}
void RBTree::inorder() {
inorderBST(root);
}
void RBTree::insertValue(int n)
{ Node *node = new Node(n);
root = insertBST(root, node);
fixInsertRBTree(node);
}

AVL Tree
#include "bits/stdc++.h"
using namespace std;

struct AVLNode {
int value;
AVLNode *leftChild,
*rightChild; int height;

AVLNode(int val) : value(val), leftChild(nullptr), rightChild(nullptr), height(1) {}

};
class AVLTree {
private:
AVLNode* rootNode;
int rotationCount;

int height(AVLNode* node) {

return node ? node->height : 0;
}
int balanceFactor(AVLNode* node) {
return node ? height(node->leftChild) - height(node->rightChild) : 0;
}

void updateHeight(AVLNode* node) {

node->height = 1 + max(height(node->leftChild), height(node->rightChild));
}

void leftRotate(AVLNode*& rootNode, AVLNode*& x) {

AVLNode* y = x->rightChild;
x->rightChild = y->leftChild;

if (y->leftChild) {
y->leftChild = x;
}
x = y;
rotationCount++;
}

void rightRotate(AVLNode*& rootNode, AVLNode*& x) {

AVLNode* y = x->leftChild;
x->leftChild = y->rightChild;

if (y->rightChild) {
y->rightChild = x;
}
x = y;
rotationCount++;
}

void fixBalance(AVLNode*& rootNode, AVLNode*& node) {

int balance = balanceFactor(node);

if (balance > 1) {

if (balanceFactor(node->leftChild) < 0) {
leftRotate(rootNode, node->leftChild);
}
rightRotate(rootNode, node);
} else if (balance < -1) {
if (balanceFactor(node->rightChild) > 0) {
 rightRotate(rootNode, node->rightChild);
}
leftRotate(rootNode, node);
}
}

void insertBST(AVLNode*& rootNode, AVLNode*& node) {

if (!rootNode) {
rootNode = node;
return;
}

if (node->value < rootNode->value) {

insertBST(rootNode->leftChild, node);
} else {
insertBST(rootNode->rightChild, node);
}

updateHeight(rootNode);
fixBalance(rootNode, rootNode);
}

public:
AVLTree() : rootNode(nullptr), rotationCount(0) {}

void insert(int value) {

AVLNode* node = new AVLNode(value);
insertBST(rootNode, node);
}

int getHeight() {
return height(rootNode);
}

int getRotationCount() {
return rotationCount;
}

AVLNode* getRoot()
{ return rootNode;
}
 AVLNode* getLeftChild() {
return rootNode ? rootNode->leftChild : nullptr;
}

AVLNode* getRightChild() {
return rootNode ? rootNode->rightChild : nullptr;
}
};