0% found this document useful (0 votes)

10 views118 pages

Advanced Data Structures: BST & AVL Trees

The document discusses advanced data structures, focusing on Binary Search Trees (BST) and AVL Trees, highlighting their properties, advantages, disadvantages, and operations. It explains how AVL Trees maintain balance through rotations to ensure efficient performance for search, insertion, and deletion operations. Additionally, it outlines the applications of these trees, particularly in scenarios requiring efficient data organization and retrieval.

Uploaded by

Farhan Mushtaque

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

10 views118 pages

Advanced Data Structures: BST & AVL Trees

Uploaded by

Farhan Mushtaque

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY

Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024

Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Unit – 1
Advance Search Tree
Binary Search Tree
A Binary Search Tree (BST) is a hierarchical data structure that organizes
elements in a specific order to facilitate efficient searching, insertion, and
deletion operations.
Key Properties:
• Binary Tree Structure: Each node in a BST can have at most two
children: a left child and a right child.
• Ordered Elements: For any given node:
o All values in its left subtree are less than the node's value.
o All values in its right subtree are greater than the node's value.
• Recursive Property: Both the left and right subtrees must also be valid
BSTs.
Advantages:
• Efficient Searching: The ordered structure allows for efficient
searching, similar to binary search on a sorted array, achieving an
average time complexity of O(log n) for a balanced tree.
• Dynamic Operations: Insertion and deletion of elements can be
performed efficiently while maintaining the sorted order.
• Ordered Traversal: In-order traversal of a BST yields elements in
sorted order.
Disadvantages:
• Unbalanced Trees: If elements are inserted in a sorted or nearly sorted
order, the BST can become unbalanced, degenerating into a linked list-

Prepared By – Ms. Bindiya Sahu

CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

like structure. In this worst-case scenario, operations can have a time

complexity of O(n).
• Memory Overhead: BSTs require additional memory to store pointers
to child nodes compared to simpler data structures like arrays.
Operations
• Search: Start at the root, compare the target value with the current
node's value. If the target is smaller, move to the left child; if larger,
move to the right child. Repeat until the value is found or a null node is
reached.
• Insertion: Find the appropriate position for the new element by
following the search logic. Once a null pointer is encountered, insert
the new node at that position.
• Deletion: Deleting a node can be more complex, involving different
cases depending on whether the node has zero, one, or two children,
often requiring finding a successor or predecessor to maintain the BST
property.

Applications:
BSTs are used in various applications requiring efficient data organization and
retrieval, such as: Database indexing, Implementing dictionaries and sets,
Maintaining sorted data streams, and Implementing priority queues (though
heaps are often preferred for this).

Self-Balancing BSTs:
To mitigate the issue of unbalanced trees, self-balancing BSTs like AVL trees
and Red-Black trees automatically adjust their structure during insertions and
deletions to maintain a logarithmic height, ensuring O(log n) time complexity
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

for operations even in the worst case.

AVL Tree
An AVL tree is a self-balancing binary search tree, which is a key concept
within advanced data structures. It is named after its inventors, Adelson-
Velsky and Landis. The primary characteristic of an AVL tree is that for every
node, the height difference between its left and right subtrees (known as the
balance factor) must be at most 1. This balance factor can be -1, 0, or 1.

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the
difference between heights of left and right subtrees for any node cannot be
more than one.
Balance Factor = left subtree height - right subtree height
For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1
Example of an AVL Tree:
The balance factors for different nodes are: 12 : +1, 8 : +1, 18 : +1, 5 : +1, 11
: 0, 17 : 0 and 4 : 0. Since all differences are lies between -1 to +1, so the tree
is an AVL tree.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Example of a BST which is not an AVL Tree:

The Below Tree is not an AVL Tree as the balance factor for nodes 8,
4 and 7 is more than 1.

Important Points about AVL Tree:

• Use Cases: AVL Trees are particularly useful when you need frequent
and efficient lookups, like in database indexing, memory-intensive
applications, or where predictable time complexity is crucial.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Drawbacks Compared to Other Trees: Although faster in lookups

than Red-Black Trees, AVL Trees might incur slightly more overhead
on insertions and deletions due to stricter balancing requirements. As a
result, Red-Black Trees are more common in standard libraries
like TreeMap or TreeSet in Java or map in C++ STL.
• In-order Traversal: An in-order traversal of an AVL Tree still gives
you elements in sorted order, just like any Binary Search Tree.

Operations on an AVL Tree:

• Searching : It is same as normal Binary Search Tree (BST) as an AVL
Tree is always a BST. So we can use the same implementation as BST.
The advantage here is time complexity is O(log n)
• Insertion : It does rotations along with normal BST insertion to make
sure that the balance factor of the impacted nodes is less than or equal
to 1 after insertion
• Deletion : It also does rotations along with normal BST deletion to
make sure that the balance factor of the impacted nodes is less than or
equal to 1 after deletion.

Key Features and Concepts:

• Self-Balancing Property:
Unlike a standard binary search tree (BST) which can become skewed and
degrade to O(n) time complexity in worst-case scenarios, AVL trees maintain
balance to ensure O(log n) time complexity for search, insertion, and deletion
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

operations.
• Balance Factor:
Each node in an AVL tree stores its balance factor, which is calculated
as height(left_subtree) - height(right_subtree).
• Rotations:
When an insertion or deletion operation causes a node's balance factor to fall
outside the allowed range of -1, 0, or 1, the tree performs rotations to restore
balance. There are four types of rotations:
• Single Rotations:
• Left Rotation (LL): Used when a node becomes left-
heavy due to an insertion in the left subtree of its left child.
• Right Rotation (RR): Used when a node becomes right-
heavy due to an insertion in the right subtree of its right
child.
• Double Rotations:
• Left-Right Rotation (LR): Used when a node becomes
left-heavy due to an insertion in the right subtree of its left
child. This involves a left rotation on the child, followed
by a right rotation on the parent.
• Right-Left Rotation (RL): Used when a node becomes
right-heavy due to an insertion in the left subtree of its
right child. This involves a right rotation on the child,
followed by a left rotation on the parent.
Rotating the subtrees (Used in Insertion and Deletion)
An AVL tree may rotate in one of the following four ways to keep itself
balanced while making sure that the BST properties are maintained.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

1. Left-Left Rotation:
• Occurs when a node is inserted into the left subtree of the left child,
causing the balance factor to become more than +1.
• Fix: Perform a single right rotation.

2. Right-Right Rotation:
• Occurs when a node is inserted into the right subtree of the right child,
making the balance factor less than -1.
Fix: Perform a single left rotation.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

3. Left-Right Rotation:
• Occurs when a node is inserted into the right subtree of the left child,
which disturbs the balance factor of an ancestor node, making it left-
heavy.
• Fix: Perform a left rotation on the left child, followed by a right rotation
on the node.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

4. Right-Left
Rotation:
• Occurs
when a node is
inserted into
the left subtree of the right child, which disturbs the balance factor of
an ancestor node, making it right-heavy.
• Fix: Perform a right rotation on the right child, followed by a left
rotation on the node.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Applications of AVL Tree:

1. AVL Tree is used as a first example self balancing BST in teaching
DSA as it is easier to understand and implement compared to Red Black
2. Applications, where insertions and deletions are less common but
frequent data lookups along with other operations of BST like sorted
traversal, floor, ceil, min and max.
3. Red Black tree is more commonly implemented in language libraries
like map in C++, set in C++, TreeMap in Java and TreeSet in Java.
4. AVL Trees can be used in a real time environment where predictable
and consistent performance is required.
Advantages of AVL Tree:
1. AVL trees can self-balance themselves and therefore provides time
complexity as O(log n) for search, insert and delete.
2. As it is a balanced BST, so items can be traversed in sorted order.
3. Since the balancing rules are strict compared to Red Black Tree, AVL
trees in general have relatively less height and hence the search is faster.
4. AVL tree is relatively less complex to understand and implement
compared to Red Black Trees.
Disadvantages of AVL Tree:
1. It is difficult to implement compared to normal BST.
2. Less used compared to Red-Black trees. Due to its rather strict balance.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

3. AVL trees provide complicated insertion and removal operations as

more rotations are performed.

Why AVL Trees are Advanced:

AVL trees are considered an advanced data structure due to their self-
balancing mechanism. This mechanism adds complexity to the
implementation of insertion and deletion operations compared to a basic BST,
as it requires careful tracking of balance factors and the application of
rotations to maintain the tree's height-balanced property. This ensures optimal
performance even in scenarios that would lead to worst-case behavior in an
unbalanced BST.
AVL Insert Node Implementation
This code is based on the BST implementation on the previous page, for
inserting nodes.
There is only one new attribute for each node in the AVL tree compared to
the BST, and that is the height, but there are many new functions and extra
code lines needed for the AVL Tree implementation because of how the AVL
Tree rebalances itself.
The implementation below builds an AVL tree based on a list of characters,
to create the AVL Tree in the simulation above. The last node to be inserted
'F', also triggers a right rotation, just like in the simulation above.
Example
class TreeNode:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

[Link] = 1

def getHeight(node):
if not node:
return 0
return [Link]

def getBalance(node):
if not node:
return 0
return getHeight([Link]) - getHeight([Link])

def rightRotate(y):
print('Rotate right on node',[Link])
x = [Link]
T2 = [Link]
[Link] = y
[Link] = T2
[Link] = 1 + max(getHeight([Link]), getHeight([Link]))
[Link] = 1 + max(getHeight([Link]), getHeight([Link]))
return x

def leftRotate(x):
print('Rotate left on node',[Link])
y = [Link]
T2 = [Link]
[Link] = x
[Link] = T2
[Link] = 1 + max(getHeight([Link]), getHeight([Link]))
[Link] = 1 + max(getHeight([Link]), getHeight([Link]))
return y
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

def insert(node, data):

if not node:
return TreeNode(data)

if data < [Link]:

[Link] = insert([Link], data)
elif data > [Link]:
[Link] = insert([Link], data)

# Update the balance factor and balance the tree

[Link] = 1 + max(getHeight([Link]), getHeight([Link]))
balance = getBalance(node)

# Balancing the tree

# Left Left
if balance > 1 and getBalance([Link]) >= 0:
return rightRotate(node)

# Left Right
if balance > 1 and getBalance([Link]) < 0:
[Link] = leftRotate([Link])
return rightRotate(node)

# Right Right
if balance < -1 and getBalance([Link]) <= 0:
return leftRotate(node)

# Right Left
if balance < -1 and getBalance([Link]) > 0:
[Link] = rightRotate([Link])
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

return leftRotate(node)

return node

def inOrderTraversal(node):
if node is None:
return
inOrderTraversal([Link])
print([Link], end=", ")
inOrderTraversal([Link])

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
root = insert(root, letter)

inOrderTraversal(root)

AVL Delete Node Implementation

When deleting a node that is not a leaf node, the AVL Tree requires
the minValueNode() function to find a node's next node in the in-order
traversal. This is the same as when deleting a node in a Binary Search Tree,
as explained on the previous page.
To delete a node in an AVL Tree, the same code to restore balance is needed
as for the code to insert a node.
Example

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

def minValueNode(node):
current = node
while [Link] is not None:
current = [Link]
return current

def delete(node, data):

if not node:
return node

temp = minValueNode([Link])
[Link] = [Link]
[Link] = delete([Link], [Link])

if node is None:
return node

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

# Update the balance factor and balance the tree

[Link] = 1 + max(getHeight([Link]), getHeight([Link]))
balance = getBalance(node)

# Balancing the tree

# Left Left
if balance > 1 and getBalance([Link]) >= 0:
return rightRotate(node)

# Left Right
if balance > 1 and getBalance([Link]) < 0:
[Link] = leftRotate([Link])
return rightRotate(node)

# Right Right
if balance < -1 and getBalance([Link]) <= 0:
return leftRotate(node)

# Right Left
if balance < -1 and getBalance([Link]) > 0:
[Link] = rightRotate([Link])
return leftRotate(node)

return node

Time Complexity for AVL Trees

