VISVESVARAYA TECHNOLOGICAL UNIVERSITY

“JnanaSangama”, Belgaum -590014, Karnataka.

LAB REPORT
on

ADVANCED DATA STRUCTURES (20CS5PEADS)

Submitted by

Kalle Venkata Sravan Dhira (1BM19CS068)

V SEM SEC B
ADSLAB BATCH- 3

Under the Guidance of

Namratha M
Assistant Professor,
Dept.of CSE,BMSCE

in partial fulfillment for the award of the degree of

BACHELOR OF ENGINEERING
in
COMPUTER SCIENCE AND ENGINEERING

B.M.S. COLLEGE OF ENGINEERING

(Autonomous Institution under VTU)
BENGALURU-560019
Oct-2021 to Jan-2022

1
LAB PROGRAM 1
Write a program to implement the following list: An ordinary Doubly Linked List
requires space for two address fields to store the addresses of previous and next nodes. A
memory efficient version of Doubly Linked List can be created using only one space for
the address field with every node. This memory efficient Doubly Linked List is called
XOR Linked List or Memory Efficient as the list uses bitwise XOR operation to save
space for one address. In the XOR linked list, instead of storing actual memory addresses,
every node stores the XOR of addresses of previous and next nodes.

SOURCE CODE
#include<iostream>
#include<vector>
#include<cstdint>
using namespace std;

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

Node* XOR(Node* x, Node* y) {

return (Node*)((uintptr_t)(x) ^ (uintptr_t)(y));
}

//Helper function to traverse the linkedlist

void traverse(Node* head)
{
Node* curr = head;
Node* prev = nullptr;
Node *next;

while (curr != nullptr)

{
cout <<curr->data<<"->";
2
next = XOR(prev, curr->link);
prev = curr;
 curr = next;
}
}

// Helper function to insert a node at the beginning of the XOR linked list
void push(Node* &headRef, int data)
{
Node* newNode = new Node();
newNode->data = data;
newNode->link = XOR(headRef, nullptr);
if (headRef)
{
headRef->link = XOR(newNode, XOR(headRef->link, nullptr));
}
headRef = newNode;
}

int main(){
vector<int> keys = { 1, 2, 3, 4, 5 };
Node* head = nullptr;
for (int i = keys.size() - 1; i >=0; i--)
{push(head, keys[i]);}
cout<<"Doubly XOR linked list"<<endl;
traverse(head);
return 0;
}

3
OUTPUT 1
OUTPUT 2

LAB PROGRAM 2
Write a program to perform insertion, deletion and searching operations on a skip list.
SOURCE CODE

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
Node **forward;
Node(int key,int lvl)
{
this->key = key;
forward = new Node*[lvl+1];
 memset(forward,0,sizeof(Node*)*(lvl+1));
}
};
class skiplist
{
int maxlvl;
float p;
int level;
Node *header;

public:
skiplist(int, float);
int randomLevel();
Node* createNode(int, int);
void insertElement(int);

5
void deleteElement(int);
void searchElement(int);
void displayList();
};

skiplist::skiplist(int maxlvl,float p)
{
this->maxlvl = maxlvl;
this->p = p;
level=0;
header = new Node(-1,maxlvl);
}

int skiplist::randomLevel()
{
float r = (float)rand()/RAND_MAX;
 int lvl = 0;
while(r < p && lvl < maxlvl)
{
lvl++;
r = (float)rand()/RAND_MAX;
}
return lvl;
};

Node* skiplist::createNode(int key, int level)

{
Node *n = new Node(key, level);
return n;
}

