Algorithms
1. AVL Tree
Theory:
An AVL tree is a height-balanced binary search tree. To maintain efficiency, the
height difference (balance factor) between the left and right subtrees of any node
must be -1,0,1.
Algorithm & Steps:
1. Calculate Balance Factor: Balance Factor= Height(left subtree) - Height(right
subtree)
2. Rotations: If a node becomes unbalanced (factor is 2 or -2) after insertion,
perform rotations:
LL (Left-Left): Single rotation for insertion in the left subtree of the left
child.
RR (Right-Right): Single rotation for insertion in the right subtree of the
right child.
LR (Left-Right): Double rotation (Left then Right).
RL (Right-Left): Double rotation (Right then Left).
Program (Algorithm Logic for Rotation):
The sources provide algorithmic steps for rotations rather than full C code:
Algorithm Left_To_Left_Rotation(Pptr)
Aptr = Pptr->Left
Pptr->Left = Aptr->Right
Aptr->Right = Pptr
Compute heights for Pptr and Aptr
Pptr = Aptr
Algorithms 1
return Pptr
End
Applications:
Used for searching operations where time complexity must be maintained at
O(log n).
2. Red-Black Tree
Theory:
A self-balancing binary search tree where every node is colored either Red or
Black. Properties include: root is always black, children of a red node must be
black (no consecutive reds), and every path from a node to its descendant NULL
nodes has the same number of black nodes,.
Algorithm (Insertion):
1. Insert the new node as Red.
2. If parent is Black, exit.
3. If parent is Red, check the uncle's color:
Recolor: If uncle is Red, change parent and uncle to Black, and
grandparent to Red.
Rotation: If uncle is Black (or NULL), perform suitable rotation and recolor.
Applications:
Used to implement efficient symbol tables and memory managers where
insertion and deletion frequency is high (inferred from context of balanced
trees).
3. Tries (Standard & Compressed)
Theory:
A tree-like structure for storing strings where nodes represent an alphabet. It
allows for efficient information retrieval with time complexity $O(M)$ where $M$
is key length.
Compressed Trie: Compresses chains of redundant nodes to save space.
Algorithms 2
Suffix Trie: Compressed trie of all suffixes of a string.
Program (Struct Definition):
#define NR 27 // 26 letters + blank
typedef struct trie_node {
bool NotLeaf;
struct trie_node *children[NR];
char word;
} trie_node;
// Operations: Insertion, Deletion, Searching, Traversing
Applications:
Spell checking.
Data compression.
Pattern matching and finding longest palindromes.
4. Single Linked List (Array & Linked Implementation)
Theory:
A linear data structure where elements (nodes) contain data and a pointer to the
next node,.
Algorithm (Linked List Representation):
Insertion: Create a new node. If inserting at the beginning, new node points to
head, and head becomes new node. If at end, traverse to the last node and
link it to the new node.
Deletion: Adjust pointers to bypass the node to be deleted and free its
memory.
Program (Linked List Struct):
struct node {
int key;
int value;
struct node *next;
Algorithms 3
};
struct node *head, *tail;
// Operations: isEmpty(), size(), insert(), find(), erase()
Applications:
Implementing Dictionaries.
Used in separate chaining for Hash Tables.
5. Queue (Array & Linked List)
Theory:
A linear structure following FIFO (First In First Out).
Array: Uses indices front and rear .
Linked List: Nodes connected linearly; insertions at rear, deletions from front.
Program (Array Implementation Logic):
Based on BFS implementation details:
int queue, front = -1, rear = -1;
void InsertQueue(int V) {
// Increment rear and add V to queue[rear]
}
int dequeue() {
// Return queue[front] and increment front
}
Applications:
Breadth First Search (BFS) graph traversal.
Managing tasks in operating systems (inferred).
6. Heap Sort
Algorithms 4
Theory:
A comparison-based sort using a Binary Heap (Max Heap or Min Heap). A Max
Heap is a complete binary tree where every parent is greater than its children,.
Algorithm:
1. Build Heap: Transform input array into a heap.
2. Swap & Heapify: Swap the root (largest) with the last element. Reduce heap
size by 1. Heapify the root to maintain heap property. Repeat until heap is
empty.
Program (C Routine):
void heapify(int a[], int i, int n) {
int child, tmp;
for (tmp = a[i]; i * 2 < n; i = child) {
child = i * 2;
if ((child != n) && (a[child + 1] > a[child]))
child++;
if (tmp < a[child])
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
void heapsort(int a[], int n) {
int i, tmp;
for (i = n / 2; i > 0; i--)
heapify(a, i, n);
for (i = n; i >= 2; i--) {
tmp = a[i]; a[i] = a; a = tmp; // Swap
heapify(a, 1, i - 1);
}
Algorithms 5
}
// Note: Source code adapted from
Applications:
Efficient sorting with $O(n \log n)$ time complexity.
7. Merge Sort
Theory:
An external sorting technique based on the Divide and Conquer strategy. It divides
the array into halves, sorts them recursively, and merges them.
Algorithm:
1. Divide: Split array into two subarrays (A1, A2).
2. Recursion: Recursively sort A1 and A2.
3. Conquer: Merge sorted A1 and A2 into a single sorted sequence.
Program:
void mergeSort(int lo, int hi) {
if (lo < hi) {
int m = (lo + hi) / 2;
mergeSort(lo, m);
mergeSort(m + 1, hi);
merge(lo, m, hi);
}
}
// Merge function logic involves comparing elements of two subarrays
// and placing them into a temporary array.
Applications:
External sorting where data does not fit into RAM (e.g., hard drive storage).
8. KMP (Knuth-Morris-Pratt) Algorithm
Algorithms 6
Theory:
A linear time string matching algorithm that avoids recomputing matches by
utilizing a precomputed "Longest Prefix Suffix" (LPS) array.
Algorithm:
1. Preprocessing: Compute LPS array for the pattern. LPS[i] stores the length of
the longest proper prefix of pattern[0...i] that is also a suffix of pattern[0...i] .
2. Searching: Compare Pattern and Text characters. On mismatch, use LPS
value to shift the pattern index without backtracking the text index.
Applications:
Exact matching in linear time O(n+m).
9. Boyer-Moore Algorithm
Theory:
Scans the pattern from right to left against the text. It uses two heuristics to skip
unnecessary comparisons: Bad Character and Good Suffix.
Algorithm:
1. Align pattern with text. Compare from rightmost character.
2. Mismatch Case:
If the mismatched character in text exists in the pattern, shift pattern to
align it (Bad Character Heuristic).
If not, shift pattern completely past the mismatch.
3. Use Good Suffix heuristic to shift based on matched suffixes.
Applications:
Most efficient string-matching algorithm when the alphabet is moderately
sized and the pattern is relatively long.
10. Skip List
Theory:
A probabilistic data structure storing a sorted list of items with a hierarchy of
linked lists ("express lanes") that connect increasingly sparse subsequences.
Algorithms 7
Algorithm:
Searching: Start at the top layer. Move horizontally until the next node is
greater than the target, then move down to the next layer. Repeat until the
bottom layer.
Insertion: Search for the position. Insert node. Probabilistically determine how
many layers upwards the new node should occupy.
Program (Struct):
struct skipnode {
typedef const pair<K, T> key_pair; // Template notion from source
key_pair element;
// Pointers to next nodes in different levels
};
Note: Source provides a C++ style struct definition.
Applications:
Distributed applications (network connections).
Highly scalable concurrent priority queues.
11. Dictionaries
Theory:
A collection of pairs $\langle key, value \rangle$. Keys are used to search for
values. Can be Unique (distinct keys) or Duplicate.
Algorithm:
Linear Search (Array): Compare key sequentially with every element.
Complexity O(n).
Binary Search (Array): Used on sorted arrays. Compare key with middle
element. Adjust search range to left or right half. Complexity O(log n),.
Program (Binary Search Logic):
Algorithms 8
// Based on
while (low <= high) {
mid = (low + high) / 2;
if (key == A[mid]) { flag = 1; break; }
else if (key < A[mid]) high = mid - 1;
else low = mid + 1;
}
Applications:
Unique Dictionary: Student information (Roll No as key).
Duplicate Dictionary: Compiler Symbol Tables (variable names as keys,
type/scope as values).
12. Splay Trees
Theory:
A Splay Tree is a self-adjusting Binary Search Tree (BST). In a Splay Tree, the
most recently accessed element is moved to the root position. This reorganization
ensures that frequently accessed elements are closer to the root, allowing for
quicker future operations.
Rotations:
Splaying involves a series of rotations to move a node to the root.
Zig / Zag Rotation: Single rotations used when the node is a child of the root
(Zig for left child, Zag for right child).
Zig-Zig / Zag-Zag Rotation: Double rotations used when the node and its
parent are both left children or both right children.
Zig-Zag / Zag-Zig Rotation: A sequence of rotations used when the node is a
right child of a left parent (or vice versa).
Algorithm & Theoretical Steps:
Insertion Operation:
Algorithms 9
1. Check Empty: If the tree is empty, insert the new node as the root and
exit.
2. BST Insertion: If the tree is not empty, insert the new node as a leaf node
using standard Binary Search Tree logic.
3. Splay: After insertion, perform splaying operations (rotations) to bring the
newly inserted node to the root position.
Deletion Operation:
1. Splay to Root: Search for the node to be deleted and splay it to the root.
2. Delete: Remove the node from the root position.
3. Join: Join the remaining subtrees using Binary Search Tree logic.
Applications:
Used in scenarios requiring fast access to recently used data (e.g., caches),
as the "splay" operation moves these elements to the root.
13. Standard Tries
Theory:
A Trie (or retrieval tree) is a tree-like data structure used for efficient information
retrieval. It stores an entire alphabet in its nodes, and strings are retrieved by
traversing down a branch. The time complexity for searching is $O(M)$, where
$M$ is the maximum string length (key length).
Each node has multiple branches representing possible characters.
The last node of a key is marked as an "end of word" node.
Algorithm & Theoretical Steps:
Structure: Each node contains a boolean to mark a leaf (end of word) and an
array of pointers to children nodes (e.g., size 26 for English alphabet).
Insertion:
1. Start at the root node.
2. Get the index of the first character of the input string (e.g., 'a' = 0).
Algorithms 10
3. Check if the corresponding child pointer exists. If not, create a new node.
4. Move to the child node and repeat for the next character in the string.
5. Once the end of the string is reached, mark the current node as a leaf
node (or end of word).
Deletion:
1. If the key is not found, do not modify the trie.
2. If the key is a unique suffix (no other key shares this branch path), delete
all nodes from the root to the leaf of the key.
3. If the key is a prefix of another key, simply unmark the "leaf node" status.
4. If the key shares a prefix with others but branches off, delete only the
unique nodes corresponding to that key.
Applications:
Spell checking.
Data compression.
Storing and querying XML documents.
14. Compressed Tries
Theory:
Standard Tries can be space-inefficient ($O(n)$ space) due to redundant nodes.
Compressed Tries overcome this by compressing chains of nodes that have only
one child into a single node.
Algorithm & Theoretical Steps:
Construction:
1. Identify chains of redundant nodes in a Standard Trie (nodes with single
children).
2. Collapse these chains into single nodes that represent a sequence of
characters rather than a single character.
3. The structure serves as an auxiliary index, often storing indices to an array
of strings rather than the strings themselves to save space ($O(S)$ space
Algorithms 11
where $S$ is the number of strings).
Operations: Insertion and deletion logic follows the Standard Trie but must
handle splitting or merging compressed nodes when new keys break existing
patterns (e.g., inserting "bbaabb" into a trie that already has "bab").
Applications:
Used to optimize space requirements while maintaining the fast retrieval
speeds of standard tries.
15. Suffix Tries (Suffix Trees)
Theory:
A Suffix Trie (often referred to as a Suffix Tree in the sources) is a Compressed
Trie containing all the suffixes of a given string $X$. It is a powerful structure for
solving string-related problems.
Algorithm & Theoretical Steps:
1. Identify Suffixes: Generate all possible suffixes of the given string.
Example: For "minimize", suffixes are "e", "ze", "ize", ..., "minimize".
2. Build Trie: Insert all these suffixes into a standard trie structure.
3. Compress: Apply compression logic to collapse non-branching paths into
single edges/nodes.
4. Representation: The tree is often represented using numbers (indices)
pointing to the original string to save space.
Applications:
Pattern matching.
Finding distinct substrings in a given string.
Finding the longest palindrome in a string.
Algorithms 12