Take a look at the unbalanced Binary Search Tree below. Searching for "M"
means that all nodes except 1 must be compared. But searching for "M" in the
AVL Tree below only requires us to visit 4 nodes.
So in worst case, algorithms like search, insert, and delete must run through
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

the whole height of the tree. This means that keeping the height (h) of the tree
low, like we do using AVL Trees, gives us a lower runtime.

See the comparison of the time complexities between Binary Search Trees and
AVL Trees below, and how the time complexities relate to the height (h) of
the tree, and the number of nodes (n) in the tree.
• The BST is not self-balancing. This means that a BST can be very
unbalanced, almost like a long chain, where the height is nearly the
same as the number of nodes. This makes operations like searching,
deleting and inserting nodes slow, with time complexity O(h)=O(n).
• The AVL Tree however is self-balancing. That means that the height
of the tree is kept to a minimum so that operations like searching,
deleting and inserting nodes are much faster, with time
complexity O(h)=O(logn).

RED-BLACK TREE
Red Black Trees are a type of balanced binary search tree that use a set of

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

rules to maintain balance, ensuring logarithmic time complexity for

operations like insertion, deletion, and searching, regardless of the initial
shape of the tree. Red Black Trees are self-balancing, using a simple color-
coding scheme to adjust the tree after each modification.

A Red-Black Tree is a self-balancing binary search tree where each node has
an additional attribute: a color, which can be either red or black. The primary
objective of these trees is to maintain balance during insertions and deletions,
ensuring efficient data retrieval and manipulation.
Properties of Red-Black Trees
A Red-Black Tree have 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 Property: Red nodes cannot have red children (no two consecutive
red nodes on any path).
4. Black Property: Every path from a node to its descendant null nodes
(leaves) has the same number of black nodes.
5. Leaf Property: All leaves (NIL nodes) are black.
These properties ensure that the longest path from the root to any leaf is no
more than twice as long as the shortest path, maintaining the tree's balance
and efficient performance.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Example of Red-Black Tree:

The Correct Red-Black Tree in above image ensures that every path from the
root to a leaf node has the same number of black nodes. In this case, there is
one (excluding the root node).
The Incorrect Red Black Tree does not follow the red-black properties as two
red nodes are adjacent to each other. Another problem is that one of the paths
to a leaf node has zero black nodes, whereas the other two contain a black
node.

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc)
take O(h) time where h is the height of the BST. The cost of these operations
may become O(n) for a skewed Binary tree. If we make sure that the height of
the tree remains O(log n) after every insertion and deletion, then we can
guarantee an upper bound of O(log n) for all these operations. The height of a
Red-Black tree is always O(log n) where n is the number of nodes in the tree.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Sr. No. Algorithm Time Complexity

1. Search O(log n)
2. Insert O(log n)
3. Delete O(log n)

Basic Operations on Red-Black Tree:

The basic operations on a Red-Black Tree include:
1. Insertion
2. Search
3. Deletion
4. Rotation
1. Insertion
Inserting a new node in a Red-Black Tree involves a two-step process:
performing a standard binary search tree (BST) insertion, followed by fixing
any violations of Red-Black properties.
Insertion Steps
1. BST Insert: Insert the new node like in a standard BST.
2. Fix Violations:
• If the parent of the new node is black, no properties are violated.
• If the parent is red, the tree might violate the Red Property,
requiring fixes.
Fixing Violations During Insertion
After inserting the new node as a red node, we might encounter several cases
depending on the colors of the node's parent and uncle (the sibling of the
parent):
• Case 1: Uncle is Red: Recolor the parent and uncle to black, and the

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

grandparent to red. Then move up the tree to check for further

violations.
• Case 2: Uncle is Black:
o Sub-case 2.1: Node is a right child: Perform a left rotation on
the parent.
o Sub-case 2.2: Node is a left child: Perform a right rotation on
the grandparent and recolor appropriately.
2. Searching
Searching for a node in a Red-Black Tree is similar to searching in a
standard Binary Search Tree (BST). The search operation follows a
straightforward path from the root to a leaf, comparing the target value with
the current node's value and moving left or right accordingly.
Search Steps
1. Start at the Root: Begin the search at the root node.
2. Traverse the Tree:
• If the target value is equal to the current node's value, the node is
found.
• If the target value is less than the current node's value, move to
the left child.
• If the target value is greater than the current node's value, move
to the right child.
3. Repeat: Continue this process until the target value is found or a NIL
node is reached (indicating the value is not present in the tree).
3. Deletion
Deleting a node from a Red-Black Tree also involves a two-step process:
performing the BST deletion, followed by fixing any violations that arise.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Deletion Steps
1. BST Deletion: Remove the node using standard BST rules.
2. Fix Double Black:
• If a black node is deleted, a "double black" condition might arise,
which requires specific fixes.
Fixing Violations During Deletion
When a black node is deleted, we handle the double black issue based on the
sibling's color and the colors of its children:
• Case 1: Sibling is Red: Rotate the parent and recolor the sibling and
parent.
• Case 2: Sibling is Black:
o Sub-case 2.1: Sibling's children are black: Recolor the sibling
and propagate the double black upwards.
o Sub-case 2.2: At least one of the sibling's children is red:
o If the sibling's far child is red: Perform a rotation on the
parent and sibling, and recolor appropriately.
o If the sibling's near child is red: Rotate the sibling and
its child, then handle as above.
4. Rotation
Rotations are fundamental operations in maintaining the balanced structure of
a Red-Black Tree (RBT). They help to preserve the properties of the tree,
ensuring that the longest path from the root to any leaf is no more than twice
the length of the shortest path. Rotations come in two types: left
rotations and right rotations.
1. Left Rotation
A left rotation at node 𝑥x moves 𝑥x down to the left and its right child y up

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

to take 𝑥x’s place.

Before Rotation: After Left Rotation:

Left Rotation Steps:

