Unit: 6: Advanced Algorithms
Binary Search Tree
A Binary Search Tree (BST) is a type of binary tree data structure in which each
node contains a unique key and satisfies a specific ordering property:
• All nodes in the left subtree of a node contain values strictly less than the
node’s value.
• All nodes in the right subtree of a node contain values strictly greater than
the node’s value.
Lchilf<Root<Rchild
• The primary operations on a Binary Search Tree (BST) are Search, Insertion,
and Deletion, along with various Traversal methods. These operations have
an average time complexity of O(log n) in a balanced tree.
(1) Search: This operation finds a specific key within the tree. It starts
at the root and recursively or iteratively compares the target key
with the current node's value. If the target is less, it moves to the
left subtree; if greater, it moves to the right. The process stops
when the key is found or an empty (null) subtree is reached.
(2) Insertion: A new node is always inserted as a leaf node in its correct
position to maintain the BST property. The process involves
searching for the appropriate empty spot by comparing the new
value with existing nodes and moving left or right accordingly until
a Null pointer is found where the new node can be placed.
(3) Deletion: Removing a node is the most complex operation, involving
three cases:
• Node has no children (leaf node): Simply remove the node and
set its parent's pointer to NULL
• Node has one child: The node is removed, and its parent's
pointer is connected directly to the deleted node's single child.
• Node has two children: The node to be deleted is replaced by
its in-order [Link] successor/predecessor is then
deleted from its original position
• BSTs are widely used in database indexing, symbol tables, and in advanced
structures like AVL tree and Red-Black tree.
(2) Balanced Trees (AVL Tree and Red Black Trees)
(ii) Red- Black Trees
• A Red-Black Tree is a self-balancing binary search tree with a height
limit of O(logN), enabling efficient search, insertion, and deletion
operations in O(logN) time.
• Each node has an additional attribute: a color, which can be either
red or black.
• These colors are used to maintain balance during insertions and
deletions, ensuring efficient data retrieval and manipulation.
Properties of Red-Black Trees
A Red-Black Tree has the following properties:
1. Node Color: Each node is either red or black.
2. Root Property: The root of the tree is always black.
3. Red Node Property: Red nodes cannot have red children (Red nodes
cannot be adjacent).
4. Black Node Property: Every path from a node to its descendant leaves
must have the same number of black nodes.
5. Leaf Property: All leaves (NIL nodes) are black.
Basic Operations of Red-Black Trees
• Insertion
• Deletion
• Search
(1) Insertion Operation:
Insertion operation of a Red-Black tree follows the same insertion
algorithm of a binary search tree. The elements are inserted following
the binary search property and as an addition, the nodes are color
coded as red and black to balance the tree according to the red-black
tree properties.
(2) Deletion Operation:
he deletion operation on red black tree must be performed in such a way
that it must restore all the properties of a binary search tree and a red
black tree
Delete nodes 4, 5, 3 from the tree. Fig. After Deletion
(3) Search operation
The search operation in red-black tree follows the same algorithm as that of
a binary search tree. The tree is traversed and each node is compared with
the key element to be searched; if found it returns a successful search.
Otherwise, it returns an unsuccessful search.
Rotations
B RIGHT-ROTATE(A) A
A LEFT-ROTATE(B) B
g a
a b b g
Rotations maintain the inorder ordering of keys:
• a a, b b, c g a A b B c.
A rotation can be performed in O(1) time.
L10.18
Case 2
C LEFT-ROTATE(A) C
y y
A B
x B x A
Transform to Case 3.
L10.28
Case 3
C
RIGHT-ROTATE(C)
y B
B
A C
x A
Done! No more
violations of RB
property 3 are
possible.
L10.29
Rabin-Karp Algorithm for Pattern Searching
Given two strings text (the text) and pattern (the pattern), consisting of
lowercase English alphabets, find all 0-based starting indices where pattern
occurs as a substring in text.
Examples:
Input: text = "geeksforgeeks", pattern = "geeks"
Output: [0, 8]
Explanation: The string "geeks" occurs at index 0 and 8 in text.
Input: text = "aabaacaadaabaaba", pattern = "aaba"
Output: [0, 9, 12]
Like the Naive Algorithm, the Rabin-Karp algorithm also check every
substring. But unlike the Naive algorithm, the Rabin Karp algorithm matches
the hash value of the pattern with the hash value of the current substring of
text. So Rabin Karp algorithm has the following steps:
Rabin-Karp Steps
1. Calculate Pattern Hash: Compute the hash of the pattern and the first
substring (window) of the text.
2. Slide Window: Move through the text, updating the hash using the
rolling hash technique.
3. Compare Hashes: If the hash of the pattern equals the text window's
hash, perform a character-by-character comparison (to handle
potential hash collisions).
4. Match Found: If the character-by-character check passes, add the
index to the result list.
• Compute the hash of the pattern
• Compare pattern's hash with the hashes of all substrings (of same
length as pattern) of the text. If the hashes match, we do a character-
by-character check to confirm (to avoid errors due to hash collisions).
(A) Calculating Hash Value :
Step 1: Assign modulus and a base value
The leftmost character will have rank 1 and the rightmost ranks
10. Also, use base b = 10
(Take a=1, b=2, c=3 ….z=26 values)
Step 2: Calculate the Hash Value of Pattern
Formula for initial hash: hash(P) = (P[0] * d^(m-1) + P[1] * d^(m-2) + ...
+ P[m-1] * d^0) mod q, where m is the pattern length.
(B) Calculate First Text Substring Hash: Compute the hash value for the
first substring of the text that has the same length as the pattern.
(C Update Hash Efficiently (Rolling Hash): The hash for the next window
is calculated from the previous one in O(1) time.
Formula for next hash: new_hash = (d * (old_hash - text[old_index] * h)
+ text[new_index]) mod q, where h = d^(m-1) mod q
============================================