Use Ctrl+F to search and refer geeksforgeeks for more info
Linked Lists:
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.Each node in a list consists of at least two parts: 1) data 2) pointer to the next node.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
void printList(struct node *n)
{
while (n != NULL)
{
printf(" %d ", n->data);
n = n->next;
}
}
int main()
{
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
head = (struct node*)malloc(sizeof(struct node));
second = (struct node*)malloc(sizeof(struct node));
third = (struct node*)malloc(sizeof(struct node));
head->data = 1; //assign data in first node
head->next = second; // Link first node with the second node
second->data = 2; //assign data to second node
second->next = third;
third->data = 3; //assign data to third node
third->next = NULL;
printList(head);//traversal
getchar();
return 0;
}
Inserting a node in Linked List:
add node at the front.
void push(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
after a given node:
void insertAfter(struct node* prev_node, int new_data)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct node* new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. move the next of prev_node as new_node */
prev_node->next = new_node;
}
at the end:
void append(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
struct node *last = *head_ref; /* used in 2*/
new_node->data = new_data;
new_node->next = NULL;
/* 1. If the Linked List is empty, then make the new node as head */
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
/* 2. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 3. Change the next of last node */
last->next = new_node;
return;
}
Deleting a node from linked list:
To delete a node from linked list, we need to do following steps.
1) Find previous node of the node to be deleted.
2) Changed next of previous node.
3) Free memory for the node to be deleted.
void deleteNode(struct node **head_ref, int key)
{
struct node* temp = *head_ref, *prev;
if (temp != NULL && temp->data == key)
{
*head_ref = temp->next; // Changed head
free(temp); // free old head
return;
}
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp); // Free memory
}
Circular linked list
Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.
Function to insert a node at the begining of a Circular linked list
void push(struct node **head_ref, int data)
{
struct node *ptr1 = (struct node *)malloc(sizeof(struct node));
struct node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then set the next of last node */
if (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
Function to print nodes in a given Circular linked list
void printList(struct node *head)
{
struct node *temp = head;
if (head != NULL)
{
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
}
}
Sorted insert for circular linked list
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data < new_node->data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;
Doubly Linked List
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
struct node
{
int data;
struct node *next; // Pointer to next node in DLL
struct node *prev; // Pointer to previous node in DLL
};
Inserting a node:
1) Add a node at the front:
void push(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
(*head_ref) = new_node;
}
2) Add a node after a given node.:
void insertAfter(struct node* prev_node, int new_data)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct node* new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
new_node->prev = prev_node;
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
3) Add a node at the end:
void append(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
struct node *last = *head_ref; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL)
{
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
Delete a node in a Doubly Linked List:
void deleteNode(struct node **head_ref, struct node *del)
{
if(*head_ref == NULL || del == NULL)
return;
if(*head_ref == del)
*head_ref = del->next;
if(del->next != NULL)
del->next->prev = del->prev;
if(del->prev != NULL)
del->prev->next = del->next;
free(del);
return;
}
Traverse a list is similar to singly linked list
Stack:
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Push: Adds an item in the stack.
Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed.
Peek: Get the topmost item.
Stack Using Arrays:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Stack
{
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
return stack;
}
int isFull(struct Stack* stack)
{ return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack)
{ return stack->top == -1; }
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
int main()
{
struct Stack* stack = createStack(100);
push(stack, 10);
push(stack, 20);
push(stack, 30);
printf("%d popped from stack\n", pop(stack));
printf("Top item is %d\n", peek(stack));
return 0;
}
Stack Using Linked List:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct StackNode
{
int data;
struct StackNode* next;
};
struct StackNode* newNode(int data)
{
struct StackNode* stackNode =
(struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
int isEmpty(struct StackNode *root)
{
return !root;
}
void push(struct StackNode** root, int data)
{
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d pushed to stack\n", data);
}
int pop(struct StackNode** root)
{
if (isEmpty(*root))
return INT_MIN;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct StackNode* root)
{
if (isEmpty(root))
return INT_MIN;
return root->data;
}
int main()
{
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack\n", pop(&root));
printf("Top element is %d\n", peek(root));
return 0;
}
Queue:
Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO)
Enqueue: Adds an item to the queue.
Dequeue: Removes an item from the queue.
Front: Get the front item from queue.
Rear: Get the last item from queue.
Array implementation Of Queue
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Queue
{
int front, rear, size;
unsigned capacity;
int* array;
};
struct Queue* createQueue(unsigned capacity)
{
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1; // This is important, see the enqueue
queue->array = (int*) malloc(queue->capacity * sizeof(int));
return queue;
}
int isFull(struct Queue* queue)
{ return (queue->size == queue->capacity); }
int isEmpty(struct Queue* queue)
{ return (queue->size == 0); }
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)%queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf("%d enqueued to queue\n", item);
}
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)%queue->capacity;
queue->size = queue->size - 1;
return item;
}
int front(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
int rear(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
int main()
{
struct Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
printf("%d dequeued from queue\n", dequeue(queue));
printf("Front item is %d\n", front(queue));
printf("Rear item is %d\n", rear(queue));
return 0;
}
linked list based implementation of queue
#include <stdlib.h>
#include <stdio.h>
struct QNode
{
int key;
struct QNode *next;
};
struct Queue
{
struct QNode *front, *rear;
};
struct QNode* newNode(int k)
{
struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
temp->key = k;
temp->next = NULL;
return temp;
}
struct Queue *createQueue()
{
struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
void enQueue(struct Queue *q, int k)
{
struct QNode *temp = newNode(k);
if (q->rear == NULL)
{
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
struct QNode *deQueue(struct Queue *q)
{.
if (q->front == NULL)
return NULL;
struct QNode *temp = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
return temp;
}
int main()
{
struct Queue *q = createQueue();
enQueue(q, 10);
enQueue(q, 20);
deQueue(q);
deQueue(q);
enQueue(q, 30);
enQueue(q, 40);
enQueue(q, 50);
struct QNode *n = deQueue(q);
if (n != NULL)
printf("Dequeued item is %d", n->key);
return 0;
}
Binary Tree:
Trees:Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical data structures. The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent.Finally, elements with no children are called leaves.
Binary Tree: A tree whose elements have at most 2 children is called a binary tree.We typically name them the left and right child. A Tree node contains following parts.1. Data 2. Pointer to left child 3. Pointer to right child
#include<stdio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 NULL NULL NULL
/ \
NULL NULL
*/
getchar();
return 0;
}
Full Binary Tree A Binary Tree is full if every node has 0 or 2 children.
Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible
Inorder Traversal:
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Preorder Traversal:
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Postorder Traversal:
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
Example:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void printPostorder(struct node* node)
{
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
printf("%d ", node->data);
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
void printPreorder(struct node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("\n Preorder traversal of binary tree is \n");
printPreorder(root);
printf("\n Inorder traversal of binary tree is \n");
printInorder(root);
printf("\n Postorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
Binary Search Tree:
Binary Search Tree, is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
Example:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct 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);
return node;
}
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
inorder(root);
return 0;
}
Searching a key:
struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
Delete a node:
1) Node to be deleted is leaf: Simply remove from the tree.
2) Node to be deleted has only one child: Copy the child to the node and delete the child
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
struct node* deleteNode(struct 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)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two children: Get the inorder successor
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
Binary Heap:
A Binary Heap is a Binary Tree with following properties.
1) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.
// A C++ program to demonstrate common Binary Heap Operations
#include<iostream>
#include<climits>
using namespace std;
// Prototype of a utility function to swap two integers
void swap(int *x, int *y);
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int capacity); // Constructor
void MinHeapify(int );
int parent(int i) { return (i-1)/2; }
int left(int i) { return (2*i + 1); } // to get index of left child of node at index i
int right(int i) { return (2*i + 2); } // to get index of right child of node at index i
int extractMin(); // to extract the root which is the minimum element
void decreaseKey(int i, int new_val); // Decreases key value of key at index i to new_val
int getMin() { return harr[0]; } // Returns the minimum key (key at root) from min heap
void deleteKey(int i); // Deletes a key stored at index i
void insertKey(int k); // Inserts a new key 'k'
};
MinHeap::MinHeap(int cap) // Constructor: Builds a heap from a given array a[] of given size
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
void MinHeap::insertKey(int k)
{
if (heap_size == capacity)
{
cout << "\nOverflow: Could not insertKey\n";
return;
}
heap_size++;
int i = heap_size - 1;
harr[i] = k;
while (i != 0 && harr[parent(i)] > harr[i]) // Fix the min heap property if it is violated
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}
void MinHeap::decreaseKey(int i, int new_val)
{
harr[i] = new_val;
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}
int MinHeap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);
return root;
}
void MinHeap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int main()
{
MinHeap h(11);
h.insertKey(3);
h.insertKey(2);
h.deleteKey(1);
h.insertKey(15);
h.insertKey(5);
h.insertKey(4);
h.insertKey(45);
cout << h.extractMin() << " ";
cout << h.getMin() << " ";
h.decreaseKey(2, 1);
cout << h.getMin();
return 0;
}
Binomial Heap:
A Binomial Heap is a set of Binomial Trees where each Binomial Tree follows Min Heap property. And there can be at-most one Binomial Tree of any degree. A Binomial Tree of order k has following properties:
a) It has exactly 2k nodes.
b) It has depth as k.
c) There are exactly kCi nodes at depth i for i = 0, 1, . . . , k.
d) The root has degree k and children of root are themselves Binomial Trees with order k-1, k-2,.. 0 from left to right.
12------------10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
A Binomial Heap with 13 nodes. It is a collection of 3 Binomial Trees of orders 0, 2 and 3 from left to right.
Hashing:
Hashing is an improvement over Direct Access Table. The idea is to use hash function that converts a given phone number or any other key to a smaller number and uses the small number as index in a table called hash table.
Since a hash function gets us a small number for a key which is a big integer or string, there is possibility that two keys result in same value.Following are the ways to handle collisions:
Chaining:The idea is to make each cell of hash table point to a linked list of records that have same hash function value.
Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we one by one examine table slots until the desired element is found or it is clear that the element is not in the table.
Graph:
Graph is a data structure that consists of following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge.The pair of form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost
Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j }
Adjacency List: An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists.
Adjacency list representation of graphs
#include <stdio.h>
#include <stdlib.h>
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
struct Graph
{
int V;
struct AdjList* array;
};
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int main()
{
// create the graph given in above fugure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}
Traversal for a Graph:
BFS:
#include<iostream>
#include <list>
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BFS(int s); // prints BFS traversal from a given source s
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
bool *visited = new bool[V]; // Mark all the vertices as not visited
for(int i = 0; i < V; i++)
visited[i] = false;
list<int> queue; // Create a queue for BFS
visited[s] = true; // Mark the current node as visited and enqueue it
queue.push_back(s);
list<int>::iterator i; // 'i' will be used to get all adjacent vertices of a vertex
while(!queue.empty())
{
s = queue.front(); // Dequeue a vertex from queue and print it
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex If a adjacent has not been visited, then mark it visited and enqueue it
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal (starting from vertex 2) \n";
g.BFS(2);
return 0;
}
DFS:
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int v) // DFS traversal of the vertices reachable from v. It uses recursive DFSUtil
{
bool *visited = new bool[V]; // Mark all the vertices as not visited
for(int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(v, visited); // Call the recursive helper function to print DFS traversal
}
AVL Tree:
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all node
Insertion
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left;
struct node *right;
int height;
};
int max(int a, int b);
int height(struct node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
struct node* newNode(int key)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
struct node *rightRotate(struct node *y)
{
struct node *x = y->left;
struct 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;
}
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
struct 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;
}
int getBalance(struct node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key)
{
if (node == NULL) /* Perform the normal BST rotation */
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
node->height = max(height(node->left), height(node->right)) + 1;
int balance = getBalance(node);
if (balance > 1 && key < node->left->key) // Left Left Case
return rightRotate(node);
if (balance < -1 && key > node->right->key) // Left Left Case
return leftRotate(node);
if (balance > 1 && key > node->left->key) // Left Right Case
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) // Right Left Case
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preOrder(struct node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
printf("Pre order traversal of the constructed AVL tree is \n");
preOrder(root);
return 0;
}
Deletion:
struct node* deleteNode(struct 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
{
if( (root->left == NULL) || (root->right == NULL) )
{
struct node *temp = root->left ? root->left : root->right;
if(temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
}
else
{
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == NULL)
return root;
root->height = max(height(root->left), height(root->right)) + 1;
int balance = getBalance(root);
if (balance > 1 && getBalance(root->left) >= 0) // Left Left Case
return rightRotate(root);
if (balance > 1 && getBalance(root->left) < 0) // Left Right Case
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->right) <= 0) // Right Right Case
return leftRotate(root);
if (balance < -1 && getBalance(root->right) > 0) // Right Left Case
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
Splay Tree:
Splay tree is also self-balancing BST. The main idea of splay tree is to bring the recently accessed item to root of the tree, this makes the recently searched item to be accessible in O(1) time if accessed again
Search Operation:
There are following cases for the node being accessed.
1) Node is root We simply return the root, don’t do anything else as the accessed node is already root.
2) Zig: Node is child of root (the node has no grandparent). Node is either a left child of root (we do a right rotation) or node is a right child of its parent (we do a left rotation).
3) Node has both parent and grandparent. There can be following subcases.
........3.a) Zig-Zig and Zag-Zag Node is left child of parent and parent is also left child of grand parent (Two right rotations) OR node is right child of its parent and parent is also right child of grand parent (Two Left Rotations).
........3.b) Zig-Zag and Zag-Zig Node is left child of parent and parent is right child of grand parent (Left Rotation followed by right rotation) OR node is right child of its parent and parent is left child of grand parent (Right Rotation followed by left rotation).
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
struct node* newNode(int key)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
struct node *rightRotate(struct node *x)
{
struct node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
// This function modifies the tree and returns the new root
struct node *splay(struct node *root, int key)
{
if (root == NULL || root->key == key) // Base cases: root is NULL or key is present at root
return root;
if (root->key > key) // Key lies in left subtree
{
if (root->left == NULL) return root; // Key is not in tree, we are done
if (root->left->key > key) // Zig-Zig (Left Left)
{
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
}
else if (root->left->key < key) // Zig-Zag (Left Right)
{
root->left->right = splay(root->left->right, key);
if (root->left->right != NULL)
root->left = leftRotate(root->left);
}
return (root->left == NULL)? root: rightRotate(root);
}
else // Key lies in right subtree
{
if (root->right == NULL) return root; // Key is not in tree, we are done
if (root->right->key > key) // Zag-Zig (Right Left)
{
root->right->left = splay(root->right->left, key);
if (root->right->left != NULL)
root->right = rightRotate(root->right);
}
else if (root->right->key < key) // Zag-Zag (Right Right)
{
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
return (root->right == NULL)? root: leftRotate(root);
}
}
struct node *search(struct node *root, int key)
{
return splay(root, key);
}
void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct node *root = newNode(100);
root->left = newNode(50);
root->right = newNode(200);
root->left->left = newNode(40);
root->left->left->left = newNode(30);
root->left->left->left->left = newNode(20);
root = search(root, 20);
printf("Preorder traversal of the modified Splay tree is \n");
preOrder(root);
return 0;
}
Insert:
Following are different cases to insert a key k in splay tree.
1) Root is NULL: We simply allocate a new node and return it as root.
2) Splay the given key k. If k is already present, then it becomes the new root. If not present, then last accessed leaf node becomes the new root.
3) If new root’s key is same as k, don’t do anything as k is already present.
4) Else allocate memory for new node and compare root’s key with k.
…….4.a) If k is smaller than root’s key, make root as right child of new node, copy left child of root as left child of new node and make left child of root as NULL.
…….4.b) If k is greater than root’s key, make root as left child of new node, copy right child of root as right child of new node and make right child of root as NULL.
5) Return new node as new root of tree.
Program:
struct node *insert(struct node *root, int k)
{
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->key == k) return root;
struct node *newnode = newNode(k);
if (root->key > k)
{
newnode->right = root;
newnode->left = root->left;
root->left = NULL;
}
else
{
newnode->left = root;
newnode->right = root->right;
root->right = NULL;
}
return newnode; // newnode becomes new root
}
B-Tree:
To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations require O(h) disk accesses where h is height of the tree. B-tree is a fat tree. Height of B-Trees is kept low by putting maximum possible keys in a B-Tree node. Generally, a B-Tree node size is kept equal to the disk block size
Insertion
1) Initialize x as root.
2) While x is not leaf, do following
..a) Find the child of x that is going to to be traversed next. Let the child be y.
..b) If y is not full, change x to point to y.
..c) If y is full, split it and change x to point to one of the two parts of y. If k is smaller than mid key in y, then set x as first part of y. Else second part of y. When we split y, we move a key from y to its parent x.
3) The loop in step 2 stops when x is leaf. x must have space for 1 extra key as we have been splitting all nodes in advance. So simply insert k to x.
Deletion:
We sketch how deletion works with various cases of deleting keys from a B-tree.
1. If the key k is in node x and x is a leaf, delete the key k from x.
2. If the key k is in node x and x is an internal node, do the following.
a) If the child y that precedes k in node x has at least t keys, then find the predecessor k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
b) If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k0 of k in the subtree rooted at z. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
c) Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.
3. If the key k is not present in internal node x, determine the root x.c(i) of the appropriate subtree that must contain k, if k is in the tree at all. If x.c(i) has only t-1 keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys. Then finish by recursing on the appropriate child of x.
a) If x.c(i) has only t-1 keys but has an immediate sibling with at least t keys, give x.c(i) an extra key by moving a key from x down into x.c(i), moving a key from x.c(i) ’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.c(i).
b) If x.c(i) and both of x.c(i)’s immediate siblings have t-1 keys, merge x.c(i) with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node
C++ implemntation of search and traverse:
#include<iostream>
using namespace std;
class BTreeNode
{
int *keys; // An array of keys
int t; // Minimum degree (defines the range for number of keys)
BTreeNode **C; // An array of child pointers
int n; // Current number of keys
bool leaf; // Is true when node is leaf. Otherwise false
public:
BTreeNode(int _t, bool _leaf); // Constructor
void traverse();
BTreeNode *search(int k); // returns NULL if k is not present.
friend class BTree;
};
class BTree
{
BTreeNode *root; // Pointer to root node
int t; // Minimum degree
public:
BTree(int _t)
{ root = NULL; t = _t; }
void traverse()
{ if (root != NULL) root->traverse(); }
BTreeNode* search(int k)
{ return (root == NULL)? NULL : root->search(k); }
};
BTreeNode::BTreeNode(int _t, bool _leaf)
{
t = _t; // Copy the given minimum degree and leaf property
leaf = _leaf;
keys = new int[2*t-1];
C = new BTreeNode *[2*t];
n = 0; // Initialize the number of keys as 0
}
void BTreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
BTreeNode *BTreeNode::search(int k)
{
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
C++ implemntation of insert and delete:
#include<iostream>
using namespace std;
class BTreeNode
{
int *keys; // An array of keys
int t; // Minimum degree (defines the range for number of keys)
BTreeNode **C; // An array of child pointers
int n; // Current number of keys
bool leaf; // Is true when node is leaf. Otherwise false
public:
BTreeNode(int _t, bool _leaf); // Constructor
void traverse();
BTreeNode *search(int k); // returns NULL if k is not present.
int findKey(int k);
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void remove(int k);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);
int getPred(int idx); // A function to get the predecessor of the key-
int getSucc(int idx);
void fill(int idx);
void borrowFromPrev(int idx);
void borrowFromNext(int idx);
void merge(int idx);
friend class BTree;
};
class BTree
{
BTreeNode *root; // Pointer to root node
int t; // Minimum degree
public:
BTree(int _t)
{
root = NULL;
t = _t;
}
void traverse()
{
if (root != NULL) root->traverse();
}
BTreeNode* search(int k)
{
return (root == NULL)? NULL : root->search(k);
}
void insert(int k);
void remove(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;
}
int BTreeNode::findKey(int k)
{
int idx=0;
while (idx<n && keys[idx] < k)
++idx;
return idx;
}
void BTreeNode::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 "<< k <<" is does not exist in the tree\n";
return;
}
bool flag = ( (idx==n)? true : false );
if (C[idx]->n < t)
fill(idx);
if (flag && idx > n)
C[idx-1]->remove(k);
else
C[idx]->remove(k);
}
return;
}
void BTreeNode::removeFromLeaf (int idx)
{
for (int i=idx+1; i<n; ++i)
keys[i-1] = keys[i];
n--;
return;
}
void BTreeNode::removeFromNonLeaf(int idx)
{
int k = keys[idx];
if (C[idx]->n >= t)
{
int pred = getPred(idx);
keys[idx] = pred;
C[idx]->remove(pred);
}
else if (C[idx+1]->n >= t)
{
int succ = getSucc(idx);
keys[idx] = succ;
C[idx+1]->remove(succ);
}
else
{
merge(idx);
C[idx]->remove(k);
}
return;
}
int BTreeNode::getPred(int idx)
{
BTreeNode *cur=C[idx];
while (!cur->leaf)
cur = cur->C[cur->n];
return cur->keys[cur->n-1];
}
int BTreeNode::getSucc(int idx)
{
BTreeNode *cur = C[idx+1];
while (!cur->leaf)
cur = cur->C[0];
return cur->keys[0];
}
void BTreeNode::fill(int idx)
{
if (idx!=0 && C[idx-1]->n>=t)
borrowFromPrev(idx);
else if (idx!=n && C[idx+1]->n>=t)
borrowFromNext(idx);
else
{
if (idx != n)
merge(idx);
else
merge(idx-1);
}
return;
}
void BTreeNode::borrowFromPrev(int idx)
{
BTreeNode *child=C[idx];
BTreeNode *sibling=C[idx-1];
for (int i=child->n-1; i>=0; --i)
child->keys[i+1] = child->keys[i];
if (!child->leaf)
{
for(int i=child->n; i>=0; --i)
child->C[i+1] = child->C[i];
}
child->keys[0] = keys[idx-1];
if (!leaf)
child->C[0] = sibling->C[sibling->n];
keys[idx-1] = sibling->keys[sibling->n-1];
child->n += 1;
sibling->n -= 1;
return;
}
void BTreeNode::borrowFromNext(int idx)
{
BTreeNode *child=C[idx];
BTreeNode *sibling=C[idx+1];
child->keys[(child->n)] = keys[idx];
if (!(child->leaf))
child->C[(child->n)+1] = sibling->C[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->C[i-1] = sibling->C[i];
}
child->n += 1;
sibling->n -= 1;
return;
}
void BTreeNode::merge(int idx)
{
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx+1];
child->keys[t-1] = keys[idx];
for (int i=0; i<sibling->n; ++i)
child->keys[i+t] = sibling->keys[i];
if (!child->leaf)
{
for(int i=0; i<=sibling->n; ++i)
child->C[i+t] = sibling->C[i];
}
for (int i=idx+1; i<n; ++i)
keys[i-1] = keys[i];
for (int i=idx+2; i<=n; ++i)
C[i-1] = C[i];
child->n += sibling->n+1;
n--;
delete(sibling);
return;
}
void BTree::insert(int k)
{
if (root == NULL)
{
root = new BTreeNode(t, true);
root->keys[0] = k; // Insert key
root->n = 1; // Update number of keys in root
}
else // If tree is not empty
{
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);
root = s;
}
else // If root is not full, call insertNonFull for root
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 // If this node is not leaf
{
while (i >= 0 && keys[i] > k)
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;
for (int j = n; j >= i+1; j--)
C[j+1] = C[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;
}
void BTreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
BTreeNode *BTreeNode::search(int k)
{
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
void BTree::remove(int k)
{
if (!root)
{
cout << "The tree is empty\n";
return;
}
root->remove(k);
if (root->n==0)
{
BTreeNode *tmp = root;
if (root->leaf)
root = NULL;
else
root = root->C[0];
delete tmp;
}
return;
}
int main()
{
BTree t(3); // A B-Tree with minium degree 3
t.insert(1);
t.insert(3);
t.insert(7);
t.insert(10);
t.insert(11);
t.insert(13);
t.insert(14);
t.insert(15);
t.insert(18);
t.insert(16);
t.insert(19);
t.insert(24);
t.insert(25);
t.insert(26);
t.insert(21);
t.insert(4);
t.insert(5);
t.insert(20);
t.insert(22);
t.insert(2);
t.insert(17);
t.insert(12);
t.insert(6);
cout << "Traversal of tree constructed is\n";
t.traverse();
cout << endl;
t.remove(6);
cout << "Traversal of tree after removing 6\n";
t.traverse();
cout << endl;
t.remove(13);
cout << "Traversal of tree after removing 13\n";
t.traverse();
cout << endl;
t.remove(7);
cout << "Traversal of tree after removing 7\n";
t.traverse();
cout << endl;
t.remove(4);
cout << "Traversal of tree after removing 4\n";
t.traverse();
cout << endl;
t.remove(2);
cout << "Traversal of tree after removing 2\n";
t.traverse();
cout << endl;
t.remove(16);
cout << "Traversal of tree after removing 16\n";
t.traverse();
cout << endl;
return 0;
}
Red Black Tree:
Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node follows following rules.
1) Every node has a color either red or black.
2) Root of tree is always black.
3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).
4) Every path from root to a NULL node has same number of black nodes.
Insert:
The algorithms has mainly two cases depending upon the color of uncle. If uncle is red, we do recoloring. If uncle is black, we do rotations and/or recoloring.
Color of a NULL node is considered as BLACK.
Let x be the newly inserted node.
1) Perform standard BST insertion and make the color of newly inserted nodes as RED.
2) Do following if color of x’s parent is not BLACK or x is not root.
….a) If x’s uncle is RED (Grand parent must have been black from property 4)
……..(i) Change color of parent and uncle as BLACK.
……..(ii) color of grand parent as RED.
……..(iii) Change x = x’s grandparent, repeat steps 2 and 3 for new x.
redBlackCase2
….b) If x’s uncle is BLACK, then there can be four configurations for x, x’s parent (p) and x’s grandparent (g) (This is similar to AVL Tree)
……..i) Left Left Case (p is left child of g and x is left child of p)
……..ii) Left Right Case (p is left child of g and x is right child of p)
……..iii) Right Right Case (Mirror of case a)
……..iv) Right Left Case (Mirror of case c)
3) If x is root, change color of x as BLACK (Black height of complete tree increases by 1).
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data; // for data part
char color; // for color property
struct node *left, *right, *parent;
};
void LeftRotate(struct node **root,struct node *x)
{
struct node *y = x->right;
x->right = y->left;
if (x->right != NULL)
x->right->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;
}
void rightRotate(struct node **root,struct node *y)
{
struct node *x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
x->parent =y->parent;
if (x->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;
}
void insertFixUp(struct node **root,struct node *z)
{
while (z != *root && z->parent->color == 'R')
{
struct node *y;
if (z->parent == z->parent->parent->left)
y = z->parent->parent->right;
else
y = z->parent->parent->left;
// If uncle is RED, do following
if (y->color == 'R')
{
y->color = 'B';
z->parent->color = 'B';
z->parent->parent->color = 'R';
z = z->parent->parent;
}
// Uncle is BLACK, there are four cases (LL, LR, RL and RR)
else
{
// Left-Left (LL) case, do following
if (z->parent == z->parent->parent->left &&
z == z->parent->left)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent->parent);
}
// Left-Right (LR) case, do following
if (z->parent == z->parent->parent->left &&
z == z->parent->right)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
LeftRotate(root,z->parent);
rightRotate(root,z->parent->parent);
}
// Right-Right (RR) case, do following
if (z->parent == z->parent->parent->right &&
z == z->parent->right)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
LeftRotate(root,z->parent->parent);
}
// Right-Left (RL) case, do following
if (z->parent == z->parent->parent->right &&
z == z->parent->left)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent);
LeftRotate(root,z->parent->parent);
}
}
}
(*root)->color = 'B'; //keep root always black
}
void insert(struct node **root, int data)
{
struct node *z = (struct node*)malloc(sizeof(struct node));
z->data = data;
z->left = z->right = z->parent = NULL;
if (*root == NULL)
{
z->color = 'B';
(*root) = z;
}
else
{
struct node *y = NULL;
struct node *x = (*root);
while (x != NULL)
{
y = x;
if (z->data < x->data)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (z->data > y->data)
y->right = z;
else
y->left = z;
z->color = 'R';
insertFixUp(root,z);
}
}
void inorder(struct node *root)
{
if (root == NULL)
return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main()
{
struct node *root = NULL;
insert(&root,5);
insert(&root,3);
insert(&root,7);
insert(&root,2);
insert(&root,4);
insert(&root,6);
insert(&root,8);
insert(&root,11);
printf("inorder Traversal Is : ");
inorder(root);
return 0;
}
Deletion Steps
Following are detailed steps for deletion.
1) Perform standard BST delete. When we perform standard delete operation in BST, we always end up deleting a node which is either leaf or has only one child (For an internal node, we copy the successor and then recursively call delete for successor, successor is always a leaf node or a node with one child). So we only need to handle cases where a node is leaf or has one child. Let v be the node deleted and u be the child that replaces v.
2) Simple Case: If either u or v is red, we mark the replaced child as black (No change in black height). Note that both u and v cannot be red as v is parent of u and two consecutive reds are not allowed in red-black tree.
3) If Both u and v are Black.
3.1) Color u as double black. Now our task reduces to convert this double black to single black. Note that If v is leaf, then u is NULL and color of NULL is considered as black. So the deletion of a black leaf also causes a double black.
3.2) Do following while the current node u is double black or it is not root. Let sibling of node be s.
….(a): If sibling s is black and at least one of sibling’s children is red, perform rotation(s). Let the red child of s be r. This case can be divided in four subcases depending upon positions of s and r.
…………..(i) Left Left Case (s is left child of its parent and r is left child of s or both children of s are red). This is mirror of right right case shown in below diagram.
…………..(ii) Left Right Case (s is left child of its parent and r is right child). This is mirror of right left case shown in below diagram.
…………..(iii) Right Right Case (s is right child of its parent and r is right child of s or both children of s are red)
…………..(iv) Right Left Case (s is right child of its parent and r is left child of s)
…..(b): If sibling is black and its both children are black, perform recoloring, and recur for the parent if parent is black.
In this case, if parent was red, then we didn’t need to recur for prent, we can simply make it black (red + double black = single black)
…..(c): If sibling is red, perform a rotation to move old sibling up, recolor the old sibling and parent. The new sibling is always black (See the below diagram). This mainly converts the tree to black sibling case (by rotation) and leads to case (a) or (b). This case can be divided in two subcases.
…………..(i) Left Case (s is left child of its parent). This is mirror of right right case shown in below diagram. We right rotate the parent p.
…………..(iii) Right Case (s is right child of its parent). We left rotate the parent p.
3.3) If u is root, make it single black and return (Black height of complete tree reduces by 1).
Thats it for Now..............
Linked Lists:
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.Each node in a list consists of at least two parts: 1) data 2) pointer to the next node.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
void printList(struct node *n)
{
while (n != NULL)
{
printf(" %d ", n->data);
n = n->next;
}
}
int main()
{
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
head = (struct node*)malloc(sizeof(struct node));
second = (struct node*)malloc(sizeof(struct node));
third = (struct node*)malloc(sizeof(struct node));
head->data = 1; //assign data in first node
head->next = second; // Link first node with the second node
second->data = 2; //assign data to second node
second->next = third;
third->data = 3; //assign data to third node
third->next = NULL;
printList(head);//traversal
getchar();
return 0;
}
Inserting a node in Linked List:
add node at the front.
void push(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
after a given node:
void insertAfter(struct node* prev_node, int new_data)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct node* new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. move the next of prev_node as new_node */
prev_node->next = new_node;
}
at the end:
void append(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
struct node *last = *head_ref; /* used in 2*/
new_node->data = new_data;
new_node->next = NULL;
/* 1. If the Linked List is empty, then make the new node as head */
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
/* 2. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 3. Change the next of last node */
last->next = new_node;
return;
}
Deleting a node from linked list:
To delete a node from linked list, we need to do following steps.
1) Find previous node of the node to be deleted.
2) Changed next of previous node.
3) Free memory for the node to be deleted.
void deleteNode(struct node **head_ref, int key)
{
struct node* temp = *head_ref, *prev;
if (temp != NULL && temp->data == key)
{
*head_ref = temp->next; // Changed head
free(temp); // free old head
return;
}
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp); // Free memory
}
Circular linked list
Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.
Function to insert a node at the begining of a Circular linked list
void push(struct node **head_ref, int data)
{
struct node *ptr1 = (struct node *)malloc(sizeof(struct node));
struct node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then set the next of last node */
if (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
Function to print nodes in a given Circular linked list
void printList(struct node *head)
{
struct node *temp = head;
if (head != NULL)
{
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
}
}
Sorted insert for circular linked list
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data < new_node->data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;
Doubly Linked List
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
struct node
{
int data;
struct node *next; // Pointer to next node in DLL
struct node *prev; // Pointer to previous node in DLL
};
Inserting a node:
1) Add a node at the front:
void push(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
(*head_ref) = new_node;
}
2) Add a node after a given node.:
void insertAfter(struct node* prev_node, int new_data)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct node* new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
new_node->prev = prev_node;
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
3) Add a node at the end:
void append(struct node** head_ref, int new_data)
{
struct node* new_node = (struct node*) malloc(sizeof(struct node));
struct node *last = *head_ref; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL)
{
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
Delete a node in a Doubly Linked List:
void deleteNode(struct node **head_ref, struct node *del)
{
if(*head_ref == NULL || del == NULL)
return;
if(*head_ref == del)
*head_ref = del->next;
if(del->next != NULL)
del->next->prev = del->prev;
if(del->prev != NULL)
del->prev->next = del->next;
free(del);
return;
}
Traverse a list is similar to singly linked list
Stack:
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Push: Adds an item in the stack.
Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed.
Peek: Get the topmost item.
Stack Using Arrays:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Stack
{
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
return stack;
}
int isFull(struct Stack* stack)
{ return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack)
{ return stack->top == -1; }
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
int main()
{
struct Stack* stack = createStack(100);
push(stack, 10);
push(stack, 20);
push(stack, 30);
printf("%d popped from stack\n", pop(stack));
printf("Top item is %d\n", peek(stack));
return 0;
}
Stack Using Linked List:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct StackNode
{
int data;
struct StackNode* next;
};
struct StackNode* newNode(int data)
{
struct StackNode* stackNode =
(struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
int isEmpty(struct StackNode *root)
{
return !root;
}
void push(struct StackNode** root, int data)
{
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d pushed to stack\n", data);
}
int pop(struct StackNode** root)
{
if (isEmpty(*root))
return INT_MIN;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct StackNode* root)
{
if (isEmpty(root))
return INT_MIN;
return root->data;
}
int main()
{
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack\n", pop(&root));
printf("Top element is %d\n", peek(root));
return 0;
}
Queue:
Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO)
Enqueue: Adds an item to the queue.
Dequeue: Removes an item from the queue.
Front: Get the front item from queue.
Rear: Get the last item from queue.
Array implementation Of Queue
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Queue
{
int front, rear, size;
unsigned capacity;
int* array;
};
struct Queue* createQueue(unsigned capacity)
{
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1; // This is important, see the enqueue
queue->array = (int*) malloc(queue->capacity * sizeof(int));
return queue;
}
int isFull(struct Queue* queue)
{ return (queue->size == queue->capacity); }
int isEmpty(struct Queue* queue)
{ return (queue->size == 0); }
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)%queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf("%d enqueued to queue\n", item);
}
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)%queue->capacity;
queue->size = queue->size - 1;
return item;
}
int front(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
int rear(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
int main()
{
struct Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
printf("%d dequeued from queue\n", dequeue(queue));
printf("Front item is %d\n", front(queue));
printf("Rear item is %d\n", rear(queue));
return 0;
}
linked list based implementation of queue
#include <stdlib.h>
#include <stdio.h>
struct QNode
{
int key;
struct QNode *next;
};
struct Queue
{
struct QNode *front, *rear;
};
struct QNode* newNode(int k)
{
struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
temp->key = k;
temp->next = NULL;
return temp;
}
struct Queue *createQueue()
{
struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
void enQueue(struct Queue *q, int k)
{
struct QNode *temp = newNode(k);
if (q->rear == NULL)
{
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
struct QNode *deQueue(struct Queue *q)
{.
if (q->front == NULL)
return NULL;
struct QNode *temp = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
return temp;
}
int main()
{
struct Queue *q = createQueue();
enQueue(q, 10);
enQueue(q, 20);
deQueue(q);
deQueue(q);
enQueue(q, 30);
enQueue(q, 40);
enQueue(q, 50);
struct QNode *n = deQueue(q);
if (n != NULL)
printf("Dequeued item is %d", n->key);
return 0;
}
Binary Tree:
Trees:Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical data structures. The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent.Finally, elements with no children are called leaves.
Binary Tree: A tree whose elements have at most 2 children is called a binary tree.We typically name them the left and right child. A Tree node contains following parts.1. Data 2. Pointer to left child 3. Pointer to right child
#include<stdio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
/* 4 becomes left child of 2
1
/ \
2 3
/ \ / \
4 NULL NULL NULL
/ \
NULL NULL
*/
getchar();
return 0;
}
Full Binary Tree A Binary Tree is full if every node has 0 or 2 children.
Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible
Inorder Traversal:
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Preorder Traversal:
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Postorder Traversal:
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
Example:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void printPostorder(struct node* node)
{
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
printf("%d ", node->data);
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
void printPreorder(struct node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("\n Preorder traversal of binary tree is \n");
printPreorder(root);
printf("\n Inorder traversal of binary tree is \n");
printInorder(root);
printf("\n Postorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
Binary Search Tree:
Binary Search Tree, is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
Example:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct 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);
return node;
}
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
inorder(root);
return 0;
}
Searching a key:
struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
Delete a node:
1) Node to be deleted is leaf: Simply remove from the tree.
2) Node to be deleted has only one child: Copy the child to the node and delete the child
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
struct node* deleteNode(struct 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)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two children: Get the inorder successor
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
Binary Heap:
A Binary Heap is a Binary Tree with following properties.
1) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.
// A C++ program to demonstrate common Binary Heap Operations
#include<iostream>
#include<climits>
using namespace std;
// Prototype of a utility function to swap two integers
void swap(int *x, int *y);
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int capacity); // Constructor
void MinHeapify(int );
int parent(int i) { return (i-1)/2; }
int left(int i) { return (2*i + 1); } // to get index of left child of node at index i
int right(int i) { return (2*i + 2); } // to get index of right child of node at index i
int extractMin(); // to extract the root which is the minimum element
void decreaseKey(int i, int new_val); // Decreases key value of key at index i to new_val
int getMin() { return harr[0]; } // Returns the minimum key (key at root) from min heap
void deleteKey(int i); // Deletes a key stored at index i
void insertKey(int k); // Inserts a new key 'k'
};
MinHeap::MinHeap(int cap) // Constructor: Builds a heap from a given array a[] of given size
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
void MinHeap::insertKey(int k)
{
if (heap_size == capacity)
{
cout << "\nOverflow: Could not insertKey\n";
return;
}
heap_size++;
int i = heap_size - 1;
harr[i] = k;
while (i != 0 && harr[parent(i)] > harr[i]) // Fix the min heap property if it is violated
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}
void MinHeap::decreaseKey(int i, int new_val)
{
harr[i] = new_val;
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}
int MinHeap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);
return root;
}
void MinHeap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int main()
{
MinHeap h(11);
h.insertKey(3);
h.insertKey(2);
h.deleteKey(1);
h.insertKey(15);
h.insertKey(5);
h.insertKey(4);
h.insertKey(45);
cout << h.extractMin() << " ";
cout << h.getMin() << " ";
h.decreaseKey(2, 1);
cout << h.getMin();
return 0;
}
Binomial Heap:
A Binomial Heap is a set of Binomial Trees where each Binomial Tree follows Min Heap property. And there can be at-most one Binomial Tree of any degree. A Binomial Tree of order k has following properties:
a) It has exactly 2k nodes.
b) It has depth as k.
c) There are exactly kCi nodes at depth i for i = 0, 1, . . . , k.
d) The root has degree k and children of root are themselves Binomial Trees with order k-1, k-2,.. 0 from left to right.
12------------10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
A Binomial Heap with 13 nodes. It is a collection of 3 Binomial Trees of orders 0, 2 and 3 from left to right.
Hashing:
Hashing is an improvement over Direct Access Table. The idea is to use hash function that converts a given phone number or any other key to a smaller number and uses the small number as index in a table called hash table.
Since a hash function gets us a small number for a key which is a big integer or string, there is possibility that two keys result in same value.Following are the ways to handle collisions:
Chaining:The idea is to make each cell of hash table point to a linked list of records that have same hash function value.
Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we one by one examine table slots until the desired element is found or it is clear that the element is not in the table.
Graph:
Graph is a data structure that consists of following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge.The pair of form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost
Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j }
Adjacency List: An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists.
Adjacency list representation of graphs
#include <stdio.h>
#include <stdlib.h>
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
struct Graph
{
int V;
struct AdjList* array;
};
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int main()
{
// create the graph given in above fugure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}
Traversal for a Graph:
BFS:
#include<iostream>
#include <list>
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BFS(int s); // prints BFS traversal from a given source s
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
bool *visited = new bool[V]; // Mark all the vertices as not visited
for(int i = 0; i < V; i++)
visited[i] = false;
list<int> queue; // Create a queue for BFS
visited[s] = true; // Mark the current node as visited and enqueue it
queue.push_back(s);
list<int>::iterator i; // 'i' will be used to get all adjacent vertices of a vertex
while(!queue.empty())
{
s = queue.front(); // Dequeue a vertex from queue and print it
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex If a adjacent has not been visited, then mark it visited and enqueue it
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal (starting from vertex 2) \n";
g.BFS(2);
return 0;
}
DFS:
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int v) // DFS traversal of the vertices reachable from v. It uses recursive DFSUtil
{
bool *visited = new bool[V]; // Mark all the vertices as not visited
for(int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(v, visited); // Call the recursive helper function to print DFS traversal
}
AVL Tree:
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all node
Insertion
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left;
struct node *right;
int height;
};
int max(int a, int b);
int height(struct node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
struct node* newNode(int key)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}
struct node *rightRotate(struct node *y)
{
struct node *x = y->left;
struct 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;
}
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
struct 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;
}
int getBalance(struct node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key)
{
if (node == NULL) /* Perform the normal BST rotation */
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
node->height = max(height(node->left), height(node->right)) + 1;
int balance = getBalance(node);
if (balance > 1 && key < node->left->key) // Left Left Case
return rightRotate(node);
if (balance < -1 && key > node->right->key) // Left Left Case
return leftRotate(node);
if (balance > 1 && key > node->left->key) // Left Right Case
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) // Right Left Case
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preOrder(struct node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
printf("Pre order traversal of the constructed AVL tree is \n");
preOrder(root);
return 0;
}
Deletion:
struct node* deleteNode(struct 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
{
if( (root->left == NULL) || (root->right == NULL) )
{
struct node *temp = root->left ? root->left : root->right;
if(temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
}
else
{
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == NULL)
return root;
root->height = max(height(root->left), height(root->right)) + 1;
int balance = getBalance(root);
if (balance > 1 && getBalance(root->left) >= 0) // Left Left Case
return rightRotate(root);
if (balance > 1 && getBalance(root->left) < 0) // Left Right Case
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->right) <= 0) // Right Right Case
return leftRotate(root);
if (balance < -1 && getBalance(root->right) > 0) // Right Left Case
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
Splay Tree:
Splay tree is also self-balancing BST. The main idea of splay tree is to bring the recently accessed item to root of the tree, this makes the recently searched item to be accessible in O(1) time if accessed again
Search Operation:
There are following cases for the node being accessed.
1) Node is root We simply return the root, don’t do anything else as the accessed node is already root.
2) Zig: Node is child of root (the node has no grandparent). Node is either a left child of root (we do a right rotation) or node is a right child of its parent (we do a left rotation).
3) Node has both parent and grandparent. There can be following subcases.
........3.a) Zig-Zig and Zag-Zag Node is left child of parent and parent is also left child of grand parent (Two right rotations) OR node is right child of its parent and parent is also right child of grand parent (Two Left Rotations).
........3.b) Zig-Zag and Zag-Zig Node is left child of parent and parent is right child of grand parent (Left Rotation followed by right rotation) OR node is right child of its parent and parent is left child of grand parent (Right Rotation followed by left rotation).
#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
struct node* newNode(int key)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
struct node *rightRotate(struct node *x)
{
struct node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
// This function modifies the tree and returns the new root
struct node *splay(struct node *root, int key)
{
if (root == NULL || root->key == key) // Base cases: root is NULL or key is present at root
return root;
if (root->key > key) // Key lies in left subtree
{
if (root->left == NULL) return root; // Key is not in tree, we are done
if (root->left->key > key) // Zig-Zig (Left Left)
{
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
}
else if (root->left->key < key) // Zig-Zag (Left Right)
{
root->left->right = splay(root->left->right, key);
if (root->left->right != NULL)
root->left = leftRotate(root->left);
}
return (root->left == NULL)? root: rightRotate(root);
}
else // Key lies in right subtree
{
if (root->right == NULL) return root; // Key is not in tree, we are done
if (root->right->key > key) // Zag-Zig (Right Left)
{
root->right->left = splay(root->right->left, key);
if (root->right->left != NULL)
root->right = rightRotate(root->right);
}
else if (root->right->key < key) // Zag-Zag (Right Right)
{
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
return (root->right == NULL)? root: leftRotate(root);
}
}
struct node *search(struct node *root, int key)
{
return splay(root, key);
}
void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct node *root = newNode(100);
root->left = newNode(50);
root->right = newNode(200);
root->left->left = newNode(40);
root->left->left->left = newNode(30);
root->left->left->left->left = newNode(20);
root = search(root, 20);
printf("Preorder traversal of the modified Splay tree is \n");
preOrder(root);
return 0;
}
Insert:
Following are different cases to insert a key k in splay tree.
1) Root is NULL: We simply allocate a new node and return it as root.
2) Splay the given key k. If k is already present, then it becomes the new root. If not present, then last accessed leaf node becomes the new root.
3) If new root’s key is same as k, don’t do anything as k is already present.
4) Else allocate memory for new node and compare root’s key with k.
…….4.a) If k is smaller than root’s key, make root as right child of new node, copy left child of root as left child of new node and make left child of root as NULL.
…….4.b) If k is greater than root’s key, make root as left child of new node, copy right child of root as right child of new node and make right child of root as NULL.
5) Return new node as new root of tree.
Program:
struct node *insert(struct node *root, int k)
{
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->key == k) return root;
struct node *newnode = newNode(k);
if (root->key > k)
{
newnode->right = root;
newnode->left = root->left;
root->left = NULL;
}
else
{
newnode->left = root;
newnode->right = root->right;
root->right = NULL;
}
return newnode; // newnode becomes new root
}
B-Tree:
To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. The main idea of using B-Trees is to reduce the number of disk accesses. Most of the tree operations require O(h) disk accesses where h is height of the tree. B-tree is a fat tree. Height of B-Trees is kept low by putting maximum possible keys in a B-Tree node. Generally, a B-Tree node size is kept equal to the disk block size
Insertion
1) Initialize x as root.
2) While x is not leaf, do following
..a) Find the child of x that is going to to be traversed next. Let the child be y.
..b) If y is not full, change x to point to y.
..c) If y is full, split it and change x to point to one of the two parts of y. If k is smaller than mid key in y, then set x as first part of y. Else second part of y. When we split y, we move a key from y to its parent x.
3) The loop in step 2 stops when x is leaf. x must have space for 1 extra key as we have been splitting all nodes in advance. So simply insert k to x.
Deletion:
We sketch how deletion works with various cases of deleting keys from a B-tree.
1. If the key k is in node x and x is a leaf, delete the key k from x.
2. If the key k is in node x and x is an internal node, do the following.
a) If the child y that precedes k in node x has at least t keys, then find the predecessor k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
b) If y has fewer than t keys, then, symmetrically, examine the child z that follows k in node x. If z has at least t keys, then find the successor k0 of k in the subtree rooted at z. Recursively delete k0, and replace k by k0 in x. (We can find k0 and delete it in a single downward pass.)
c) Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.
3. If the key k is not present in internal node x, determine the root x.c(i) of the appropriate subtree that must contain k, if k is in the tree at all. If x.c(i) has only t-1 keys, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least t keys. Then finish by recursing on the appropriate child of x.
a) If x.c(i) has only t-1 keys but has an immediate sibling with at least t keys, give x.c(i) an extra key by moving a key from x down into x.c(i), moving a key from x.c(i) ’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.c(i).
b) If x.c(i) and both of x.c(i)’s immediate siblings have t-1 keys, merge x.c(i) with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node
C++ implemntation of search and traverse:
#include<iostream>
using namespace std;
class BTreeNode
{
int *keys; // An array of keys
int t; // Minimum degree (defines the range for number of keys)
BTreeNode **C; // An array of child pointers
int n; // Current number of keys
bool leaf; // Is true when node is leaf. Otherwise false
public:
BTreeNode(int _t, bool _leaf); // Constructor
void traverse();
BTreeNode *search(int k); // returns NULL if k is not present.
friend class BTree;
};
class BTree
{
BTreeNode *root; // Pointer to root node
int t; // Minimum degree
public:
BTree(int _t)
{ root = NULL; t = _t; }
void traverse()
{ if (root != NULL) root->traverse(); }
BTreeNode* search(int k)
{ return (root == NULL)? NULL : root->search(k); }
};
BTreeNode::BTreeNode(int _t, bool _leaf)
{
t = _t; // Copy the given minimum degree and leaf property
leaf = _leaf;
keys = new int[2*t-1];
C = new BTreeNode *[2*t];
n = 0; // Initialize the number of keys as 0
}
void BTreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
BTreeNode *BTreeNode::search(int k)
{
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
C++ implemntation of insert and delete:
#include<iostream>
using namespace std;
class BTreeNode
{
int *keys; // An array of keys
int t; // Minimum degree (defines the range for number of keys)
BTreeNode **C; // An array of child pointers
int n; // Current number of keys
bool leaf; // Is true when node is leaf. Otherwise false
public:
BTreeNode(int _t, bool _leaf); // Constructor
void traverse();
BTreeNode *search(int k); // returns NULL if k is not present.
int findKey(int k);
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void remove(int k);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);
int getPred(int idx); // A function to get the predecessor of the key-
int getSucc(int idx);
void fill(int idx);
void borrowFromPrev(int idx);
void borrowFromNext(int idx);
void merge(int idx);
friend class BTree;
};
class BTree
{
BTreeNode *root; // Pointer to root node
int t; // Minimum degree
public:
BTree(int _t)
{
root = NULL;
t = _t;
}
void traverse()
{
if (root != NULL) root->traverse();
}
BTreeNode* search(int k)
{
return (root == NULL)? NULL : root->search(k);
}
void insert(int k);
void remove(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;
}
int BTreeNode::findKey(int k)
{
int idx=0;
while (idx<n && keys[idx] < k)
++idx;
return idx;
}
void BTreeNode::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 "<< k <<" is does not exist in the tree\n";
return;
}
bool flag = ( (idx==n)? true : false );
if (C[idx]->n < t)
fill(idx);
if (flag && idx > n)
C[idx-1]->remove(k);
else
C[idx]->remove(k);
}
return;
}
void BTreeNode::removeFromLeaf (int idx)
{
for (int i=idx+1; i<n; ++i)
keys[i-1] = keys[i];
n--;
return;
}
void BTreeNode::removeFromNonLeaf(int idx)
{
int k = keys[idx];
if (C[idx]->n >= t)
{
int pred = getPred(idx);
keys[idx] = pred;
C[idx]->remove(pred);
}
else if (C[idx+1]->n >= t)
{
int succ = getSucc(idx);
keys[idx] = succ;
C[idx+1]->remove(succ);
}
else
{
merge(idx);
C[idx]->remove(k);
}
return;
}
int BTreeNode::getPred(int idx)
{
BTreeNode *cur=C[idx];
while (!cur->leaf)
cur = cur->C[cur->n];
return cur->keys[cur->n-1];
}
int BTreeNode::getSucc(int idx)
{
BTreeNode *cur = C[idx+1];
while (!cur->leaf)
cur = cur->C[0];
return cur->keys[0];
}
void BTreeNode::fill(int idx)
{
if (idx!=0 && C[idx-1]->n>=t)
borrowFromPrev(idx);
else if (idx!=n && C[idx+1]->n>=t)
borrowFromNext(idx);
else
{
if (idx != n)
merge(idx);
else
merge(idx-1);
}
return;
}
void BTreeNode::borrowFromPrev(int idx)
{
BTreeNode *child=C[idx];
BTreeNode *sibling=C[idx-1];
for (int i=child->n-1; i>=0; --i)
child->keys[i+1] = child->keys[i];
if (!child->leaf)
{
for(int i=child->n; i>=0; --i)
child->C[i+1] = child->C[i];
}
child->keys[0] = keys[idx-1];
if (!leaf)
child->C[0] = sibling->C[sibling->n];
keys[idx-1] = sibling->keys[sibling->n-1];
child->n += 1;
sibling->n -= 1;
return;
}
void BTreeNode::borrowFromNext(int idx)
{
BTreeNode *child=C[idx];
BTreeNode *sibling=C[idx+1];
child->keys[(child->n)] = keys[idx];
if (!(child->leaf))
child->C[(child->n)+1] = sibling->C[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->C[i-1] = sibling->C[i];
}
child->n += 1;
sibling->n -= 1;
return;
}
void BTreeNode::merge(int idx)
{
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx+1];
child->keys[t-1] = keys[idx];
for (int i=0; i<sibling->n; ++i)
child->keys[i+t] = sibling->keys[i];
if (!child->leaf)
{
for(int i=0; i<=sibling->n; ++i)
child->C[i+t] = sibling->C[i];
}
for (int i=idx+1; i<n; ++i)
keys[i-1] = keys[i];
for (int i=idx+2; i<=n; ++i)
C[i-1] = C[i];
child->n += sibling->n+1;
n--;
delete(sibling);
return;
}
void BTree::insert(int k)
{
if (root == NULL)
{
root = new BTreeNode(t, true);
root->keys[0] = k; // Insert key
root->n = 1; // Update number of keys in root
}
else // If tree is not empty
{
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);
root = s;
}
else // If root is not full, call insertNonFull for root
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 // If this node is not leaf
{
while (i >= 0 && keys[i] > k)
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;
for (int j = n; j >= i+1; j--)
C[j+1] = C[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;
}
void BTreeNode::traverse()
{
int i;
for (i = 0; i < n; i++)
{
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
BTreeNode *BTreeNode::search(int k)
{
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
void BTree::remove(int k)
{
if (!root)
{
cout << "The tree is empty\n";
return;
}
root->remove(k);
if (root->n==0)
{
BTreeNode *tmp = root;
if (root->leaf)
root = NULL;
else
root = root->C[0];
delete tmp;
}
return;
}
int main()
{
BTree t(3); // A B-Tree with minium degree 3
t.insert(1);
t.insert(3);
t.insert(7);
t.insert(10);
t.insert(11);
t.insert(13);
t.insert(14);
t.insert(15);
t.insert(18);
t.insert(16);
t.insert(19);
t.insert(24);
t.insert(25);
t.insert(26);
t.insert(21);
t.insert(4);
t.insert(5);
t.insert(20);
t.insert(22);
t.insert(2);
t.insert(17);
t.insert(12);
t.insert(6);
cout << "Traversal of tree constructed is\n";
t.traverse();
cout << endl;
t.remove(6);
cout << "Traversal of tree after removing 6\n";
t.traverse();
cout << endl;
t.remove(13);
cout << "Traversal of tree after removing 13\n";
t.traverse();
cout << endl;
t.remove(7);
cout << "Traversal of tree after removing 7\n";
t.traverse();
cout << endl;
t.remove(4);
cout << "Traversal of tree after removing 4\n";
t.traverse();
cout << endl;
t.remove(2);
cout << "Traversal of tree after removing 2\n";
t.traverse();
cout << endl;
t.remove(16);
cout << "Traversal of tree after removing 16\n";
t.traverse();
cout << endl;
return 0;
}
Red Black Tree:
Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node follows following rules.
1) Every node has a color either red or black.
2) Root of tree is always black.
3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).
4) Every path from root to a NULL node has same number of black nodes.
Insert:
The algorithms has mainly two cases depending upon the color of uncle. If uncle is red, we do recoloring. If uncle is black, we do rotations and/or recoloring.
Color of a NULL node is considered as BLACK.
Let x be the newly inserted node.
1) Perform standard BST insertion and make the color of newly inserted nodes as RED.
2) Do following if color of x’s parent is not BLACK or x is not root.
….a) If x’s uncle is RED (Grand parent must have been black from property 4)
……..(i) Change color of parent and uncle as BLACK.
……..(ii) color of grand parent as RED.
……..(iii) Change x = x’s grandparent, repeat steps 2 and 3 for new x.
redBlackCase2
….b) If x’s uncle is BLACK, then there can be four configurations for x, x’s parent (p) and x’s grandparent (g) (This is similar to AVL Tree)
……..i) Left Left Case (p is left child of g and x is left child of p)
……..ii) Left Right Case (p is left child of g and x is right child of p)
……..iii) Right Right Case (Mirror of case a)
……..iv) Right Left Case (Mirror of case c)
3) If x is root, change color of x as BLACK (Black height of complete tree increases by 1).
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data; // for data part
char color; // for color property
struct node *left, *right, *parent;
};
void LeftRotate(struct node **root,struct node *x)
{
struct node *y = x->right;
x->right = y->left;
if (x->right != NULL)
x->right->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;
}
void rightRotate(struct node **root,struct node *y)
{
struct node *x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
x->parent =y->parent;
if (x->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;
}
void insertFixUp(struct node **root,struct node *z)
{
while (z != *root && z->parent->color == 'R')
{
struct node *y;
if (z->parent == z->parent->parent->left)
y = z->parent->parent->right;
else
y = z->parent->parent->left;
// If uncle is RED, do following
if (y->color == 'R')
{
y->color = 'B';
z->parent->color = 'B';
z->parent->parent->color = 'R';
z = z->parent->parent;
}
// Uncle is BLACK, there are four cases (LL, LR, RL and RR)
else
{
// Left-Left (LL) case, do following
if (z->parent == z->parent->parent->left &&
z == z->parent->left)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent->parent);
}
// Left-Right (LR) case, do following
if (z->parent == z->parent->parent->left &&
z == z->parent->right)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
LeftRotate(root,z->parent);
rightRotate(root,z->parent->parent);
}
// Right-Right (RR) case, do following
if (z->parent == z->parent->parent->right &&
z == z->parent->right)
{
char ch = z->parent->color ;
z->parent->color = z->parent->parent->color;
z->parent->parent->color = ch;
LeftRotate(root,z->parent->parent);
}
// Right-Left (RL) case, do following
if (z->parent == z->parent->parent->right &&
z == z->parent->left)
{
char ch = z->color ;
z->color = z->parent->parent->color;
z->parent->parent->color = ch;
rightRotate(root,z->parent);
LeftRotate(root,z->parent->parent);
}
}
}
(*root)->color = 'B'; //keep root always black
}
void insert(struct node **root, int data)
{
struct node *z = (struct node*)malloc(sizeof(struct node));
z->data = data;
z->left = z->right = z->parent = NULL;
if (*root == NULL)
{
z->color = 'B';
(*root) = z;
}
else
{
struct node *y = NULL;
struct node *x = (*root);
while (x != NULL)
{
y = x;
if (z->data < x->data)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (z->data > y->data)
y->right = z;
else
y->left = z;
z->color = 'R';
insertFixUp(root,z);
}
}
void inorder(struct node *root)
{
if (root == NULL)
return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main()
{
struct node *root = NULL;
insert(&root,5);
insert(&root,3);
insert(&root,7);
insert(&root,2);
insert(&root,4);
insert(&root,6);
insert(&root,8);
insert(&root,11);
printf("inorder Traversal Is : ");
inorder(root);
return 0;
}
Deletion Steps
Following are detailed steps for deletion.
1) Perform standard BST delete. When we perform standard delete operation in BST, we always end up deleting a node which is either leaf or has only one child (For an internal node, we copy the successor and then recursively call delete for successor, successor is always a leaf node or a node with one child). So we only need to handle cases where a node is leaf or has one child. Let v be the node deleted and u be the child that replaces v.
2) Simple Case: If either u or v is red, we mark the replaced child as black (No change in black height). Note that both u and v cannot be red as v is parent of u and two consecutive reds are not allowed in red-black tree.
3) If Both u and v are Black.
3.1) Color u as double black. Now our task reduces to convert this double black to single black. Note that If v is leaf, then u is NULL and color of NULL is considered as black. So the deletion of a black leaf also causes a double black.
3.2) Do following while the current node u is double black or it is not root. Let sibling of node be s.
….(a): If sibling s is black and at least one of sibling’s children is red, perform rotation(s). Let the red child of s be r. This case can be divided in four subcases depending upon positions of s and r.
…………..(i) Left Left Case (s is left child of its parent and r is left child of s or both children of s are red). This is mirror of right right case shown in below diagram.
…………..(ii) Left Right Case (s is left child of its parent and r is right child). This is mirror of right left case shown in below diagram.
…………..(iii) Right Right Case (s is right child of its parent and r is right child of s or both children of s are red)
…………..(iv) Right Left Case (s is right child of its parent and r is left child of s)
…..(b): If sibling is black and its both children are black, perform recoloring, and recur for the parent if parent is black.
In this case, if parent was red, then we didn’t need to recur for prent, we can simply make it black (red + double black = single black)
…..(c): If sibling is red, perform a rotation to move old sibling up, recolor the old sibling and parent. The new sibling is always black (See the below diagram). This mainly converts the tree to black sibling case (by rotation) and leads to case (a) or (b). This case can be divided in two subcases.
…………..(i) Left Case (s is left child of its parent). This is mirror of right right case shown in below diagram. We right rotate the parent p.
…………..(iii) Right Case (s is right child of its parent). We left rotate the parent p.
3.3) If u is root, make it single black and return (Black height of complete tree reduces by 1).
Thats it for Now..............
No comments:
Post a Comment