1. Set y to be the right child of x.
2. Move y’s left subtree to x’s right subtree.
3. Update the parent of x and y.
4. Update x’s parent to point to y instead of x.
5. Set y’s left child to x.
6. Update x’s parent to y.
Pseudocode of Left Rotation:
// Utility function to perform left rotation
void leftRotate(Node* x)
{
Node* y = x->right;
x->right = y->left;
if (y->left != NIL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

else if (x == x->parent->left) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
2. Right Rotation
A right rotation at node 𝑥x moves 𝑥x down to the right and its left child y up
to take 𝑥x’s place.
Befor Right Rotation: After Right Rotation:

Right Rotation Steps:

1. Set y to be the left child of x.
2. Move y’s right subtree to x’s left subtree.
3. Update the parent of x and y.
4. Update x’s parent to point to y instead of x.
5. Set y’s right child to x.
6. Update x’s parent to y.
Pseudocode of Right Rotation:
// Utility function to perform right rotation
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

void rightRotate(Node* x)
{
Node* y = x->left;
x->left = y->right;
if (y->right != NIL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
else if (x == x->parent->right) {
x->parent->right = y;
}
else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
When to Perform Rotations?
Rotations in Red-Black Trees are typically performed during insertions and
deletions to maintain the properties of the tree. Below are the scenarios for
rotations:
1. Fixing Violations after Insertion
When a new node is inserted, it is always colored red. This can create

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

violations of Red-Black Tree properties, specifically:

• The root must be black.
• Red nodes cannot have red children.
Case Analysis for Fixing Insertions:
• Case 1: Recoloring and Propagating Upwards
o If the parent and uncle of the new node are both red, recolor the
parent and uncle to black, and the grandparent to red. Then,
recursively apply the fix-up to the grandparent.
• Case 2: Rotation and Recoloring
o If the new node’s uncle is black and the new node is the right
child of a left child (or vice versa), perform a rotation to move
the new node up and align it.
o If the new node’s uncle is black and the new node is the left child
of a left child (or right of a right), perform a rotation and recolor
the parent and grandparent to fix the violation.
2. Fixing Violations after Deletion
After deletion, the tree might need fixing to restore properties:
• When a black node is removed, or a red node is replaced by a black
node, a double-black situation can arise.
Case Analysis for Fixing Deletions:
• Case 1: Sibling is Red
o Recolor the sibling and the parent, and perform a rotation.
• Case 2: Sibling is Black with Black Children
o Recolor the sibling to red and move the problem up to the parent.
• Case 3: Sibling is Black with at least one Red Child
o Rotate and recolor to fix the double-black issue.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Implementation of Red-Black Tree:

#include <iostream>
using namespace std;
// Node structure for the Red-Black Tree
struct Node {
int data;
string color;
Node *left, *right, *parent;
Node(int data)
: data(data)
, color("RED")
, left(nullptr)
, right(nullptr)
, parent(nullptr)
{
}
};

// Red-Black Tree class

class RedBlackTree {
private:
Node* root;
Node* NIL;

// Utility function to perform left rotation

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

void leftRotate(Node* x)
{
Node* y = x->right;
x->right = y->left;
if (y->left != NIL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
else if (x == x->parent->left) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}

// Utility function to perform right rotation

void rightRotate(Node* x)
{
Node* y = x->left;
x->left = y->right;

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

if (y->right != NIL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
else if (x == x->parent->right) {
x->parent->right = y;
}
else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}

// Function to fix Red-Black Tree properties after

// insertion
void fixInsert(Node* k)
{
while (k != root && k->parent->color == "RED") {
if (k->parent == k->parent->parent->left) {
Node* u = k->parent->parent->right; // uncle
if (u->color == "RED") {
k->parent->color = "BLACK";

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

u->color = "BLACK";
k->parent->parent->color = "RED";
k = k->parent->parent;
}
else {
if (k == k->parent->right) {
k = k->parent;
leftRotate(k);
}
k->parent->color = "BLACK";
k->parent->parent->color = "RED";
rightRotate(k->parent->parent);
}
}
else {
Node* u = k->parent->parent->left; // uncle
if (u->color == "RED") {
k->parent->color = "BLACK";
u->color = "BLACK";
k->parent->parent->color = "RED";
k = k->parent->parent;
}
else {
if (k == k->parent->left) {
k = k->parent;
rightRotate(k);

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

}
k->parent->color = "BLACK";
k->parent->parent->color = "RED";
leftRotate(k->parent->parent);
}
}
}
root->color = "BLACK";
}

// Inorder traversal helper function

void inorderHelper(Node* node)
{
if (node != NIL) {
inorderHelper(node->left);
cout << node->data << " ";
inorderHelper(node->right);
}
}

// Search helper function

Node* searchHelper(Node* node, int data)
{
if (node == NIL || data == node->data) {
return node;
}

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

if (data < node->data) {

return searchHelper(node->left, data);
}
return searchHelper(node->right, data);
}

public:
// Constructor
RedBlackTree()
{
NIL = new Node(0);
NIL->color = "BLACK";
NIL->left = NIL->right = NIL;
root = NIL;
}

// Insert function
void insert(int data)
{
Node* new_node = new Node(data);
new_node->left = NIL;
new_node->right = NIL;

Node* parent = nullptr;

Node* current = root;

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

// BST insert
while (current != NIL) {
parent = current;
if (new_node->data < current->data) {
current = current->left;
}
else {
current = current->right;
}
}

new_node->parent = parent;

if (parent == nullptr) {
root = new_node;
}
else if (new_node->data < parent->data) {
parent->left = new_node;
}
else {
parent->right = new_node;
}

if (new_node->parent == nullptr) {
new_node->color = "BLACK";
return;

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

if (new_node->parent->parent == nullptr) {
return;
}

fixInsert(new_node);
}

// Inorder traversal
void inorder() { inorderHelper(root); }

// Search function
Node* search(int data)
{
return searchHelper(root, data);
}
};

int main()
{
RedBlackTree rbt;

// Inserting elements
[Link](10);
[Link](20);

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

[Link](30);
[Link](15);

// Inorder traversal
cout << "Inorder traversal:" << endl;
[Link](); // Output: 10 15 20 30

// Search for a node

cout << "\nSearch for 15: "
<< ([Link](15) != [Link](0))
<< endl; // Output: 1 (true)
cout << "Search for 25: "
<< ([Link](25) != [Link](0))
<< endl; // Output: 0 (false)

return 0;
}

Advantages of Red-Black Trees:

• Balanced: Red-Black Trees are self-balancing, meaning they
automatically maintain a balance between the heights of the left and
right subtrees. This ensures that search, insertion, and deletion
operations take O(log n) time in the worst case.
• Efficient search, insertion, and deletion: Due to their balanced
structure, Red-Black Trees offer efficient operations. Search, insertion,

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

and deletion all take O(log n) time in the worst case.

• Simple to implement: The rules for maintaining the Red-Black Tree
properties are relatively simple and straightforward to implement.
• Widely used: Red-Black Trees are a popular choice for implementing
various data structures, such as maps, sets, and priority queues.
Disadvantages of Red-Black Trees:
• More complex than other balanced trees: Compared to simpler
balanced trees like AVL trees, Red-Black Trees have more complex
insertion and deletion rules.
• Constant overhead: Maintaining the Red-Black Tree properties adds
a small overhead to every insertion and deletion operation.
• Not optimal for all use cases: While efficient for most operations,
Red-Black Trees might not be the best choice for applications where
frequent insertions and deletions are required, as the constant overhead
can become significant.

Applications of Red-Black Trees:

• Implementing maps and sets: Red-Black Trees are often used to
implement maps and sets, where efficient search, insertion, and deletion
are crucial.
• Priority queues: Red-Black Trees can be used to implement priority
queues, where elements are ordered based on their priority.
• File systems: Red-Black Trees are used in some file systems to manage
file and directory structures.
• In-memory databases: Red-Black Trees are sometimes used in in-
memory databases to store and retrieve data efficiently.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Graphics and game development: Red-Black Trees can be used in

graphics and game development for tasks like collision detection and
pathfinding.

SPLAY TREE
A splay tree is a self-adjusting binary search tree introduced by Sleator and
Tarjan in 1985. Its key idea is to move the most recently accessed or inserted
element to the root through a process called splaying, which uses tree
rotations.
• Working: Whenever an element is accessed (searched, inserted, or
deleted), the tree reorganizes so that element becomes the new root, and
other nodes move closer to the root.
• Time Complexity: All operations (search, insertion, deletion) take
O(log n) amortized time, though individual operations may take
longer.

A step-by-step explanation of the rotation operations:

• Zig Rotation: If a node has a right child, perform a right rotation to
bring it to the root. If it has a left child, perform a left rotation.
• Zig-Zig Rotation: If a node has a grandchild that is also its child's right
or left child, perform a double rotation to balance the tree. For example,
if the node has a right child and the right child has a left child, perform
a right-left rotation. If the node has a left child and the left child has a
right child, perform a left-right rotation.
• Note: The specific implementation details, including the exact rotations
used, may vary depending on the exact form of the splay tree.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Rotations in Splay Tree

• Zig Rotation
• Zag Rotation
• Zig - Zig Rotation
• Zag - Zag Rotation
• Zig - Zag Rotation
• Zag - Zig Rotation

1) Zig Rotation:
The Zig Rotation in splay trees operates in a manner similar to the single right
rotation in AVL Tree rotations. This rotation results in nodes moving one
position to the right from their current location.
For example:

2) Zag Rotation:
The Zag Rotation in splay trees operates in a similar fashion to the single left
rotation in AVL Tree rotations. During this rotation, nodes shift one position
to the left from their current location.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

For instance:

3) Zig-Zig Rotation:
The Zig-Zig Rotation in splay trees is a double zig rotation. This rotation
results in nodes shifting two positions to the right from their current location.

4) Zag-Zag Rotation:
In splay trees, the Zag-Zag Rotation is a double zag rotation. This rotation
causes nodes to move two positions to the left from their present position. For
example:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

5) Zig-Zag Rotation:
The Zig-Zag Rotation in splay trees is a combination of a zig rotation followed
by a zag rotation. As a result of this rotation, nodes shift one position to the
right and then one position to the left from their current location.

6) Zag-Zig Rotation:
The Zag-Zig Rotation in splay trees is a series of zag rotations followed by a
zig rotation. This results in nodes moving one position to the left, followed by
a shift one position to the right from their current location. The following
illustration offers a visual representation of this concept:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

IMPLEMENTATION
#include <iostream>
using namespace std;
struct Node {
int key;
Node *left, *right;
};
Node* newNode(int key) {
Node* node = new Node();
node->key = key;
node->left = node->right = nullptr;
return node;
}

Node* rightRotate(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
return y;
}
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

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

Node* splay(Node* root, int key) {

if (root == nullptr || root->key == key)
return root;

if (root->key > key) {

if (root->left == nullptr)
return root;
if (root->left->key > key) {
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
}
else if (root->left->key < key) {
root->left->right = splay(root->left->right, key);
if (root->left->right != nullptr)
root->left = leftRotate(root->left);
}
return (root->left == nullptr) ? root : rightRotate(root);
}

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

else {
if (root->right == nullptr)
return root;
if (root->right->key > key) {
root->right->left = splay(root->right->left, key);
if (root->right->left != nullptr)
root->right = rightRotate(root->right);
}
else if (root->right->key < key) {
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
return (root->right == nullptr) ? root : leftRotate(root);
}
}

Node* insert(Node* root, int key) {

if (root == nullptr)
return newNode(key);

root = splay(root, key);

if (root->key == key)
return root;

Node* node = newNode(key);

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

if (root->key > key) {

node->right = root;
node->left = root->left;
root->left = nullptr;
}
else {
node->left = root;
node->right = root->right;
root->right = nullptr;
}
return node;
}

void preOrder(Node* node) {

if (node != nullptr) {
cout << node->key << " ";
preOrder(node->left);
preOrder(node->right);
}
}

int main() {
Node* root = nullptr;
root = insert(root, 100);
root = insert(root, 50);
root = insert(root, 200);

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

root = insert(root, 40);

root = insert(root, 60);
cout << "Preorder traversal of the modified Splay tree:" << endl;
preOrder(root);
return 0;
}

Output
Preorder traversal of the modified Splay tree:

Applications of the splay tree:

• Caching: Splay trees can be used to implement cache memory
management, where the most frequently accessed items are moved to
the top of the tree for quicker access.
• Data Compression: Splay trees can be used to compress data by
identifying and encoding repeating patterns.
• Text Processing: Splay trees can be used in text processing
applications, such as spell-checkers, where words are stored in a splay
tree for quick searching and retrieval.
• Graph Algorithms: Splay trees can be used to implement graph
algorithms, such as finding the shortest path in a weighted graph.
• Online Gaming: Splay trees can be used in online gaming to store and
manage high scores, leaderboards, and player statistics.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Advantages:
o Frequently accessed elements remain near the root, making future
operations faster.
o Simple implementation compared to other balanced trees.
o Useful in applications like caching, data compression, and network
routing.
Disadvantages:
o Tree is not strictly balanced, so worst-case operations may be slow.
o Not suitable for systems requiring guaranteed worst-case
performance (e.g., real-time or safety-critical systems).
o Memory Usage is more.
o Complexity is high.
o Reorganization overhead.
Treap
Treap is a Balanced Binary Search Tree, but not guaranteed to have height as
O(Log n). The idea is to use Randomization and Binary Heap property to
maintain balance with high probability. The expected time complexity of
search, insert and delete is O(Log n).

A treap is an advanced data structure that merges a binary search tree and a
heap, storing nodes with both a search key and a random priority. It maintains
both the binary search tree property (keys are ordered) and the heap
property (priorities are ordered, typically max-heap), which results in a self-
balancing tree with an average O(log n) time complexity for most operations
like insertion, deletion, and searching.
How it Works

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

1. Node Structure: Each node in a treap holds a key (the data value) and
a randomly assigned priority.
2. Binary Search Tree Property: The keys are arranged such that all
keys in the left subtree of a node are smaller than the node's key, and
all keys in the right subtree are larger.
3. Heap Property: The priorities are arranged such that any node's
priority is greater than or equal to its children's priorities (for a max-
heap).
4. Randomization for Balance: The random priorities ensure that the
treap remains balanced on average. When a node is inserted or deleted,
the tree may undergo rotations to maintain both properties, effectively
moving nodes up or down by a random amount.

Key Properties and Advantages

• Self-Balancing: Treaps automatically balance themselves due to the
random priorities, preventing worst-case scenarios of unbalanced trees
that degrade performance.
• Average O(log n) Complexity: Insertion, deletion, and search
operations all have an average time complexity of O(log n).
• Versatility: Treaps can be adapted for various problems, serving as an
efficient alternative to other balanced trees like splay trees or segment
trees.
• Dynamic Operations: Beyond basic search, insert, and delete, treaps
can also implement split and join operations, which are fundamental
for more complex data manipulations.
Use Cases
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Dynamic Sets: Used for managing dynamic sets of ordered data

efficiently.
• Connectivity Problems: Can be applied to problems involving
network connectivity.
• Range Query Problems: Useful for answering queries about ranges of
data.
• Rope Data Structures: A modified version of a treap, known as an
implicit Cartesian tree, can function as a rope for efficient string
operations.
Operations
A treap provides the following operations:
• Insert (X,Y) in O(\log N): Adds a new node to the tree. One possible
variant is to pass only X and generate Y randomly inside the operation.
• Search (X) in O(\log N): Looks for a node with the specified key
value $X$ . The implementation is the same as for an ordinary binary
search tree.
• Erase (X) in O(\log N) : Looks for a node with the specified key
value $X$ and removes it from the tree.
• Build ( X_1 , ..., X_N) in O(N): Builds a tree from a list of values. This
can be done in linear time (assuming that $X_1, ..., X_N$ are sorted).
• Union ( T_1, T_2 ) in O(M \log (N/M)) : Merges two trees, assuming
that all the elements are different. It is possible to achieve the same
complexity if duplicate elements should be removed during merge.
• Intersect ( T_1 , T_2 ) in O(M \log (N/M)): Finds the intersection of
two trees (i.e. their common elements). We will not consider the
implementation of this operation here.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

SKIP LIST
A skip list is a probabilistic data structure that organizes elements in a sorted
list across multiple layers, offering efficient search, insertion, and deletion
operations with an average time complexity of O(log n). It serves as an
alternative to balanced binary search trees like AVL trees or red-black trees,
often favored for its simpler implementation and suitability for parallel
computing environments.
Structure:
• Multiple Layers:
A skip list consists of several sorted linked lists, stacked one upon another.
• Bottom Layer (Level 0):
This is a standard sorted linked list containing all elements of the data
structure.
• Higher Layers:
Each subsequent higher layer (Level 1, Level 2, etc.) contains a subset of the
elements from the layer below it. These higher layers act as "express lanes,"
allowing for faster traversal by skipping over elements present only in lower
layers.
• Randomized Level Assignment:
When a new element is inserted, its level (how many layers it will be included
in) is determined probabilistically, typically using a "coin-flipping"
mechanism. A random number is generated, and based on a predefined
probability, the element is promoted to higher levels. This ensures that, on
average, elements are distributed across levels in a way that facilitates
logarithmic time complexity.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Operations:
• Search:
Searching begins from the highest level and proceeds downwards. At each
level, the search moves horizontally until the next element is greater than the
target key, or the end of the list is reached. If the target is not found in the
current level, the search drops down to the next lower level, starting from the
node just before the point of descent.
• Insertion:
A new element's level is determined randomly. The element is then inserted
into the appropriate positions in all layers up to its assigned level, maintaining
sorted order and updating pointers.
• Deletion:
Similar to insertion, deletion involves locating the element in all relevant
layers and removing it by updating pointers.
Advantages:
• Logarithmic Time Complexity:
Offers average O(log n) time for search, insertion, and deletion, comparable
to balanced trees.
• Simpler Implementation:
Often considered easier to implement than complex balanced tree algorithms.
• Parallelism:
Well-suited for parallel computing environments, as insertions can be
performed in different parts of the list concurrently without requiring global
rebalancing.
Disadvantages:
• Probabilistic Guarantees:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

While average-case performance is excellent, worst-case scenarios, though

highly improbable, can lead to linear time complexity if the random level
assignments result in a poorly balanced structure.
• Space Overhead:
Requires more memory than a simple linked list due to the multiple layers and
pointers.

Representation of Skip List

A Skip List is represented as a series of linked lists, where each list is a level
of the Skip List. Each node in the Skip List contains a key and a value. The
key is used to sort the elements in the list, and the value is the data associated
with the key.
Each node also contains pointers to the next node in the same level, and
pointers to the next node in the level below. The top level of the Skip List
contains only one node, which is the head of the list. The head node contains
pointers to the first node in each level of the Skip List.

Types of Skip List

Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

There are more than one type of Skip Lists:

• Randomized Skip List: In a randomized skip list, the elements
promoted to higher levels are chosen randomly. This makes the
structure of the skip list unpredictable.
• Deterministic Skip List:In the deterministic skip list, the elements
promoted to higher levels are chosen based on a deterministic rule. This
makes the structure of the skip list predictable. For example, in a
deterministic skip list, every 2nd element is promoted to the next level.

Operations on Skip List

A Skip List supports the following operations:
• Search: Search for an element in the Skip List.
• Insert: Insert an element into the Skip List.
• Delete: Delete an element from the Skip List.
Implementing a Skip List
A Skip List can be implemented using a linked list data structure. Each node
in the Skip List contains a key, a value, and an array of pointers to the next
node in each level. The Skip List also contains a head node that points to the
first node in each level.

Algorithm to implement Skip List

• Create a Node structure, with key, value, and an array of pointers.
• Create a SkipList structure, with a head node and the level of the Skip
List.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Create a function to create a new node.

• Create a function to create a new Skip List.
• Create a function to generate a random level for a node.
• Create a function to insert a node into the Skip List.
• Create a function to display the Skip List.
• At last, create a main function to test the Skip List.

Example of Skip List

//C Program to implement Skip List
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define MAX_LEVEL 6
// Node structure
struct Node {
int key;
struct Node *forward[MAX_LEVEL];
};
// SkipList structure
struct SkipList {
struct Node *header;
int level;
};
// Create a node
struct Node* createNode(int key, int level) {

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

struct Node newNode = (struct Node)malloc(sizeof(struct Node));

newNode->key = key;
for (int i = 0; i < level; i++)
newNode->forward[i] = NULL;
return newNode;
}
// Create a SkipList
struct SkipList* createSkipList() {
struct SkipList *list = (struct SkipList*)malloc(sizeof(struct SkipList));
list->header = createNode(INT_MIN, MAX_LEVEL);
list->level = 0;
return list;
}
// Generate random level for node
int randomLevel() {
int level = 0;
while (rand() < RAND_MAX / 2 && level < MAX_LEVEL)
level++;
return level;
}
// Insert a node
void insertNode(struct SkipList *list, int key) {
struct Node *current = list->header;
struct Node *update[MAX_LEVEL];
for (int i = list->level; i >= 0; i--) {
while (current->forward[i] != NULL && current->forward[i]->key < key)

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

current = current->forward[i];
update[i] = current;
}
current = current->forward[0];
if (current == NULL || current->key != key) {
int rlevel = randomLevel();
if (rlevel > list->level) {
for (int i = list->level + 1; i <= rlevel; i++)
update[i] = list->header;
list->level = rlevel;
}
struct Node *newNode = createNode(key, rlevel);
for (int i = 0; i <= rlevel; i++) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
}
// Display the SkipList
void displayList(struct SkipList *list) {
printf("\nSkip List\n");
for (int i = 0; i <= list->level; i++) {
struct Node *node = list->header->forward[i];
printf("Level %d: ", i);
while (node != NULL) {
printf("%d ", node->key);

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

node = node->forward[i];
}
printf("\n");
}
}
int main() {
srand((unsigned)time(0));
struct SkipList *list = createSkipList();
insertNode(list, 3);
insertNode(list, 6);
insertNode(list, 7);
insertNode(list, 9);
insertNode(list, 12);
insertNode(list, 19);
insertNode(list, 17);
insertNode(list, 26);
insertNode(list, 21);
insertNode(list, 25);
displayList(list);
return 0;
}
Output
Skip List
Level 0: 3 6 7 9 12 17 19 21 25 26
Level 1: 6 9 12 17 21 26
Level 2: 9

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Search Operation in Skip List

The search operation in a Skip List is similar to a linked list. We start from
the top level and move to the next level if the key is greater than the current
node. We continue this process until we find the key or reach the bottom level.
If the key is found, we return the node; otherwise, we return NULL.
Algorithm
Following are steps to search for a key in a Skip List:
• Start from the top level of the Skip List.
• Move to the next level if the key is greater than the current node.
• Continue this process until we find the key or reach the bottom level.
• If the key is found, return the node; otherwise, return NULL.

Delete Operation in Skip List

The delete operation in a Skip List is similar to a linked list. We search for the
key to be deleted and update the pointers to remove the node from the list. The
delete operation is as follows:
Algorithm
• Search for the key to be deleted in the Skip List.
• Update the pointers to remove the node from the list.
• Repeat this process for all levels of the Skip List.

Time Complexity and Space Complexity of Skip List

• The time complexity of search, insert, and delete operations in a Skip
List is O(log n) on average.
• The time complexity of these operations is the same as that of a
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

balanced binary search tree.

• The space complexity of a Skip List is O(n).

Applications of Skip List

• Database Indexing: Skip Lists are used in databases to index data
efficiently.
• Search Engines: Skip Lists are also used in search engines to store and
retrieve web pages.
• Network Routing Algorithms: This data structure also used in
network routing algorithms to find the shortest path between two nodes.
Advantages of Skip List
• Efficient Operations: Skip Lists provide efficient search, insert, and
delete operations.
• Simple Implementation: Skip Lists are easy to implement compared
to other data structures like AVL trees and Red-Black trees.
• Space Efficiency: Skip Lists are space-efficient and require less
memory compared to other data structures.

Disadvantages of Skip List

• Complexity: Skip Lists are complex data structures compared to linked
lists.
• Randomness: The performance of Skip Lists depends on the
randomness of the levels.

Finger Search Tree

A finger search tree is a data structure that is designed to allow for efficient
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

search and access of data in a set or a sequence. It is a type of binary search

tree that uses a "finger" or a reference to a particular element in the tree to
quickly find and retrieve other elements. In this article, we will explore the
types, advantages, disadvantages, and implementation codewise of a finger
search tree data structure.

Types of Finger Search Tree:

There are several types of finger search trees, including the binary search
tree (BST), the red-black tree (RBT), and the AVL tree. Each type of finger
search tree has its own set of rules for inserting and deleting elements,
balancing the tree, and maintaining the finger reference.
• The BST is the simplest type of finger search tree, where each node has
at most two children - a left child and a right child. The finger reference
in a BST is a pointer to a node in the tree.
• The RBT is a more complex type of finger search tree that uses color-
coded nodes to balance the tree. The finger reference in an RBT is a
pointer to a node in the tree, and the color of the node is used to
determine how the tree is balanced.
• The AVL tree is a self-balancing type of finger search tree that uses a
height balance factor to maintain balance. The finger reference in an
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

AVL tree is a pointer to a node in the tree, and the height balance factor
is used to determine how the tree is balanced.

Implementation of Finger Search Tree:

Step 1: Define the basic building blocks of the finger tree, i.e., the nodes and
the annotations. A node can either be a leaf node or a tree node. A leaf node
contains a single element, whereas a tree node contains two subtrees and an
annotation that summarizes the information about the elements in those
subtrees.
Step 2: Define the finger tree data structure, which consists of a finger (i.e., a
pointer to the currently focused element) and the root node of the tree.
Step 3: Define the annotation functions that summarize the information about
the elements in a subtree.
Step 4: Define the split and insert functions for the finger tree. The split
function splits the tree at a given index and returns two new finger trees. The
insert function inserts a new element at a given index in the tree.
Step 5: Define the search function for the finger tree. The search function
searches for an element in the tree and returns its index if found, or None if
not found.
Implementation
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class Leaf {
public:
int value;
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Leaf(int val) : value(val) {}

};

class Node {
public:
Node* left;
Node* right;
int size;
Node(Node* l, Node* r, int s) : left(l), right(r), size(s) {}
};

class FingerTree {
public:
Node* root;
int finger;

FingerTree(Node* r = nullptr, int f = -1) : root(r), finger(f) {}

};

int search(FingerTree* tree, int value) {

if (tree == nullptr) {
return -1;
}
if (dynamic_cast<Leaf*>(tree->root) != nullptr) {
return (tree->root->value == value) ? 0 : -1;
} else if (value <= tree->root->left->size) {

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

int index = search(new FingerTree(tree->root->left), value);

return (index != -1) ? index : -1;
} else {
int index = search(new FingerTree(tree->root->right), value - tree->root-
>left->size);
return (index != -1) ? (index + tree->root->left->size) : -1;
}
}

FingerTree* insert(FingerTree* tree, int index, int value) {

if (tree == nullptr) {
return new FingerTree(new Leaf(value), value);
}
if (tree->root == nullptr) {
return new FingerTree(new Leaf(value), value);
}
if (dynamic_cast<Leaf*>(tree->root) != nullptr) {
if (index == 0) {
return new FingerTree(new Node(new Leaf(value), tree->root, 2),
value);
} else if (index == 1) {
return new FingerTree(new Node(tree->root, new Leaf(value), 2),
value);
} else {
throw std::out_of_range("Index out of bounds");
}

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

} else if (index <= tree->root->left->size) {

FingerTree* left = insert(new FingerTree(tree->root->left), index,
value);
int size = tree->root->size + 1;
if (size % 2 == 0) {
return new FingerTree(new Node(left->root, tree->root->right, size),
value);
} else {
return new FingerTree(new Node(left->root, tree->root, size), value);
}
} else {
FingerTree* right = insert(new FingerTree(tree->root->right), index -
tree->root->left->size, value);
int size = tree->root->size + 1;
if (size % 2 == 0) {
return new FingerTree(new Node(tree->root->left, right->root, size),
value);
} else {
return new FingerTree(new Node(tree->root, right->root, size),
value);
}
}
}

Advantages of Finger Search Tree:

• Efficient searching: Finger trees support fast search operations with a

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

worst-case time complexity of O(log n), making them suitable for

applications that require frequent searching.
• Flexible: Finger trees can be used to implement a wide range of data
structures, including priority queues, ordered sets, and sequences.
• Persistent: Finger trees support efficient persistent data structures,
which allow multiple versions of a data structure to be maintained
without affecting the original structure.
• Easy to implement: Finger trees have a simple and elegant recursive
structure that makes them easy to implement and understand.
Disadvantages of Finger Search Tree:
• Overhead: Finger trees have a higher memory overhead than other
search tree data structures because they require additional information
to be stored at each node, including the size of the subtree.
• Complex operations: Some operations, such as concatenation and
splitting, can be more complex and less efficient in finger trees than in
other search tree data structures.
• Lack of popularity: Finger trees are not as widely used as other search
tree data structures, so there may be less community support and fewer
third-party libraries available.

Biased Search Tree

A biased search tree is a type of search tree designed to optimize access time
for items with varying access frequencies. Unlike standard balanced search
trees (like AVL trees or Red-Black trees) that aim for uniform access time for
all elements, biased search trees prioritize faster access to more frequently
accessed items.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Here's how they work:

• Known Access Frequencies:
Biased search trees assume that each item in the tree has a known "weight" or
estimated access frequency. This weight represents how often that particular
item is expected to be searched for.
• Minimizing Weighted Average Access Time:
The primary goal is to arrange the tree structure such that the average access
time, weighted by these frequencies, is minimized. This means items with
higher weights are placed closer to the root, resulting in fewer comparisons
and faster retrieval.
• Self-Balancing with Bias:
While they are biased towards frequently accessed items, these trees still need
to maintain a certain level of balance to prevent worst-case scenarios and
ensure efficient updates (insertions and deletions). They achieve this through
specialized balancing mechanisms that take the item weights into account.
Examples of Biased Search Trees:
• Splay Trees:
While not explicitly designed for known access frequencies, splay trees are a
form of self-adjusting binary search tree that implicitly achieve a form of bias
by moving recently accessed items closer to the root.
• Biased a,b Trees:
These are a generalization of B-trees designed for biased access in external
memory, particularly useful in paged environments.
• Pseudo-weight-balanced Trees:
A simpler, biased version of weight-balanced trees, offering easier
implementation and analysis while still providing efficient biased access.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Applications:
Biased search trees are valuable in applications where access patterns are non-
uniform and can be predicted or estimated. This includes:
• Efficient table storage:
Databases or caching systems where certain records are accessed more
frequently than others.
• Network optimization algorithms:
Routing tables or other network structures where certain destinations are more
common.
• Data structures for statistical analysis:
When analyzing data with skewed distributions, biased trees can accelerate
access to frequently occurring values.
Data Structure for External Storage
A data structure for external storage is designed to efficiently organize and
retrieve data that is too large to fit in a computer's main memory (RAM) and
must reside on slower, non-volatile external memory, like hard disks or solid-
state drives. The primary goal of these structures is to minimize costly
input/output (I/O) operations, which involve moving data between the
external storage and RAM.
The most widely used and prominent external storage data structures include:
• B-trees and their variants (like B+ trees)
• External merge sort
• Hashing
B-Trees and B+ Trees
B-trees are the most common and asymptotically optimal data structures for
disk-based storage, used extensively in database and file systems.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

How B-Trees work

• Reduced height: Unlike binary search trees, B-tree nodes can have
many children, which makes the tree's overall height very short. This
significantly reduces the number of disk I/O operations required to find
an item.
• Nodes as disk blocks: The size of a B-tree node is designed to match
the block size of the underlying disk. This means that a single disk read
operation can fetch an entire node into main memory.
• Keys and children: Each node contains a sorted list of keys and
pointers to its children. To search for a key, the algorithm compares it
against the keys in the current node to decide which child to traverse
next.
• Self-balancing: B-trees are self-balancing, meaning all leaf nodes are
at the same depth. This ensures consistent, fast performance for
searches, insertions, and deletions, which are guaranteed to take
(log ) I/O operations.

How B+ Trees differ

B+ trees are a refinement of B-trees that offer even better performance for
certain operations, particularly range queries.
• Leaf-only data storage: All data (or pointers to data) are stored
exclusively in the leaf nodes. This allows internal nodes to store only
keys and child pointers, enabling them to fit more keys and make the
tree even wider and shorter.
• Linked leaves: The leaf nodes are linked together in a sequential, left-
to-right manner. This makes it incredibly efficient to perform range

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

queries, as you only need to find the start of the range and then traverse
the linked list of leaves.
External merge sort
External merge sort is an algorithm specifically designed to sort massive
datasets that do not fit into main memory.
How it works
1. Sorting Phase: The data is broken into smaller "chunks," each of which
can fit into the main memory. An efficient in-memory sorting algorithm
(like quicksort or heapsort) is used to sort each chunk.
2. Merging Phase: The sorted chunks are written to temporary files on
external storage. Then, they are merged back together into a single
sorted file. This is often done with a multi-way merge, where several
chunks are merged simultaneously to minimize passes.
Hashing
Hash-based indexes are another method for external storage, most effective
for equality-based searches.
How it works
• Hash function: Records are stored in "buckets" on disk. A hash
function is used to compute the address of a bucket where a record
should be stored.
• Direct access: For a search, the hash function is applied to the search
key to directly calculate the location of the record's bucket, minimizing
the need for multiple disk accesses.
• Limitations: While excellent for equality searches, hashing is
inefficient for range queries, which require a tree-based index.
51
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Indexed Sequential Access Method (ISAM): An older indexing

structure that stores records in a sorted sequence and maintains a
separate index for quick access. While simple, it is less dynamic than
B-trees.
• Heap Files: The simplest file organization, where records are inserted
into a file in no particular order. This is efficient for insertions but
inefficient for searches, as it requires a full file scan.
• Buffer Management: All these external data structures rely on a buffer
manager to handle the efficient transfer of data blocks (or "pages")
between external storage and main memory. The buffer manager
decides which pages to keep in memory (caching) to minimize disk
access.
Review of 2-3-4 Tree and 2-3 Tree
2-3-4 Tree
A 2-3-4 tree is a self-balancing tree. The number represents the number of
children each node can have. Any internal node can have either two, three,
or four child nodes. It is also called a 2-4 tree.
Note: It is a B-tree of degree four and all leaf nodes at the same level

Properties of a 2-3-4 Tree:

• A 2-node has one data element and if it is an internal node, then it has
two child nodes.
• A 3-node has two data elements and if this is an internal node, it has
three child nodes.
• A 4-node has three data elements and if it is an internal node, it has four
child nodes.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• The elements in each node should be sorted from smallest to

greatest.
• 2-3-4 tree is a perfectly balanced tree i.e., in this all leaf nodes are at the
same level.
• The type of any node is decided based on the structure of the tree (the
structure gets decided such that the tree is always a perfectly balanced
tree).
Structure of a node in 2-3-4 Tree:
Each node can have either 2, 3, or 4 children each of which holds 1, 2, or 3
data elements respectively. The data elements determine the range of the
elements that will lie in which segment. See the following figure to get an idea
of that:

Operations in a 2-3-4 tree:

There are three basic operations that are performed in a 2-3-4 tree. The
operations are:
• Insertion of a node
• Searching a value
• Deletion of a node
Insertion in 2-3-4 tree => The root is a 2 node.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Insert 10 is
• now a 3 node.

• Insert 20ow
• a 4 node.

• Insert 3040 with the node containing 30.

•
• 50: becomes a 4 node.

insert 60 in the node with

value 50.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Complexity Analysis of 2-3-4 trees:

• Searching, insertion, and deletion all take O(logN) time complexity in
2-3-4 trees. Since the 2-3-4 is always balanced. By repeating inserting
to initialize the 2-3-4 tree, we may say the time cost of init is
O(n*log(n)).
• Height: In the worst case in 2-3-4 trees the height is logN and in the
best case the height is 1/2 * logN (It is the condition when all nodes are
4 nodes).

2-3 Tree
In binary search trees we have seen the average-case time for operations like
search/insert/delete is O(log N) and the worst-case time is O(N) where N is
the number of nodes in the tree.
Like other Trees include AVL trees, Red Black Tree, B tree, 2-3 Tree is also
a height balanced tree.
The time complexity of search/insert/delete is O(log N) .
A 2-3 tree is a B-tree of order 3.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Properties of 2-3 tree:

• Nodes with two children are called 2-nodes. The 2-nodes have one data
value and two children
• Nodes with three children are called 3-nodes. The 3-nodes have two
data values and three children.
• Data is stored in sorted order.
• It is a balanced tree.
• All the leaf nodes are at same level.
• Each node can either be leaf, 2 node, or 3 node.
• Always insertion is done at leaf.
Search: To search a key K in given 2-3 tree T, we follow the following
procedure:
Base cases:
1. If T is empty, return False (key cannot be found in the tree).
2. If current node contains data value which is equal to K, return True.
3. If we reach the leaf-node and it doesn't contain the required key
value K, return False.
Recursive Calls:
1. If K < [Link], we explore the left subtree of the current
node.
2. Else if [Link] < K < [Link], we explore the
middle subtree of the current node.
3. Else if K > [Link], we explore the right subtree of the
current node.
Consider the following example:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Insertion: There are 3 possible cases in insertion which have been discussed
below:
• Case 1: Insert in a node with only one data element

• Case 2: Insert in a node with two data elements whose parent contains
only one data element.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Case 3: Insert in a node with two data elements whose parent also
contains two data elements.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

B-Tree (Balanced Tree)

A B-Tree is a self-balancing search tree that maintains sorted data and allows
efficient search, insertion, and deletion operations. Unlike binary search
trees, each node in a B-tree can have multiple keys and multiple children.
It is mainly used in databases and file systems where large amounts of data
are stored on disk because it reduces the number of disk accesses.

Properties of B-Tree
1. Balanced: All leaf nodes are at the same level (no imbalance).

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

2. Multi-way Search Tree:

o Each node can store multiple keys (not just one like in BST).
o A node with n keys has exactly n+1 children.
3. Sorted Order: Keys within a node are sorted in increasing order.
4. Height is Low: Because nodes can have many children, the height of
the tree remains small.
5. Root Constraints:
o Root must have at least 1 key.
o Other internal nodes must have at least ⌈m/2⌉ − 1 keys (where m
= order of the B-Tree).

Structure of a Node
• Each node contains:
o A list of keys (sorted).
o A list of child pointers.
• Example (order 4 B-tree):
o Each node can have 3 keys (max) and 4 children (max).
Operations
1. Search:
o Works like binary search but within nodes.
o If the key is not found in the node, the proper child pointer is
followed.
o Takes O(log n) time.
2. Insertion:
o New key is always inserted at a leaf node.
o If the node becomes overfull (more than max keys), it is split

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

into two nodes and the middle key is moved up to the parent.
o Splitting may propagate upward until the root, which may
increase the tree’s height by 1.
3. Deletion:
o More complex than insertion.
o If key is in a leaf, simply remove it.
o If key is in an internal node, replace it with predecessor/successor
and then remove from leaf.
o If a node goes below minimum keys, borrowing or merging
with sibling nodes is done to maintain balance.

Complexity
• Search: O(log n)
• Insertion: O(log n)
• Deletion: O(log n)
• Because height of tree = O(log n) (very shallow due to multiple
children).
Advantages
• Keeps data balanced → avoids skewed trees.
• Fewer disk reads (good for databases, file systems).
• Efficient for large data sets.
Disadvantages
• Implementation is more complex than BST.
• Not always optimal for small in-memory structures (AVL/Red-Black
Trees may be better).

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Applications
• Used in Databases (like MySQL, PostgreSQL) for indexing.
• File systems (e.g., NTFS, HFS, Ext4).
• Search engines and data retrieval systems.

B+ Tree
Definition
A B+ Tree is an extension of a B-Tree in which:
• All data values are stored only in the leaf nodes.
• Internal nodes store only keys (indexes) to guide the search.
• Leaf nodes are linked together in a linked list for fast sequential access.

Properties of B+ Tree
1. Balanced: Like B-tree, all leaf nodes are at the same level.
2. Internal Nodes: Contain only keys (no data).
3. Leaf Nodes: Contain both keys and data pointers (actual records or
pointers to records).
4. Linked Leaves: Leaf nodes are linked using pointers, making range
queries and sequential access very efficient.
5. Root:
o Root has at least 2 children (unless it’s also a leaf).
o Minimum keys in internal nodes = ⌈m/2⌉ − 1 (where m = order of
tree).
6. More Keys in Leaves: Leaf nodes can hold up to m keys, but internal
nodes hold only up to m-1 keys.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Structure of a B+ Tree Node

• Internal node: Contains only keys and child pointers.
• Leaf node: Contains (key, data pointer) pairs + a pointer to the next
leaf.
Example (order = 4 B+ tree):
• Internal node: max 3 keys + 4 children.
• Leaf node: max 4 data entries + pointer to next leaf.

Operations
1. Search:
o Performed by traversing down the internal nodes (like in B-
Tree).
o Final result always found in leaf nodes.
o Time = O(log n).
2. Insertion:
o Insert into correct leaf node.
o If leaf node overflows (more than max keys), split the node.
o Middle key is promoted to parent (like B-Tree).
o Splitting may propagate up to root.
3. Deletion:
o Always done from leaf nodes.
o If node underflows, borrowing or merging is done (same as B-
Tree).
o Internal nodes only store keys for guiding search, so deletion
from internal node is simpler.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Complexity
• Search: O(log n)
• Insertion: O(log n)
• Deletion: O(log n)
• Range Queries: O(log n + k) (where k = number of elements in range,
because of linked leaves).

Advantages of B+ Tree
• Efficient range queries because of linked leaves.
• Faster search: Since internal nodes are smaller (only keys), more keys
fit in one node → fewer disk accesses.
• Better suited for database indexing.
• Provides sequential access to data.
Disadvantages
• Slightly more space required due to duplicate keys (keys are repeated
in internal and leaf nodes).
• More complex than simple BST.
Applications
• Widely used in Database Management Systems (DBMS) like
MySQL, Oracle.
• File systems indexing.
• Used in applications requiring range queries (e.g., searching between
two values).

Difference Between B-Tree and B+ Tree

Feature B-Tree B+ Tree

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Storage of Data stored in internal + leaf Data stored only in leaf

data nodes nodes
Internal nodes Keys + Data Only Keys
Leaf node Not linked Linked (supports range
links queries)
Searching Slower for range queries Faster for range queries
Access Random access Both random + sequential

Priority Queue and Concatenable Queue using 2–3 Trees

1. Priority Queue using 2–3 Tree

Priority Queue – Reminder
A priority queue is an abstract data type where:
• Each element has a priority.
• Elements with higher priority are served before lower priority ones.
• Main operations:
o Insert(x, priority) → insert element with given priority.
o Find/Delete-Min (or Max) → find and remove the element
with highest/lowest priority.
How 2–3 Tree is used?
A 2–3 Tree is a balanced search tree where every internal node has either:
• 2 children and 1 key
• 3 children and 2 keys
It always remains balanced → height = O(log n).
To implement a priority queue:
• Store elements in the 2–3 Tree ordered by priority value.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Insert: Insert like a normal 2–3 tree insertion (O(log n)).

• Find-Min / Find-Max:
o Minimum → leftmost leaf.
o Maximum → rightmost leaf.
o Both can be found in O(log n).
• Delete-Min / Delete-Max: Delete element from the leaf, then
rebalance if needed (O(log n)).
2. Concatenable Queue using 2–3 Tree
Concatenable Queue – Reminder
A concatenable queue is like a deque (double-ended queue) but with an
extra operation:
• Concatenate(Q1, Q2): Combine two queues into one in O(log n)
time.
It supports:
• Insert at front/rear.
• Delete from front/rear.
• Concatenate two queues.
How 2–3 Tree is used?
• Each queue is stored in a 2–3 Tree, maintaining elements in sorted or
sequential order.
• Insert/Delete at ends:
o Insertion at front → insert at leftmost leaf.
o Insertion at rear → insert at rightmost leaf.
o Deletion works similarly.
• Concatenate(Q1, Q2):
o Join the 2–3 trees of Q1 and Q2.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

o This is done by creating a new root and adjusting keys so that

all elements of Q1 < Q2.
o Since height is O(log n), concatenation takes O(log n).

Operation Priority Queue (2–3 Concatenable Queue (2–3

Tree) Tree)
Insert O(log n) O(log n)
Delete O(log n) (min/max) O(log n) (front/rear)
Concatenate Not applicable O(log n)
Find O(log n) Not required
Min/Max

Applications
• Priority Queue: Scheduling, Dijkstra’s algorithm, job processing.
• Concatenable Queue: Text editing (concat lines/paragraphs),
symbolic computations, functional programming.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Unit – 2
Advanced Heaps
Review of Heaps
Heaps are tree-based data structures, typically a complete binary tree, that
maintain a heap order property (parent is always greater or less than children)
to allow for efficient O(log n) insertion/deletion and O(1) retrieval of the
min/max element. They are ideal for implementing priority queues and are
used in algorithms like HeapSort. Advanced variations like binomial
heaps offer efficient O(log n) or O(1) merging of heaps, a capability lacking
in standard binary heaps.
Properties
• Complete Binary Tree:
Heaps are almost completely filled, with all levels (except possibly the last)
fully populated, and the last level filled from left to right, ensuring efficient
storage in arrays.
• Heap Order Property:
• Min-Heap: A parent node's value is less than or equal to its
children's values.
• Max-Heap: A parent node's value is greater than or equal to its
children's values.
• Array Implementation: Due to the complete binary tree structure,
heaps can be effectively stored in an array, with the root at index 1 and
children of node i at indices 2i and 2i+1.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Efficiency
• Insertion/Deletion:
Operations take O(log n) time, where n is the number of elements, due to the
need to maintain the heap property.
• Min/Max Element Access:
Retrieving the minimum (in a min-heap) or maximum (in a max-heap)
element is an O(1) operation, as it is always at the root.
• Heap Construction:
An array can be converted into a heap in O(n) time, which is faster than
inserting elements one by one.
Applications
• Priority Queues: Heaps are the underlying structure for priority
queues, enabling efficient selection and removal of the highest-priority
(min or max) element.
• HeapSort: This sorting algorithm uses a heap to sort elements in O(n
log n) time.
• Graph Algorithms: Used in algorithms like Dijkstra's and Prim's for
efficient processing of vertices by priority.
Advanced Heaps
• Binomial Heaps:
These heaps allow for efficient merging of two heaps in O(log n) or even O(1)
time, depending on the variation, which is a significant advantage over
standard binary heaps where merging requires rebuilding.
• Fibonacci heaps:
Another advanced type of heap, Fibonacci heaps provide superior amortized
time complexity for operations like decrease-key, making them suitable for
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

specific graph algorithms.

Binomial Tree
A Binomial Tree of order 0 has 1 node. A Binomial Tree of order k can be
constructed by taking two binomial trees of order k-1 and making one the
leftmost child of the other.

The Binomial tree Bk is the ordered tree made of linking two binomial trees,
Bk-1 in which one becomes the leftmost child or the other. The number of
nodes the zero-order binomial tree has is 1.
Some properties of the binomial tree are:
• It has 2k2k number of nodes where k is the order.
• The tree has a depth equal to k.
• The children of the root, which has order k, are also binomial trees with
orders k-1, k-2, and 0 from left to right.

Step 1: For k = 0 (1 Node)

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

From the diagram, when the order (k = 0), only one node is present.
Step 2: For k = 1(2 Nodes)

The binomial tree of order 1 (k = 1) is formed by the two binomial trees of

order zero (k = 0). One becomes the child of the other.
Step 3: For k = 2 (4 Nodes)

The binomial tree of order 2 (k = 2) is formed by the two binomial trees of

order zero (k = 1). One becomes the child of the other.
Step 4: For k = 3(8 Nodes)

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

The binomial tree of order 3 (k = 3) is formed by the two binomial trees of

order zero (k = 2). One becomes the child of the other.

Binomial Heap
The main application of Binary Heap is to implement a priority queue.
Binomial Heap is an extension of Binary Heap that provides faster union or
merge operation with other operations provided by Binary Heap.
A Binomial Heap is a collection of Binomial Trees.

Introduction to Binomial Heap

A binomial heap is a collection of binomial trees, each of which satisfies the
heap property, i.e., the min-heap property. Each binomial tree is in heap order.
So we can say the key of the node is greater than or equal to the key of its
parent. There can be at most one binomial tree of any degree.

From the given fig, we can say that it consists of binomial trees B0, B2, and
B3, which have 1, 4, and 8 nodes, so there are a total of 13 nodes. The roots
of binomial trees are linked in increasing order of their degree.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

What are the Properties of Binomial Heap?

The binomial heap has n nodes that should follow these properties:
• Each binomial tree in the heap should follow the min-heap property, i.e,
the value of the node is greater than or equal to the value of its parent.
• At least one binomial tree should be in a heap where the root has a
degree of k. where k can be any non-negative integer.
• First, ensure the min-heap property throughout the heap. The second
property is that there should be a 1+log2n1+log2n binomial tree where
n is the number of nodes in the heap.
Example of Binomial Heap

The above binomial heap has 13 nodes, i.e., it has the binomial tree B0, B2,
and B3. The nodes in B0 are 1 node, B2 has 4 nodes, and B3 has 8 nodes.
Each of the binomial trees follows the min-heap property.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

The above binomial heap has 7 nodes, i.e., it has the binomial tree B0, B1, B2.
The nodes in B0 are 1 node, B1 has 4 nodes, and B2 have 8 nodes. Each of
the binomial trees follows the min-heap property.
Binomial Heap and the Binary Representation of a Number
The binomial heap can be used to represent the binary number also, i.e., if the
binomial heap has n binomial trees, where n is the number of set bits in the
binary representation of the number.
If we want to create a binomial heap of n nodes, then it can be defined by the
binary number 'n'. Let us explain with a plethora of examples. If we want to
create a binomial heap of 15 nodes, the binary representation of 15 is 1111, so
now numbering from the right-hand side, the set bits are at positions 0,1,2,3.
Therefore, the binomial heap will be formed with 15 nodes and the binomial
tree B0, B1, B2, and B3.
Operations of Binomial Heap
The operations that could be performed in the binomial heap are given below:
• Creating a new binomial heap
• Finding the minimum key
• Union of two binomial heap
• Inserting a node
• Extracting minimum key
• Decreasing a key
• Deleting a node
Let’s discuss the above-listed operations one by one.
Creating a New Binomial Heap
Creating a new binomial heap simply takes O(1) because creating a heap will
create the head of the heap to which no elements are attached.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Finding the Minimum Key

As previously stated, a binomial heap is a collection of binomial trees, and
each binomial tree fulfills the min-heap property. It denotes that the root node
has a minimum value. To find the minimum key, we simply compare the root
nodes of all the binomial trees. In a binomial heap, the time complexity of
finding the minimum key is O(logn).
Union of Two Binomial Heap
• Union (H1, H2) combines two binomial heaps, H1 and H2, to form a
single binomial heap.
• The first step is to merge the two heaps in a non-descending order of
degrees.
• After the simple merge, we must ensure that there is only one binomial
tree of any order. To do this, we must combine binomial trees of the
same order. We go through the list of merged roots, keeping track of
three-pointers, previous, x, and next-x.
• When we traverse the list of roots, we may encounter the following four
scenarios:
• Case 1: Because the orders of x and next-x do not match, we simply
proceed.
In the three cases listed below, x and next-x are in the same order.
• Case 2: If the next-next-x order is the same, continue.
• Case 3: Link next-x to x if the key of x is lower than or equal to the key
of next-x.
• Case 4: Make x the child of next if its key is greater.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Let's understand all the above cases using a diagram.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Inserting a node
It is possible to insert an element into the heap by simply creating a new heap
that contains the element to be added and merging it with the existing heap.
The time required for a single insertion into a heap after merging
is O(logn)O(logn).
Let's use an example to understand how to add a new node to a heap:

Three binomial trees of degrees 0, 1, and 2 are given in the heap above, with
B0 attached to the top of the heap.
Let's say we need to add node 15 to the heap mentioned above.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

We must first combine the two heaps. Node 15 is connected to node 12 as

shown below because both nodes 12 and 15 have a degree of 0.

After that, assign x to B0 with a value of 12, next(x) to B0 with a value of 15,
and sibling(next(x)) to B1 with a value of 7. Because x and next(x) have the
same degree. Next(x) is dropped and attached to x because the key value of x
is smaller than the key value of next(x). It can be seen in the picture below.

Currently, x points to node 12 with degree B1, followed by x to node 7 with

degree B1, and sibling(next(x)) points to node 15 with degree B2. While x and
next(x) have the same degree, sibling(next(x)) does not have the same degree
as x. Since x's, the key value exceeds that of next(x), x is eliminated and
attached to next(x), as shown in the image below.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Right now, node 7 is pointed to by x, and node 15 is indicated by next(x).

Since both x and next(x) have degrees of B2, and x's key value is lower than
next(xkey )'s value, next(x) will be taken out and attached to x as shown in the
illustration below.

The final binomial heap after inserting node 15 has a degree of B3 and is
described above.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Extracting Minimum Key

This implies that we must eliminate an element with the smallest key value.
As is common knowledge, the root element of a min-heap contains the
smallest key value. Therefore, we must compare the root node's key value
across all binomial trees. Let's look at an illustration of how to extract the
smallest key from a heap.

Compare the root node key values of the binomial trees in the heap above
now. In the above heap, where 7 is the minimum value, 12, 7, and 15 are the
root node's key values. As a result, remove node 7 from the tree as shown in
the image below.

Nodes 12 and 25 now have degrees of B0, while node 15 has a degree of B2.
Node 12 is indicated by pointer x, node 25 by next(x), and node 15 by
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

sibling(next(x)). Because the degree of x is equal to the degree of next(x), but

not to the degree of sibling(next(x)). As shown in the below image,
node 25 will be removed and attached to node 12 because the value of pointer
x is less than the value of pointer next(x).

Node 12's degree has now been changed to B1. After extracting the minimum
key, the heap shown above is the result.
Decreasing a Key
Let's proceed to the subsequent operation on the binomial heap. Once the key's
value is reduced, it may become smaller than the key of its parent, which
constitutes a violation of the min-heap property. After lowering the key, if
such a situation arises, swap the element with its parent, grandparent, and so
forth until the min-heap property is met.
Let's use an example to comprehend how to decrease a key in a binomial heap.
Take a look at the heap below:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Decrease the key 45 by 7 from the above heap. The heap will be after 45 has
been decreased by 7.

The above heap's min-heap property is broken after the key is decreased. Now
compare 7 to its parent number 30, and since 7 is less than 30, you can
swap 7 for 30 to get the following heap:

The element 7 will be less than its parent element 8 when compared to it once
more, so the two elements will be switched, and the resultant heap will be.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

The above heap now satisfies the min-heap property. The last heap after
decreasing a key is therefore the one mentioned above.
Delete a Node
The minimum node in the heap must be deleted to remove a node from the
heap. To do this, we must first reduce the key of the node to negative infinity
(or -). With the aid of an example, we'll now see how to delete a node. Let's
say we need to remove node 41 from the heap in the example below.

First, replace the node with negative infinity (or -∞) as shown below:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

To maintain the min-heap property, swap the negative infinity with its root
node.

Extraction of the smallest key from the heap is the following step. We will
extract this key because the minimum key in the aforementioned heap is -
infinity, and the heap would be:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

The above is the final heap after deleting node 41.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Complexity of Binomial Heap

Operations Time Complexity
Making a Heap O(logn)
Inserting a node O(logn)
Extracting Minimum key O(logn)
Union or merging O(logn)
Decreasing a Key O(logn)
Deleting a node O(logn)
Finding the Minimum key O(logn)

Represent Binomial Heap

1. A binomial heap is a collection of binomial trees.
2. The binomial tree should be arranged or represented in such a way that
it allows sequential access to all of its siblings from the leftmost sibling.
3. The key concept is to represent binomial trees with each node storing
two pointers, one to the leftmost child and the other to the right sibling.

Fibonacci Heap
Fibonacci Heap
A Fibonacci heap is an advanced data structure used to implement priority
queues efficiently. It improves over traditional binary heaps and binomial
heaps, particularly in terms of amortized time complexity for several key
operations.
The key advantage of a Fibonacci heap is its fast amortized performance. The
running times of the main operations are:
• Insert → O(1) amortized
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Merge (Union) → O(1) amortized

• Extract-Min → O(log n)
This makes Fibonacci heaps one of the most efficient heap structures,
especially useful in graph algorithms like Dijkstra’s shortest path and
Prim’s minimum spanning tree.
A Fibonacci heap is organized as a collection of heap-ordered trees, where
each tree follows the min-heap property (parent’s key ≤ children’s keys).
Among all roots, the one with the smallest key is kept at the front of the root
list for quick access.
When a new element is inserted, it is simply added as a new singleton tree in
the root list. When two Fibonacci heaps are merged, their root lists are
concatenated, making the union operation extremely fast. During extract-
min, the tree with the minimum root is removed, and its children are added to
the root list, after which the heap may require restructuring.

A unique feature of Fibonacci heaps is lazy consolidation. Instead of merging

trees immediately after every operation, the heap delays merging until it
becomes necessary, typically during extract-min. This batching approach
allows operations to be more efficient overall, reducing repeated restructuring.

In summary, a Fibonacci heap combines the flexibility of multiple heap-

ordered trees with amortized constant-time insert and merge operations, along
with efficient extract-min. Its design makes it especially valuable in
algorithms that require repeated decrease-key or merge operations.

A Fibonacci heap is a highly efficient data structure for implementing priority

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

queues, with fast amortized running times for operations such as insert, merge
and extract-min. Its use of lazy consolidation and its multi-tree structure make
it a superior alternative to traditional binary and binomial heaps in many
applications.
Heaps are mainly used for implementing priority queue.
• Binary Heap
• Binomial Heap
In terms of Time Complexity, Fibonacci Heap beats both Binary and Binomial
Heap.
Below are amortized time complexities of the Fibonacci Heap.
1) Find Min: Θ(1) [Same as Binary but not Binomial since
binomial has o(log n)]
2) Delete Min: O(Log n) [Θ(Log n) in both Binary and Binomial]
3) Insert: Θ(1) [Θ(Log n) in Binary and Θ(1) in Binomial]
4) Decrease-Key: Θ(1) [Θ(Log n) in both Binary and Binomial]
5) Merge; Θ(1) [Θ(m Log n) or Θ(m+n) in Binary and
Θ(Log n) in Binomial]
Like Binomial Heap, Fibonacci Heap is a collection of trees with min-heap or
max-heap properties. In Fibonacci Heap, trees can have any shape even if all
trees can be single nodes (This is unlike Binomial Heap where every tree has
to be a Binomial Tree).
Below is an example Fibonacci Heap taken from here.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Fibonacci Heap maintains a pointer to the minimum value (which is the root
of a tree). All tree roots are connected using a circular doubly linked list, so
all of them can be accessed using a single 'min' pointer.
The main idea is to execute operations in a "lazy" way. For example merge
operation simply links two heaps, insert operation simply adds a new tree with
a single node. The operation extract minimum is the most complicated
operation. It does delay the work of consolidating trees. This makes delete
also complicated as delete first decreases the key to minus infinite, then calls
extract minimum.
Facts about Fibonacci Heap
1. The reduced time complexity of Decrease-Key has importance in
Dijkstra and Prim algorithms. With Binary Heap, the time complexity
of these algorithms is O(VLogV + ELogV). If Fibonacci Heap is used,
then time complexity is improved to O(VLogV + E)
2. Although Fibonacci Heap looks promising time complexity-wise, it has
been found slow in practice as hidden constants are high (Source Wiki).
3. Fibonacci heaps is mainly called so because Fibonacci numbers are

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