6
void skiplist::insertElement(int key)
{
Node* current = header;
Node* update[maxlvl+1];
memset(update, 0, sizeof(Node*)*(maxlvl+1));

for(int i = level; i >= 0; i--)

{

while (current->forward[i] != NULL &&

current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
cout<<update[i]<<endl;
}
current = current->forward[0];
 if (current == NULL || current->key != key)
{

int rlevel = randomLevel();

if (rlevel > level)

{
for (int i=level+1;i<rlevel+1;i++)
update[i] = header;
level = rlevel;
}

7
Node* n = createNode(key, rlevel);

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

{
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;

}
cout << " successfully inserted"<<n->key;
cout<<endl;
}

void skiplist::deleteElement(int key)

{
Node *current = header;
 Node *update[maxlvl+1];
memset(update, 0, sizeof(Node*)*(maxlvl+1));

for(int i=level; i>=0; i--)

{
while(current->forward[i] != NULL && current->forward[i]->key < key)
current = current->forward[i];

update[i] = current;
}

8
current = current->forward[0];

if(current != NULL and current->key == key)

{
for(int i=0;i<=level;i++)
{
if(update[i]->forward[i] != current)
break;

update[i]->forward[i] = current->forward[i];
}

while(level>0 &&header->forward[level] == 0)
level--;
cout<<"Successfully deleted key element "<<key<<"\n";
}
cout<<"Element not in the skiplist "<<key<<"\n";
};

void skiplist::searchElement(int key)

{
Node *current = header;

for(int i = level; i >= 0; i--)

{
while(current->forward[i] &&
current->forward[i]->key < key)
current = current->forward[i];

9
}
current = current->forward[0];

if(current and current->key == key)

cout<<"Found Element: "<<key<<"\n";
};

void skiplist::displayList()
{
cout<<"\n*****Skip List*****"<<"\n";
for(int i=0;i<=level;i++)
{
Node *node = header->forward[i];
cout<<"Level "<<i<<": ";
while(node != NULL)
{
cout<<node->key<<" ";
node = node->forward[i];
}
cout<<"\n";
}
};
/*
int main()
{
// Seed random number generator
srand((unsigned)time(0));

10
// create SkipList object with MAXLVL and P
skiplist lst(2, 0.5);

lst.insertElement(3);
lst.insertElement(6);
lst.insertElement(7);
lst.insertElement(9);
lst.displayList();
}
*/

//DRIVER CODE
int main()
{
srand((unsigned)time(0));
skiplist lst(3, 0.5);
int n;
int k;
cout<<"1:createlist 2:deletelistelement 3:searchlist 4:displaylist"<<endl;
cout<<"Enter your choice : ";

cin>>n;
while(1)
{
switch(n)
{
case 1:cout<<"Enter the key : ";
cin>>k;
lst.insertElement(k);
break;

11
case 2:cout<<"Enter the key : ";
cin>>k;
lst.deleteElement(k);
break;

case 3:cout<<"Enter the key : ";

cin>>k;
lst.searchElement(k);
break;

case 4: lst.displayList();

}
cout<<"1:createlist 2:deletelistelement 3:searchlist 4:displaylist"<<endl;
cout<<"Enter your choice : ";

cin>>n;

}
 12
OUTPUT 1

13
OUTPUT 2
14
PROGRAM 3
Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms
an island. For example, the below matrix contains 5 islands {1, 1, 0, 0, 0}, {0, 1, 0, 0, 1},
{1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1} A cell in the 2D matrix can be connected to 8
neighbours. Use disjoint sets to implement the above scenario

SOURCE CODE
#include <bits/stdc++.h>

using namespace std;

class Disjointsets
{

vector<int> rank, parent;

int n;

public:
Disjointsets(int n)
{
rank.resize(n);
parent.resize(n);
this->n = n;

makeSet();

void makeSet()
{

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

parent[i] = i;

15
int find(int x)
{
if (parent[x] != x)

{
parent[x]=find(parent[x]);
}

return parent[x];
}

void Union(int x, int y)

{

int xR = find(x);
int yR = find(y);

if (xR == yR)
return;

if (rank[xR] < rank[yR])

parent[xR] = yR;

else if (rank[yR] < rank[xR])

parent[yR] = xR;

16
else
{
parent[yR] = xR;
rank[xR] = rank[xR] + 1;
 }
}

};

int countIslands(vector<vector<int>>a)
{

int n = a.size();
int m = a[0].size();

Disjointsets *dus = new Disjointsets(n * m);

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

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

if (a[j][k] == 0)

continue;

if (j + 1 < n && a[j + 1][k] == 1)

dus->Union(j * (m) + k,
(j + 1) * (m) + k);

if (j - 1 >= 0 && a[j - 1][k] == 1)

17
dus->Union(j * (m) + k,
(j - 1) * (m) + k);
if (k + 1 < m && a[j][k + 1] == 1)
dus->Union(j * (m) + k,
(j) * (m) + k + 1);
 if (k - 1 >= 0 && a[j][k - 1] == 1)

dus->Union(j * (m) + k,
(j) * (m) + k - 1);
if (j + 1 < n && k + 1 < m &&
a[j + 1][k + 1] == 1)
dus->Union(j * (m) + k,

(j + 1) * (m) + k + 1);
if (j + 1 < n && k - 1 >= 0 &&
a[j + 1][k - 1] == 1)
dus->Union(j * m + k,
(j + 1) * (m) + k - 1);
if (j - 1 >= 0 && k + 1 < m &&
a[j - 1][k + 1] == 1)
dus->Union(j * m + k,
(j - 1) * m + k + 1);
if (j - 1 >= 0 && k - 1 >= 0 &&
a[j - 1][k - 1] == 1)

dus->Union(j * m + k,
(j - 1) * m + k - 1);
}

int *dup = new int[n * m];

18
int noIslands = 0;
for (int j = 0; j < n; j++)
{
for (int k = 0; k < m; k++)
{
 if (a[j][k] == 1)

{
int x = dus->find(j * m + k);

if (dup[x] == 0)

{
noIslands++;
dup[x]++;
}

else
dup[x]++;
}
}
}
return noIslands;

int main()
{
vector<vector<int>>a = {{1, 1, 0, 0, 0},

{0, 1, 0, 0, 1},

19
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}};
cout << "Number of Islands is: "
<< countIslands(a) << endl;
 return 0;
}

OUTPUT 1

OUTPUT 2

20
PROGRAM 4
Write a program to perform insertion and deletion operations on AVL
trees. SOURCE CODE
#include<bits/stdc++.h>
using namespace std;
class Node
{
public:
int key;

Node *left;
Node *right;
int height;
};

//Function to get maximum of two integers

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

//Function to find height of tree

int height(Node *N)
{
if (N == NULL)

return 0;
return N->height;
}

21
//Function to allocate new node
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
 node->right = NULL;

node->height = 1;
return(node);
}

//Right rotate operation

Node *rightRotate(Node *y)

{
Node *x = y->left;

Node *T2 = x->right;

x->right = y;
y->left = T2;

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

return x;

22
}

//Left rotate operation

Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
 y->left = x;
x->right = T2;

x->height = max(height(x->left),

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

return y;
}

// Balance factor

int getBalance(Node *N)

{
if (N == NULL)
return 0;
return height(N->left) -
height(N->right);

23
//INSERT OPERATION
Node* insert(Node* node, int key)
{

if (node == NULL)
return(newNode(key));

if (key < node->key)

 node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

else
return node;

/*updating height*/

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

int balance = getBalance(node);

// Left Left Case

if (balance > 1 && key < node->left->key)

return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);

// Left Right Case

24
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case

if (balance < -1 && key < node->right->key)
{
 node->right = rightRotate(node->right);

return leftRotate(node);

return node;

//To find inorder successor

Node * minValueNode(Node* node)
{
Node* current = node;

while (current->left != NULL)

current = current->left;

return current;
}

25
//RECURSIVE DELETION FUNCTION
Node* deleteNode(Node* root, int key)
{

if (root == NULL)
return root;

if ( key < root->key )

root->left = deleteNode(root->left, key);
else if( key > root->key )

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

else

{
// node with only one child or no child
if( (root->left == NULL) ||

(root->right == NULL) )
{
Node *temp = root->left ?

root->left :
root->right;

// No child case
if (temp == NULL)
{

temp = root;

26
root = NULL;
}
else // One child case
*root = *temp;
free(temp);
}
else
{
//find inorder successor for node with two child
Node* temp = minValueNode(root->right);
 root->key = temp->key;

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

}
}

// only one node

if (root == NULL)
return root;

// Update height
root->height = 1 + max(height(root->left),

height(root->right));

int balance = getBalance(root);

//IF NODE IS UNBALANCED
// Left Left Case
if (balance > 1 &&

getBalance(root->left) >= 0)

27
return rightRotate(root);

// Left Right Case

if (balance > 1 &&
getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
 // Right Right Case

if (balance < -1 &&

getBalance(root->right) <= 0)

return leftRotate(root);

// Right Left Case

if (balance < -1 &&

getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

Node* search(Node* root, int key)

{

28
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);

return search(root->left, key);

}

//preorder traversal
void preOrder(Node *root)
{

if(root != NULL)
{

cout << root->key << " ";

preOrder(root->left);
preOrder(root->right);

}
}

//INTERACTIVE DRIVER CODE

int main()

{
int n;
int k;
Node* root = NULL;
Node* temp = NULL;
cout<<"1:createtree 2:deletetree 3:searchtree
4:displaytree"<<endl; cout<<"Enter your choice : ";

29
cin>>n;
while(1)
{

switch(n)
{
case 1:cout<<"Enter the key : ";
cin>>k;
root=insert(root,k);
break;
 case 2:cout<<"Enter the key :: ";

cin>>k;
root = deleteNode(root, k);

break;

case 3:cout<<"Enter the key :: ";

cin>>k;
temp =search(root,k);
if(temp==NULL)
{
cout<<"\nElement not found in the tree\n";

}
else
{
cout<<"\nElement is found in the tree \n";
search(root,k);
break;

30
case 4: cout<<"\nPreorder traversal of the the tree:";
preOrder(root);
cout<<endl;
break;

}
cout<<"Enter your choice : ";
cin>>n;
}
}

31
OUTPUT 1
 OUTPUT 2

32
PROGRAM 5
Write a program to perform insertion and deletion operations on 2-3 trees.
SOURCE CODE
#include <bits/stdc++.h>
using namespace std;

class TreeNode
{
int *keys;

TreeNode **child;
int n;

bool leaf;

public:
TreeNode(bool leaf);
void traverse();
int findKey(int k);
void insertNonFull(int k);
void splitChild(int i, TreeNode *y);
void remove(int k);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);

int getPred(int idx);

int getSucc(int idx);
void fill(int idx);

void borrowFromNext(int idx);

void borrowFromPrev(int idx);
void merge(int idx);
friend class Tree;

};

33
class Tree
{
TreeNode *root = NULL;
public:
 /*Tree(){

root = NULL;
}*/
void traverse()
{
if(root != NULL)

root->traverse();
}
void insert(int k);
void remove(int k);
};

TreeNode::TreeNode(bool leaf1)
{
leaf = leaf1;
keys = new int[3];
child = new TreeNode *[4];

n = 0;
}

int TreeNode::findKey(int k)
{
int idx = 0;

while(idx<n && keys[idx]<k)

34
++idx;
return idx;
}

void Tree::insert(int k)
{

if(root == NULL)
{
root = new TreeNode(true);
root->keys[0] = k;
root->n = 1;

}
else{
if(root->n == 3)
{
TreeNode *s = new TreeNode(false);
s->child[0] = root;
s->splitChild(0, root);
int i = 0;
if(s->keys[0]<k)
i++;
s->child[i]->insertNonFull(k);

root = s;
}
else

root->insertNonFull(k);
}
}

35
void TreeNode::insertNonFull(int k)
{
int i = n-1;
if(leaf == true)
{
 while(i>=0 && keys[i] > k)

{
keys[i+1] = keys[i];
i--;
}
keys[i+1] = k;

n = n + 1;
}
else{
while(i>=0 && keys[i]>k)
i--;
if(child[i+1]->n == 3)
{
splitChild(i+1, child[i+1]);
if(keys[i+1]<k)
i++;
}

child[i+1]->insertNonFull(k);
}
}

void TreeNode::splitChild(int i, TreeNode *y)

{

TreeNode *z = new TreeNode(y->leaf);

36
z->n = 1;
z->keys[0] = y->keys[2];
if(y->leaf == false)
{
for(int j=0; j<2; j++)
 z->child[j] = y->child[j+2];

}
y->n = 1;
for(int j=n; j>=i+1; j--)
child[j+1] = child[j];
child[i+1] = z;

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

keys[j+1] = keys[j];

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

n = n + 1;
}

void TreeNode::traverse()
{
cout<<endl;

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

if(leaf == false)
child[i]->traverse();
cout<<" "<<keys[i];

37
if(leaf == false)
child[i]->traverse();

cout<<endl;
}
void TreeNode::remove(int k)
{
int idx = findKey(k);
if(idx<n && keys[idx] == k)
{

if(leaf)
removeFromLeaf(idx);
else

removeFromNonLeaf(idx);
}
else
{
if(leaf)
{
cout<<"The key doesn't exist"<<endl;
return;

}
bool flag = ((idx==n)?true : false);
if(child[idx]->n < 2)

fill(idx);
if(flag && idx>n)
child[idx-1]->remove(k);

else

38
child[idx]->remove(k);
}
return;
}
void TreeNode::removeFromLeaf(int idx)
{
for(int i=idx+1; i<n; ++i)
keys[i-1] = keys[i];
n--;

return;

void TreeNode::removeFromNonLeaf(int idx)

{
int k = keys[idx];
if(child[idx]->n >=2)
{
int pred = getPred(idx);
keys[idx] = pred;
child[idx]->remove(pred);
}

else if(child[idx+1]->n >= 2)

{

int succ = getSucc(idx);

keys[idx] = succ;
child[idx+1]->remove(succ);
}

else{

39
merge(idx);
child[idx]->remove(k);
}
return;
}

int TreeNode::getPred(int idx)

{
TreeNode *curr = child[idx];
while(!curr->leaf)

curr = curr->child[curr->n];

return curr->keys[curr->n-1];
}

int TreeNode::getSucc(int idx)

{
TreeNode *curr = child[idx+1];
while (!curr->leaf)
curr = curr->child[0];
return curr->keys[0];
}

void TreeNode::fill(int idx)

{

if(idx!=0 && child[idx-1]->n>=2)

borrowFromPrev(idx);

else if (idx!=n && child[idx+1]->n>=2)

borrowFromNext(idx);

40
else
{
if (idx != n)
merge(idx);
 else

merge(idx-1);
}
return;
}

void TreeNode::borrowFromPrev(int idx)

TreeNode *c=child[idx];
TreeNode *sibling=child[idx-1];

for (int i=c->n-1; i>=0; --i)

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

if (!c->leaf)
{
for(int i=c->n; i>=0; --i)

c->child[i+1] = c->child[i];
}

c->keys[0] = keys[idx-1];

if(!c->leaf)
c->child[0] = sibling->child[sibling->n];

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

c->n += 1;
sibling->n -= 1;
 return;
}

void TreeNode::borrowFromNext(int idx)

{

TreeNode *c=child[idx];

TreeNode *sibling=child[idx+1];

c->keys[(c->n)] = keys[idx];

if (!(c->leaf))
c->child[(c->n)+1] = sibling->child[0];

keys[idx] = sibling->keys[0];

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

sibling->keys[i-1] = sibling->keys[i];

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

42
c->n += 1;
sibling->n -= 1;

return;
}
void TreeNode::merge(int idx)
{
TreeNode *c = child[idx];
TreeNode *sibling = child[idx+1];

c->keys[1] = keys[idx];

for (int i=0; i<sibling->n; ++i)

c->keys[i+2] = sibling->keys[i];

if (!c->leaf)
{
for(int i=0; i<=sibling->n; ++i)
c->child[i+2] = sibling->child[i];
}

for (int i=idx+1; i<n; ++i)

keys[i-1] = keys[i];

for (int i=idx+2; i<=n; ++i)

child[i-1] = child[i];

43
c->n += sibling->n+1;
n--;

delete(sibling);
return;
}
void Tree::remove(int k)
{
if (!root)
{

cout << "The tree is empty\n";

return;
}

root->remove(k);

if (root->n==0)
{
TreeNode *tmp = root;
if (root->leaf)
root = NULL;

else
root = root->child[0];

delete tmp;
}
return;

44
int main()
{
Tree t;
int n,k;
cout<<"Enter the no. of elements"<<endl;
cin>>n;
 cout<<"Enter the keys"<<endl;
for(int i=0; i<n; i++)

cin>>k;
t.insert(k);
}
cout << "Traversal of tree constructed is\n";
t.traverse();
cout<<"Enter the key to be deleted"<<endl;
cin>>k;
t.remove(k);
cout<<"Traversal after deletion is"<<endl;
t.traverse();

return 0;

45
OUTPUT 1
OUTPUT 2

46
PROGRAM 6
Write a program to implement insertion operation on a red black tree. During insertion,
appropriately show how recolouring or rotation operation is used.
SOURCE CODE
#include <bits/stdc++.h>
using namespace std;

enum Color {RED, BLACK};

struct Node
{
int data;

bool color;
Node *left, *right, *parent;

Node(int data)
{
this->data = data;
left = right = parent = NULL;
this->color = RED;
}

};

class RBTree
{
private:

Node *root;

47
protected:
void rotateLeft(Node *&, Node *&);
void rotateRight(Node *&, Node *&);
 void fixViolation(Node *&, Node *&);
public:

RBTree() { root = NULL; }

void insert(const int &n);
void inorder();
void levelOrder();
};

void inorderHelper(Node *root)

{
if (root == NULL)
return;

inorderHelper(root->left);
cout << root->data << " ";
inorderHelper(root->right);
}

Node* BSTInsert(Node* root, Node *pt)

{

if (root == NULL)

return pt;

48
if (pt->data < root->data)
{
root->left = BSTInsert(root->left, pt);
root->left->parent = root;
 }
else if (pt->data > root->data)

{
root->right = BSTInsert(root->right, pt);
root->right->parent = root;

return root;
}

void levelOrderHelper(Node *root)

{
if (root == NULL)
return;

std::queue<Node *> q;
q.push(root);

while (!q.empty())
{

Node *temp = q.front();

49
cout << temp->data << " ";
q.pop();

if (temp->left != NULL)
q.push(temp->left);

if (temp->right != NULL)
 q.push(temp->right);
}

void RBTree::rotateLeft(Node *&root, Node *&pt)

{
Node *pt_right = pt->right;

pt->right = pt_right->left;

if (pt->right != NULL)
pt->right->parent = pt;

pt_right->parent = pt->parent;

if (pt->parent == NULL)
root = pt_right;

else if (pt == pt->parent->left)

pt->parent->left = pt_right;

else

50
pt->parent->right = pt_right;

pt_right->left = pt;
pt->parent = pt_right;
}

void RBTree::rotateRight(Node *&root, Node *&pt)

{
 Node *pt_left = pt->left;

pt->left = pt_left->right;

if (pt->left != NULL)
pt->left->parent = pt;

pt_left->parent = pt->parent;

if (pt->parent == NULL)
root = pt_left;

else if (pt == pt->parent->left)

pt->parent->left = pt_left;

else
pt->parent->right = pt_left;

pt_left->right = pt;
pt->parent = pt_left;

51
void RBTree::fixViolation(Node *&root, Node *&pt)
{
Node *parent_pt = NULL;
Node *grand_parent_pt = NULL;

while ((pt != root) && (pt->color != BLACK) &&

(pt->parent->color == RED))
{
parent_pt = pt->parent;

grand_parent_pt = pt->parent->parent;

if (parent_pt == grand_parent_pt->left)
{

Node *uncle_pt = grand_parent_pt->right;

if (uncle_pt != NULL && uncle_pt->color ==

RED)
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;

52
else
{

if (pt == parent_pt->right)
{
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
 rotateRight(root, grand_parent_pt);

swap(parent_pt->color,
grand_parent_pt->color);
pt = parent_pt;
}
}

else
{

Node *uncle_pt = grand_parent_pt->left;

if ((uncle_pt != NULL) && (uncle_pt->color ==

RED))
{
grand_parent_pt->color = RED;

parent_pt->color = BLACK;

53
uncle_pt->color = BLACK;
pt = grand_parent_pt;
}
else
{

if (pt == parent_pt->left)
{
rotateRight(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
 }

rotateLeft(root, grand_parent_pt);
swap(parent_pt->color,
grand_parent_pt->color);
pt = parent_pt;
}
}
}

root->color = BLACK;
}

void RBTree::insert(const int &data)

{

Node *pt = new Node(data);

54
// Do a normal BST insert
root = BSTInsert(root, pt);

// fix Red Black Tree violations

fixViolation(root, pt);
}

void RBTree::inorder() { inorderHelper(root);}

void RBTree::levelOrder() { levelOrderHelper(root); }
int main()
{
RBTree tree;
int n,num;
cout<<"Enter no of elements"<<endl;
cin>>n;
cout<<"Enter elements"<<endl;
for(int i=0;i<n;i++)
{

cin>>num;
tree.insert(num);
}

cout << "Inoder Traversal of Created Tree\n";

tree.inorder();

55
cout << "\n\nLevel Order Traversal of Created Tree\n";
tree.levelOrder();
cout<<endl;

return 0;
}

OUTPUT 1
OUTPUT 2

56
PROGRAM 7
Write a program to implement insertion operation on a B-tree.
SOURCE CODE
#include<iostream>
using namespace std;

class BTreeNode
{
int *keys;
int t;
 BTreeNode **C;
int n;

bool leaf;

public:
BTreeNode(int _t, bool _leaf);
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void traverse();
friend class BTree;
};

class BTree
{
BTreeNode *root;
int t;
public:

BTree(int _t)

{ root = NULL; t = _t; }

57
void traverse()
{ if (root != NULL) root->traverse(); }
void insert(int k);
};

BTreeNode::BTreeNode(int t1, bool leaf1)

{

t = t1;

leaf = leaf1;
keys = new int[2*t-1];
 C = new BTreeNode *[2*t];
n = 0;

void BTreeNode::traverse()
{

int i;

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

{

if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];

58
if (leaf == false)
C[i]->traverse();
}

void BTree::insert(int k)
{

if (root == NULL)
{

root = new BTreeNode(t, true);

root->keys[0] = k;
root->n = 1;
}
else
 {

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

BTreeNode *s = new BTreeNode(t, false);

s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;

s->C[i]->insertNonFull(k);

59
root = s;
}
else
root->insertNonFull(k);
}
}

void BTreeNode::insertNonFull(int k)
{

int i = n-1;

if (leaf == true)
{

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

{
keys[i+1] = keys[i];
 i--;
}

keys[i+1] = k;
n = n+1;
}
else
{

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

60
i--;

if (C[i+1]->n == 2*t-1)
{

splitChild(i+1, C[i+1]);
if (keys[i+1] < k)
i++;
}
C[i+1]->insertNonFull(k);

}
}

void BTreeNode::splitChild(int i, BTreeNode *y)

{

BTreeNode *z = new BTreeNode(y->t, y->leaf);

z->n = t - 1;
 for (int j = 0; j < t-1; j++)
z->keys[j] = y->keys[j+t];

if (y->leaf == false)
{
for (int j = 0; j < t; j++)
z->C[j] = y->C[j+t];
}

y->n = t - 1;

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

C[i+1] = z;

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

keys[j+1] = keys[j];

keys[i] = y->keys[t-1];
n = n + 1;
}

int main()
{
int degree,n,num;
cout<<"Enter degree"<<endl;
cin>>degree;
BTree t(degree);
cout<<"Enter no of elements"<<endl;
 cin>>n;
cout<<"Enter elements"<<endl;

for(int i=0;i<n;i++)
{
cin>>num;
t.insert(num);
}

62
cout << "Traversal of the constucted tree is ";
t.traverse();

return 0;
}

OUTPUT 1

63

OUTPUT 2
 64

PROGRAM 8
Write a program to implement functions of Dictionaries using Hashing.
SOURCE CODE
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int T_S = 200;
class HashTableEntry {

public:
int k;

int v;
HashTableEntry(int k, int v) {
this->k= k;
this->v = v;
}
};
class HashMapTable {
private:

HashTableEntry **t;
public:
HashMapTable() {
 t = new HashTableEntry * [T_S];
for (int i = 0; i< T_S; i++) {

t[i] = NULL;
}

65
int HashFunc(int k) {
return k % T_S;
}

void Insert(int k, int v) {

int h = HashFunc(k);
while (t[h] != NULL && t[h]->k != k) {
h = HashFunc(h + 1);
}
if (t[h] != NULL)
delete t[h];
t[h] = new HashTableEntry(k, v);

}
int SearchKey(int k) {
int h = HashFunc(k);

while (t[h] != NULL && t[h]->k != k) {

h = HashFunc(h + 1);
}
if (t[h] == NULL)
return -1;
else
return t[h]->v;
}

void Remove(int k) {
int h = HashFunc(k);
while (t[h] != NULL) {
 if (t[h]->k == k)
break;
h = HashFunc(h + 1);

66
if (t[h] == NULL) {
cout<<"No Element found at key "<<k<<endl;
return;
} else {
delete t[h];
}
cout<<"Element Deleted"<<endl;
}
~HashMapTable() {
for (int i = 0; i < T_S; i++) {
if (t[i] != NULL)

delete t[i];
delete[] t;
}
}

};
int main() {
HashMapTable hash;
int k, v;
int c;
while (1) {
cout<<"1.Insert element into the table"<<endl;

cout<<"2.Search element from the key"<<endl;

cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {

case 1:

67
cout<<"Enter element to be inserted: ";
cin>>v;
cout<<"Enter key at which element to be inserted: ";
cin>>k;
hash.Insert(k, v);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>k;
if (hash.SearchKey(k) == -1) {
cout<<"No element found at key "<<k<<endl;

continue;
} else {
cout<<"Element at key "<<k<<" : ";
cout<<hash.SearchKey(k)<<endl;

}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>k;
hash.Remove(k);
break;

case 4:
exit(1);
default:
 cout<<"\nEnter correct option\n";
}
}

return 0;

68
}

OUTPUT 1
69
OUTPUT 2
 70
PROGRAM 9
Write a program to implement the following functions on a Binomial heap:
1. insert(H, k): Inserts a key ‘k’ to Binomial Heap ‘H’. This operation first creates a
Binomial Heap with a single key ‘k’, then calls union on H and the new Binomial heap.
2. getMin(H): A simple way to getMin() is to traverse the list of root of Binomial Trees
and return the minimum key.
3. extractMin(H): This operation also uses union(). We first call getMin() to find the
minimum key Binomial Tree, then we remove the node and create a new Binomial Heap
by connecting all subtrees of the removed minimum node. Finally we call union() on H
and the newly created Binomial Heap.

SOURCE CODE
#include<bits/stdc++.h>

using namespace std;

// A Binomial Tree node.

struct Node
{
int data, degree;
Node *child, *sibling, *parent;
};
Node* newNode(int key)

{
Node *temp = new Node;
temp->data = key;
temp->degree = 0;
temp->child = temp->parent = temp->sibling = NULL;
return temp;
}

71
// This function merge two Binomial Trees.
Node* mergeBinomialTrees(Node *b1, Node *b2)
{
// Make sure b1 is smaller
if (b1->data > b2->data)
swap(b1, b2);

// We basically make larger valued tree

// a child of smaller valued tree
b2->parent = b1;
b2->sibling = b1->child;

b1->child = b2;
b1->degree++;

return b1;
}

// This function perform union operation on two

// binomial heap i.e. l1 & l2
list<Node*> unionBionomialHeap(list<Node*> l1,
 list<Node*> l2)
{

// _new to another binomial heap which contain

// new heap after merging l1 & l2
list<Node*> _new;
list<Node*>::iterator it = l1.begin();
list<Node*>::iterator ot = l2.begin();
while (it!=l1.end() && ot!=l2.end())

72
// if D(l1) <= D(l2)
if((*it)->degree <= (*ot)->degree)
{
_new.push_back(*it);
it++;
}
// if D(l1) > D(l2)
else
{
_new.push_back(*ot);
ot++;

}
}

// if there remains some elements in l1

// binomial heap
while (it != l1.end())
{
_new.push_back(*it);
it++;
 }

// if there remains some elements in l2

// binomial heap
while (ot!=l2.end())
{
_new.push_back(*ot);
ot++;

73
return _new;
}

// adjust function rearranges the heap so that

// heap is in increasing order of degree and
// no two binomial trees have same degree in this heap
list<Node*> adjust(list<Node*> _heap)
{
if (_heap.size() <= 1)
return _heap;
list<Node*> new_heap;

list<Node*>::iterator it1,it2,it3;
it1 = it2 = it3 = _heap.begin();

if (_heap.size() == 2)
{
it2 = it1;
it2++;
it3 = _heap.end();
}
else
{

it2++;
it3=it2;
it3++;
}
while (it1 != _heap.end())
{

// if only one element remains to be processed

74
if (it2 == _heap.end())
it1++;

// If D(it1) < D(it2) i.e. merging of Binomial

// Tree pointed by it1 & it2 is not possible
// then move next in heap
else if ((*it1)->degree < (*it2)->degree)
{
it1++;
it2++;
if(it3!=_heap.end())

it3++;
}

// if D(it1),D(it2) & D(it3) are same i.e.

// degree of three consecutive Binomial Tree are same
// in heap
else if (it3!=_heap.end() &&
(*it1)->degree == (*it2)->degree &&
(*it1)->degree == (*it3)->degree)
 {
it1++;

it2++;
it3++;
}

// if degree of two Binomial Tree are same in heap

else if ((*it1)->degree == (*it2)->degree)

75
Node *temp;
*it1 = mergeBinomialTrees(*it1,*it2);
it2 = _heap.erase(it2);
if(it3 != _heap.end())
it3++;
}
}
return _heap;
}

// inserting a Binomial Tree into binomial heap

list<Node*> insertATreeInHeap(list<Node*> _heap,

Node *tree)
{
// creating a new heap i.e temp
list<Node*> temp;

// inserting Binomial Tree into heap

temp.push_back(tree);
 // perform union operation to finally insert
// Binomial Tree in original heap

temp = unionBionomialHeap(_heap,temp);

return adjust(temp);
}

// removing minimum key element from binomial heap

// this function take Binomial Tree as input and return

76
// binomial heap after
// removing head of that tree i.e. minimum element
list<Node*> removeMinFromTreeReturnBHeap(Node *tree)
{
list<Node*> heap;
Node *temp = tree->child;
Node *lo;

// making a binomial heap from Binomial Tree

while (temp)
{

lo = temp;
temp = temp->sibling;
lo->sibling = NULL;
heap.push_front(lo);
}
return heap;
}
// inserting a key into the binomial heap
list<Node*> insert(list<Node*> _head, int key)
{

Node *temp = newNode(key);

return insertATreeInHeap(_head,temp);
}

// return pointer of minimum value Node

// present in the binomial heap

Node* getMin(list<Node*> _heap)

77
{
list<Node*>::iterator it = _heap.begin();
Node *temp = *it;
while (it != _heap.end())
{
if ((*it)->data < temp->data)
temp = *it;
it++;
}
return temp;
}

list<Node*> extractMin(list<Node*> _heap)

{
list<Node*> new_heap,lo;
Node *temp;

// temp contains the pointer of minimum value

 // element in heap
temp = getMin(_heap);

list<Node*>::iterator it;

it = _heap.begin();

while (it != _heap.end())

{
if (*it != temp)
{
// inserting all Binomial Tree into new
// binomial heap except the Binomial Tree

// contains minimum element

78
new_heap.push_back(*it);
}
it++;
}
lo = removeMinFromTreeReturnBHeap(temp);
new_heap = unionBionomialHeap(new_heap,lo);
new_heap = adjust(new_heap);
return new_heap;
}

// print function for Binomial Tree

void printTree(Node *h)

{
while (h)
{
cout << h->data << " ";
printTree(h->child);
h = h->sibling;
 }
}

// print function for binomial heap

void printHeap(list<Node*> _heap)

{
list<Node*> ::iterator it;
it = _heap.begin();
while (it != _heap.end())
{

printTree(*it);

79
it++;
}
}

// Driver program to test above functions

int main()
{
int ch,key;
list<Node*> _heap;

// Insert data in the heap

int i,n,in;
cout<<"No of items"<<endl;
cin>>n;
cout<<"enter item"<<endl;
for(i=0;i<n;i++)
{
 cin>>in;
_heap = insert(_heap,in);

cout << "Heap elements after insertion:\n";

printHeap(_heap);

Node *temp = getMin(_heap);

cout << "\nMinimum element of heap "
<< temp->data << "\n";

80
OUTPUT 1

OUTPUT 2
PROGRAM 10
Write a program to implement the following functions on a Binomial heap:
1. delete(H): Like Binary Heap, delete operation first reduces the key to minus
infinite,
then calls extractMin().
2. decreaseKey(H): decreaseKey() is also similar to Binary Heap. We compare the
decreased key with its parent and if the parent's key is more, we swap keys and recur
for
the parent. We stop when we either reach a node whose parent has a smaller key or
we hit
the root node.

#include <bits/stdc++.h>
using namespace std;

struct Node
{
int val, degree;
Node *parent, *child, *sibling;
};

Node *root = NULL;

int binomialLink(Node *h1, Node *h2)

{
h1->parent = h2;
h1->sibling = h2->child;
h2->child = h1;
h2->degree = h2->degree + 1;
}

Node *createNode(int n)
{
Node *new_node = new Node;
new_node->val = n;
new_node->parent = NULL;
new_node->sibling = NULL;
new_node->child = NULL;
new_node->degree = 0;
return new_node;
}

Node *mergeBHeaps(Node *h1, Node *h2)

{
 if (h1 == NULL)
return h2;
if (h2 == NULL)
return h1;

Node *res = NULL;

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

res = h1;

else if (h1->degree > h2->degree)

res = h2;

while (h1 != NULL && h2 != NULL)

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

else if (h1->degree == h2->degree)

{
Node *sib = h1->sibling;
h1->sibling = h2;
h1 = sib;
}

else
{
Node *sib = h2->sibling;
h2->sibling = h1;
h2 = sib;
}
}
return res;
}

Node *unionBHeaps(Node *h1, Node *h2)

{
if (h1 == NULL && h2 == NULL)
return NULL;

Node *res = mergeBHeaps(h1, h2);

Node *prev = NULL, *curr = res,

*next = curr->sibling;
while (next != NULL)
 {
if ((curr->degree != next->degree) ||
((next->sibling != NULL) &&
(next->sibling)->degree ==
curr->degree))
{
prev = curr;
curr = next;
}

else
{
if (curr->val <= next->val)
{
curr->sibling = next->sibling;
binomialLink(next, curr);
}
else
{
if (prev == NULL)
res = next;
else
prev->sibling = next;
binomialLink(curr, next);
curr = next;
}
}
next = curr->sibling;
}
return res;
}

void binomialHeapInsert(int x)
{
root = unionBHeaps(root, createNode(x));
}

void display(Node *h)

{
while (h)
{
cout << h->val << " ";
display(h->child);
h = h->sibling;
}
}

int revertList(Node *h)

{
if (h->sibling != NULL)
{
revertList(h->sibling);
(h->sibling)->sibling = h;
}
else
root = h;
}

Node *extractMinBHeap(Node *h)

{
if (h == NULL)
return NULL;

Node *min_node_prev = NULL;

Node *min_node = h;

int min = h->val;

Node *curr = h;
while (curr->sibling != NULL)
{
if ((curr->sibling)->val < min)
{
min = (curr->sibling)->val;
min_node_prev = curr;
min_node = curr->sibling;
}
curr = curr->sibling;
}

if (min_node_prev == NULL &&

min_node->sibling == NULL)
h = NULL;

else if (min_node_prev == NULL)

h = min_node->sibling;

else
min_node_prev->sibling = min_node->sibling;

if (min_node->child != NULL)
 {
revertList(min_node->child);
(min_node->child)->sibling = NULL;
}

return unionBHeaps(h, root);

}

Node *findNode(Node *h, int val)

{
if (h == NULL)
return NULL;

if (h->val == val)
return h;

Node *res = findNode(h->child, val);

if (res != NULL)
return res;

return findNode(h->sibling, val);

}

void decreaseKeyBHeap(Node *H, int old_val,

int new_val)
{
Node *node = findNode(H, old_val);

if (node == NULL)
return;

node->val = new_val;
Node *parent = node->parent;

while (parent != NULL && node->val < parent->val)

{
swap(node->val, parent->val);
node = parent;
parent = parent->parent;
}
}

Node *binomialHeapDelete(Node *h, int val)

{
 if (h == NULL)
return NULL;

decreaseKeyBHeap(h, val, INT_MIN);

return extractMinBHeap(h);
}

int main()
{
int n, temp, del;
cout << "Enter no of elements in the heap" << endl;
cin >> n;
cout << "Enter elements" << endl;
for (int i = 0; i < n; i++)
{
cin >> temp;
binomialHeapInsert(temp);
}

cout << "The heap is:\n";

display(root);
cout << endl;

cout << "Enter element to be deleted" << endl;

cin >> del;

root = binomialHeapDelete(root, del);

cout << "After deletion, the heap is:\n";

display(root);
cout << endl;

return 0;
}
OUTPUT 1

OUTPUT 2