used in the running time analysis. Also, every node in Fibonacci Heap
has a degree at most O(log n) and the size of a subtree rooted in a node
of degree k is at least Fk+2, where Fk is the kth Fibonacci number.
Advantages of Fibonacci Heap:
1. Fast amortized running time: The running time of operations such as
insert, extract-min and merge in a Fibonacci heap is O(1) for insert,
O(log n) for extract-min and O(1) amortized for merge, making it one
of the most efficient data structures for these operations.
2. Lazy consolidation: The use of lazy consolidation allows for the
merging of trees to be performed more efficiently in batches, rather than
one at a time, improving the efficiency of the merge operation.
3. Efficient memory usage: Fibonacci heaps have a relatively small
constant factor compared to other data structures, making them a more
memory-efficient choice in some applications.
Disadvantages of Fibonacci Heap:
1. Increased complexity: The structure and operations of a Fibonacci
heap are more complex than those of a binary or binomial heap, making
it a less intuitive data structure for some users.
2. Less well-known: Compared to other data structures, Fibonacci heaps
are less well-known and widely used, making it more difficult to find
resources and support for implementation and optimization.

Mergeable Heap Operations

A mergeable heap is a heap-based data structure that supports UNION, a key
operation for merging two heaps into one, in addition to standard heap
operations: MAKE-HEAP, INSERT, MINIMUM (find-min),

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

and EXTRACT-MIN. Mergeable heaps are implemented using structures

like binomial heaps or Fibonacci heaps to efficiently combine their elements
through the UNION operation, which allows for efficient merging of two
heaps into a single structure.

A mergeable heap is a heap that supports all the standard heap operations
(like insert, extract-min) plus an efficient merge operation, which combines
two heaps into one.

Core Mergeable Heap Operations

1. MAKE-HEAP(): Creates and returns a new, empty heap.
2. INSERT(H, x): Inserts an element x into heap H.
3. MINIMUM(H): Returns a pointer to the element with the minimum key
in heap H.
4. EXTRACT-MIN(H): Deletes and returns the element with the
minimum key from heap H.
5. UNION(H1, H2): Creates and returns a new heap containing all
elements from heaps H1 and H2. This operation typically "destroys"
the original heaps H1 and H2.

Basic Operations
1. Make-Heap()
o Creates a new, empty heap.
o Time Complexity: O(1)
2. Insert(H, x)
o Inserts a new element x into heap H.
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

o May involve adding x as a new tree (Fibonacci heap) or

percolating up (binary heap).
o Time Complexity:
▪ Binary Heap: O(log n)
▪ Fibonacci Heap: O(1) amortized
3. Minimum(H) / Maximum(H)
o Returns the element with the minimum (or maximum) key
without removing it.
o Time Complexity: O(1)
4. Extract-Min(H) / Extract-Max(H)
o Removes and returns the minimum (or maximum) element.
o May require restructuring or heapifying the heap.
o Time Complexity:
▪ Binary Heap: O(log n)
▪ Fibonacci Heap: O(log n) amortized
5. Union(H1, H2) / Merge(H1, H2)
o Combines two heaps H1 and H2 into a single heap containing all
elements.
o Implementation depends on the heap type:
▪ Binary Heap: O(n) (rebuild heap)
▪ Binomial Heap / Fibonacci Heap: O(1) amortized
(concatenate root lists)
6. Decrease-Key(H, x, k)
o Reduces the key of element x to k and restores heap property.
o Important in algorithms like Dijkstra.
o Time Complexity:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

▪ Binary Heap: O(log n)

▪ Fibonacci Heap: O(1) amortized
7. Delete(H, x)
o Deletes an element x from the heap.
o Often done by decreasing key to -∞ (or suitable minimum) and
then extract-min.
o Time Complexity: O(log n) (binary heap), O(log n) amortized
(Fibonacci heap)

Purpose and Advantages

The primary advantage of mergeable heaps is the efficient implementation of
the UNION operation. While standard binary heaps do not directly support
efficient merging, mergeable heap structures like binomial heaps and
Fibonacci heaps allow the UNION operation to be performed much more
quickly by restructuring the underlying trees and only re-linking pointers.
Examples of Mergeable Heaps
• Binomial Heaps:
Composed of binomial trees, where the merge operation involves linking trees
of the same order and combining them similar to adding binary numbers.
• Fibonacci Heaps:
Consist of a collection of unordered trees, with a circular doubly-linked list of
the roots and a pointer to the minimum root. The merge operation is achieved
by linking the root lists of the two heaps.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Bounding the Maximum Degree

In a heap (especially binomial or Fibonacci heaps), the degree of a node is
the number of its children. Bounding the maximum degree is important for
analyzing time complexity of operations like extract-min or union.

Bounding the maximum degree in a data structure involves defining or

restricting the highest number of connections a node can have to ensure
efficient performance and prevent resource exhaustion. This is often achieved
by maintaining a constant upper bound, such as using a Fibonacci heap's rules
to control node degrees or a B-tree's order to limit children. Bounding the
maximum degree is crucial for guaranteeing predictable time complexities for
operations like searching, inserting, and deleting, and for creating space-
efficient data structures.

Why Bounding the Maximum Degree is Important

• Performance Guarantees: A fixed, small maximum degree ensures
that certain operations, such as merging trees in a Fibonacci heap or
traversing a node in a B-tree, take a predictable amount of time.
• Resource Efficiency: Limiting the degree prevents any single node
from becoming a bottleneck, which is especially important for large
datasets and disk-based storage systems.
• Structural Balance: Many data structures, like Fibonacci heaps and B-
trees, rely on bounding the maximum degree to maintain their balanced
structure, which is key for their overall efficiency.

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

Examples of Bounded Degree in Data Structures

• Fibonacci Heaps: These heaps are designed to keep the maximum
degree of any node low.
• The rules: A node that loses a child is marked, but a node that
loses a second child is moved to the root list, which helps control
the degree.
• Goal: This process ensures that the maximum degree in the heap
remains relatively small, leading to efficient extract-
min operations.
• B-Trees: These trees are specialized for disk-based storage.
• The order: A B-tree of order m has a maximum degree
of m (meaning a node can have up to m children and m-1 keys).
• Benefit: This high branching factor significantly reduces the
height of the tree, minimizing the number of costly disk reads for
data retrieval.
• Bounded Degree Graphs: In graph theory, data structures built on
graphs with a maximum degree Δ can achieve constant-time
approximation algorithms for problems like finding a maximum
independent set.

Amortized analysis of Fibonacci Heap

The amortized analysis of a Fibonacci heap shows the average time cost over
a sequence of operations, rather than the worst-case time for a single
operation, leading to better performance for complex scenarios. This is often
achieved using a potential function method, where a function tracks the
"potential energy" of the heap, and the amortized cost is the actual cost plus
Prepared By – Ms. Bindiya Sahu
CSE DEPARTMENT
RSR RCET BHILAI
RSR RUNGTA COLLEGE OF ENGINEERING AND TECHNOLOGY
Rungta Knowledge city, Kohka – Kurud , Bhilai (C.G)-490024
Department of Computer Science & Engineering
MTECH-1st (AIML)

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

the change in potential. Operations like insert and decreaseKey often have
O(1) amortized cost, while extractMin is O(log n) amortized, making
Fibonacci heaps efficient for algorithms like Dijkstra's and Prim's.
Key Concepts
• Amortized Analysis:
Instead of looking at the worst-case of one operation, it considers the average
cost over a sequence of operations.
• Potential Function (Φ):
A function that assigns a non-negative value to the heap's state, reflecting its
"potential" for future work.
• Amortized Cost:
Actual Cost + Change in Potential. The goal is to make operations with high
actual cost also increase the potential, effectively "saving" potential for fast
operations to use later.
• Marks:
Nodes can have a "mark" which, in the potential function, contributes to the
total potential, according to TUM.
• Root List:
The collection of trees in the heap; the number of trees in the root list impacts
the potential function.
How it Works (using the potential method)
1. Define a Potential Function:
A common potential function is Φ(S) = t(S) + 2m(S), where t(S) is the number
of trees in the root list, and m(S) is the number of marked nodes in the heap,
notes from TUM.
2. Analyze Operations:

Prepared By – Ms. Bindiya Sahu

Subject: Advance Data Structure and Algorithm Subject code: 5109113(022)

• Insert: Has an actual cost of O(1) and no change in potential (no

new trees, no new marks), so the amortized cost is O(1).
• Extract-Min: This is the most complex. While it has a higher
actual cost (due to consolidation to maintain heap properties), it
decreases the number of trees in the root list and potentially
reduces marks, which decreases the potential. The amortized cost
is shown to be O(log n).
• Decrease-Key: Usually O(1) actual cost, but if the heap property
is violated, the node is cut from its parent and becomes a root,
increasing the number of trees and thus the potential. The overall
amortized cost is O(1).
3. Overall Effect:
Fast operations like insert have low actual cost but may increase the potential,
while slow operations like extract-min have a high actual cost but decrease
the potential. The potential function ensures that the total change in potential
over a sequence of operations doesn't exceed the total actual work, keeping
the amortized cost low.

Prepared By – Ms. Bindiya Sahu

CSE DEPARTMENT
RSR RCET BHILAI

BST & Avl Tree
No ratings yet
BST & Avl Tree
16 pages
Understanding Binary Search Trees and AVL Trees
No ratings yet
Understanding Binary Search Trees and AVL Trees
31 pages
Module-2 Part-1 AVL Tree
No ratings yet
Module-2 Part-1 AVL Tree
67 pages
Chapter: 3 Analysis of Sorting and Searching
No ratings yet
Chapter: 3 Analysis of Sorting and Searching
16 pages
Understanding AVL Trees: Structure & Operations
No ratings yet
Understanding AVL Trees: Structure & Operations
31 pages
AVL Trees: Structure, Rotations, and Operations
No ratings yet
AVL Trees: Structure, Rotations, and Operations
15 pages
Balanced Binary Search Trees Explained
No ratings yet
Balanced Binary Search Trees Explained
22 pages
Sayantani DSA
No ratings yet
Sayantani DSA
9 pages
AVL RB Trees
No ratings yet
AVL RB Trees
9 pages
AVL Tree Implementation Guide
No ratings yet
AVL Tree Implementation Guide
11 pages
AVL Tree Data Structure
No ratings yet
AVL Tree Data Structure
6 pages
BaoCao CayAVL English
No ratings yet
BaoCao CayAVL English
31 pages
Binary Search and AVL Trees Explained
No ratings yet
Binary Search and AVL Trees Explained
41 pages
AVL Trees
No ratings yet
AVL Trees
11 pages
Threaded Binary Trees Explained
No ratings yet
Threaded Binary Trees Explained
12 pages
Understanding AVL Trees: Balancing & Operations
No ratings yet
Understanding AVL Trees: Balancing & Operations
17 pages
AVL Trees Notes
No ratings yet
AVL Trees Notes
3 pages
AVL تابع محاضرة Tree
No ratings yet
AVL تابع محاضرة Tree
13 pages
AVL Tree: Self-Balancing BST Guide
No ratings yet
AVL Tree: Self-Balancing BST Guide
12 pages
Advanced Trees in Data Structures
100% (1)
Advanced Trees in Data Structures
13 pages
Advanced Data Structures in C++
No ratings yet
Advanced Data Structures in C++
103 pages
AVL Tree Data Structure
No ratings yet
AVL Tree Data Structure
3 pages
Converting Binary Tree to BST
No ratings yet
Converting Binary Tree to BST
7 pages
Understanding Non-Linear Data Structures
No ratings yet
Understanding Non-Linear Data Structures
66 pages
Understanding AVL Trees and Rotations
No ratings yet
Understanding AVL Trees and Rotations
14 pages
Understanding AVL Trees: Structure & Operations
No ratings yet
Understanding AVL Trees: Structure & Operations
11 pages
Binary Trees: BST & AVL Algorithms Guide
No ratings yet
Binary Trees: BST & AVL Algorithms Guide
29 pages
Understanding AVL Trees and Rotations
No ratings yet
Understanding AVL Trees and Rotations
35 pages
Lecture 10
No ratings yet
Lecture 10
7 pages
Understanding AVL Trees in Data Structures
No ratings yet
Understanding AVL Trees in Data Structures
13 pages
Understanding AVL Trees and Balancing
No ratings yet
Understanding AVL Trees and Balancing
40 pages
AVL Tree: Balancing and Operations Guide
No ratings yet
AVL Tree: Balancing and Operations Guide
42 pages
Adsj Presentation
No ratings yet
Adsj Presentation
11 pages
Binary Search Tree
No ratings yet
Binary Search Tree
7 pages
AVL Tree Operations and Applications
No ratings yet
AVL Tree Operations and Applications
12 pages
AVL Tree Insertion Visualization Guide
No ratings yet
AVL Tree Insertion Visualization Guide
116 pages
AVL and RedBlack Trees
No ratings yet
AVL and RedBlack Trees
8 pages
AVL Tree: Balancing Binary Search Trees
No ratings yet
AVL Tree: Balancing Binary Search Trees
58 pages
Unit 3
No ratings yet
Unit 3
25 pages
Disadvantages of BST vs. AVL Tree Benefits
No ratings yet
Disadvantages of BST vs. AVL Tree Benefits
22 pages
AVL Tree: Structure, Operations, and Benefits
No ratings yet
AVL Tree: Structure, Operations, and Benefits
4 pages
Understanding Tree Structures and AVL Trees
No ratings yet
Understanding Tree Structures and AVL Trees
22 pages
Understanding AVL Tree Structure
No ratings yet
Understanding AVL Tree Structure
29 pages
Understanding AVL Trees in Data Structures
100% (1)
Understanding AVL Trees in Data Structures
5 pages
Binary and AVL Trees Explained
No ratings yet
Binary and AVL Trees Explained
42 pages
Applications of AVL Trees Explained
No ratings yet
Applications of AVL Trees Explained
66 pages
AVL Trees: Advantages and Operations
No ratings yet
AVL Trees: Advantages and Operations
34 pages
Understanding AVL Trees and Rotations
No ratings yet
Understanding AVL Trees and Rotations
12 pages
Balanced Trees AVL, Heap, M-Ary
No ratings yet
Balanced Trees AVL, Heap, M-Ary
80 pages
AVL Tree Advanced Data Structure With Example
No ratings yet
AVL Tree Advanced Data Structure With Example
1 page
Trees - Unit 2
No ratings yet
Trees - Unit 2
59 pages
Understanding AVL Trees in Data Structures
No ratings yet
Understanding AVL Trees in Data Structures
20 pages
Advanced Data Structures Overview
No ratings yet
Advanced Data Structures Overview
31 pages
Advanced Tree Structures in Data Science
No ratings yet
Advanced Tree Structures in Data Science
86 pages
AVL Tree
No ratings yet
AVL Tree
46 pages
Understanding AVL Trees and Operations
No ratings yet
Understanding AVL Trees and Operations
56 pages
Understanding AVL Trees Explained
No ratings yet
Understanding AVL Trees Explained
32 pages
Understanding AVL Trees and Rotations
No ratings yet
Understanding AVL Trees and Rotations
24 pages
AVL Trees: Structure and Rotations
No ratings yet
AVL Trees: Structure and Rotations
56 pages
Non-Linear Data Structures: Trees Overview
No ratings yet
Non-Linear Data Structures: Trees Overview
88 pages
Understanding Doubly Linked Lists
No ratings yet
Understanding Doubly Linked Lists
20 pages
Understanding AVL Trees and Rotations
No ratings yet
Understanding AVL Trees and Rotations
27 pages
Graph Algorithms and Traversals Overview
No ratings yet
Graph Algorithms and Traversals Overview
226 pages
AVL Tree Operations and Balancing
No ratings yet
AVL Tree Operations and Balancing
36 pages
MCA Program Structure and Curriculum 2025
No ratings yet
MCA Program Structure and Curriculum 2025
48 pages
Advanced Data Structures Overview
No ratings yet
Advanced Data Structures Overview
115 pages
Data Structures: Concepts and Operations
No ratings yet
Data Structures: Concepts and Operations
20 pages
Understanding AVL Trees and Rotations
No ratings yet
Understanding AVL Trees and Rotations
28 pages
Basics of Compilation Process COM 413
No ratings yet
Basics of Compilation Process COM 413
34 pages
Dsoops Ii
No ratings yet
Dsoops Ii
8 pages
DSA Tree Structures and Notes
No ratings yet
DSA Tree Structures and Notes
53 pages
Understanding B-Trees: Structure & Operations
No ratings yet
Understanding B-Trees: Structure & Operations
24 pages
CSS Object-Oriented Programming Guide
100% (1)
CSS Object-Oriented Programming Guide
18 pages
AVL Tree Rotations Explained
No ratings yet
AVL Tree Rotations Explained
30 pages
Python Algorithms for Data Structures
No ratings yet
Python Algorithms for Data Structures
9 pages
Data Structures & Algorithms MCQs
No ratings yet
Data Structures & Algorithms MCQs
7 pages
Understanding AVL Tree Operations
No ratings yet
Understanding AVL Tree Operations
13 pages
Understanding B-Trees for Large Datasets
No ratings yet
Understanding B-Trees for Large Datasets
25 pages
MST Algorithms: Prim vs. Kruskal
No ratings yet
MST Algorithms: Prim vs. Kruskal
43 pages
Understanding Tree Data Structures
No ratings yet
Understanding Tree Data Structures
14 pages
CP264 Final Exam Review Guide
No ratings yet
CP264 Final Exam Review Guide
18 pages
ICPC 2020-2021 Regional Contest Problems
No ratings yet
ICPC 2020-2021 Regional Contest Problems
7 pages
AVL Tree Rotations and Balance Factors
100% (1)
AVL Tree Rotations and Balance Factors
14 pages
Data Structures: Binary Trees Explained
No ratings yet
Data Structures: Binary Trees Explained
23 pages
Data Structures Overview and Analysis
No ratings yet
Data Structures Overview and Analysis
57 pages
CS202 Data Structures Course Overview
No ratings yet
CS202 Data Structures Course Overview
2 pages
Flowchart Uses in Programming Logic
No ratings yet
Flowchart Uses in Programming Logic
20 pages
Applications of Search and Sort Algorithms
No ratings yet
Applications of Search and Sort Algorithms
12 pages